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
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
