Euclid's Algorithm

Euclid of Alexandria was a Greek mathematician who lived approximately 2300 years ago and who is famous for his mathematical writing. In particular his book "The Elements" on Geometry was used as a standard textbook in schools for about 2000 years. In this book, Euclid describes a way to find the greatest common divisor of two numbers. This algorithm was the first non-trivial algorithm which survives until today. Euclid formulated it both geometrically as well as using numbers. Here an informal description.

Given the two numbers, keep replacing the larger one by the the difference of the two numbers (larger minus smaller) until both numbers are equal; the resulting number is the greatest common divisor of the both original numbers.

Here an example.

The inputs of the example are 56 and 147.
Replace 147 by 147-56; the numbers are now 56 and 91.
Replace 91 by 91-56; the numbers are now 56 and 35.
Replace 35 by 56-35; the numbers are now 21 and 35.
Replace 35 by 35-21; the numbers are now 21 and 14.
Replace 21 by 21-14; the numbers are now 7 and 14.
Replace 14 by 14-7; the numbers are now 7 and 7.
The result is 7 and indeed, 56 = 7*8 and 147 = 7*21. 21 and 8 have no common factor.

In the first case, the loop looks as follows.

  while (v != w)
    { if (v < w) { w = w-v; } else { v = v-w; } }

So the values whose greatest common divisor has to be computed is first in the two variables v and w and after the running of the loop, both variables contain the greatest common divisor.

It turns out that such a loop can be very slow in the case that one variable is small compared to the other one, say 3 and 20000000000000000. Therefore, the implementation on this webpage comes with a time bound. To speed the process up, the remainder operation % can be used. The main loop looks in the second program now as follows.

  while ((v > 0)&&(w > 0))
    { if (v < w) { w = w%v; } else { v = v%w; } }

But here some caution is needed. After the loop terminates, one of the variables v and w is 0 while the other one has the greatest common divisor. The easiest way to form an expresion containing the greatest common divisor is therefore to use v+w. The two algorithms can be activated with the following buttons.

Chinese Remainder Theorem

The Chinese remainder theorem is motivated by the following example.

Example. Assume that Linda knows that Hugo has birthday on a day ending with a 3 this month and she also knows that it is a Tuesday. Furthermore, she knows that the first of the month is a Monday. Can she determine the exact birthday, so that she knows when to call Hugo in order to gratulate him for the birthday?

Indeed, she could make a table and look it up.

     S  M Tu  W Th  F  S
        1  2  3  4  5  6
     7  8  9 10 11 12 13
    14 15 16 17 18 19 20
    21 22 23 24 25 26 27
    28 29 30 31

So it would work in this case. But does it always work? The answer is yes: Let Sunday = 0, Monday = 1, ..., Saturday = 6. Now, if there would be two days x,y such that x < y, both have the same weekday w and the same last digit d, one would know that y-x is a multiple of 7 (as the distance is a fixed number of weeks) and a multiple of 10 (as the last digit of the day is the same). So y-x = a*10 and y-x = b*7 for some natural numbers a and b. Hence y-x must have the prime factors 2,5,7 and therefore be a multiple of 70. This contradicts to 0 < y-x < 32.

How to find a solution given by the Chinese remainder theorem? Assume now that there is an array a such that 0 ≤ a[p] < p for all indices p used by the array and the goal is now to find a number b such that b % p is equal to a[p] for all p. The following program runs over all p and keeps adding the product of the previously considered primes (stored in c) until the current value of b has the correct remainder. Then c is updated to c*p so that the new value is a multiple of p and therefore future add-ons do not change the remainder modulo p.

function chineseremainder(a)
  { var p; var b = 0; var c = 1; var s = "";
    for (p in a)
      { while ((a[p] % p) != (b % p))
          { b = b+c; }
        c = c*p; }
    return(s); }

If one now sets a[2]=1, a[3]=2, a[5]=3, a[7]=4, a[11]=5, a[13]=6 then the so obtained array describes the remainders modulo the first six primes. The program computes for this input the value 29243 in 6 steps where the below table gives the values of the variable each time after leaving the while loop:

p is 2, b is 1, a[p] is 1, c is 1;
p is 3, b is 5, a[p] is 2, c is 2;
p is 5, b is 23, a[p] is 3, c is 6;
p is 7, b is 53, a[p] is 4, c is 30;
p is 11, b is 1523, a[p] is 5, c is 210;
p is 13, b is 29243, a[p] is 6, c is 2310.

The following program activates the Chinese remainder function with these input values, that is, the remainder is k for the k-th prime where k goes from 1 to 6.