2011-02-06


Division Algorithm

For any two integers (natural numbers) a < b, there are natural numbers q, r so that:
	b = aq + r		0 ≤ r < a

For instance:

	b = 7  a = 2		7 = 2(3) + 1
	b = 12 a = 2		12 = 2(6) + 0

If a = 2, the possible remainders are: 0,1
If the remainder is 0, we call b even.
If the remainder is 1, we call b odd.

	b = 17 a = 3		17 = 3(5) + 2
					17 = 3(q) + r
					17 = 3(5) + r
					17 = 15 + r
					 r = 2
	Possible remainders: 0, 1, 2


Euclid's Algorithm

Euclid's algorithm is used to determine the fastest common divisor (GCD) of two natural numbers. It uses the division algorithm.

	b = a(q1) + r1
	   /		 /
	  /      /
	 /	  /
	a = r1(q2) + r2

	r1 = r2(q3) + r3
	…

	rn-1 = rn(qn+1) ← we eventually get a remainder of zero

rn is the largest number that divides both a & b, in other words, it is the GVD of a, b.

	r = b - a(q)