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.

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.

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 31So 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.

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.