Number Theory - Euclidean Algorithm

Euclidean Algorithm
Euclidean Algorithm - is a method use to determine Greatest Common Divisor of large numbers.

Greatest Common Divisor (GCD) - is the largest number that divides evenly into each number in a
given set of numbers. (also called Greatest Common Factor, GCF).

Quotient (q) 2
Divisor (x) 2 ⟌5 Dividend (y)
4
1 Remainder ( r)

Compare the division method above to the equivalent equation of its multiplication format;

5 = 2(2) + 1, y = q(x) + r

Euclidean algorithm uses this linear equation to solve for GCD of two numbers.

, e.g. Find the GCD of given numbers; 54 and 102.

The first step is the greater number is always the value of y, the lesser number will be the value of x in
the equation.
y = q(x) + r 102 = q(54) + r, next is to determine how many 54 in 102; 102/54 =1
102 = 1(54) + 48, then the value of r is the remainder; 102 - 54 = 48

Repeat the process using y = q(x) + r until the remainder (r) will be zero. But this time, the value of x
earlier will be the value y, then the remainder will be the value of x.

54 = q(48) + r, how many 48 in 54; 54/48 = 1
54 = 1(48) + 6, remainder; 54 - 48 = 6

Repeat the process, this time x = 6, y = 48;

48 = q(6) + r, how many 6 in 48; 48/6 = 8
48 = 8(6) + 0, remainder; 48 - 48 = 0

Since the remainder is 0, the GCD of 54 and 102 is 6. ( the last value of x or in other books stated the
last value of r before r = 0, which is also equal to 6) GCD(54,102) = 6