Euclidean Algorithm

J

jpanknin

Junior Member
Joined
Jan 8, 2020
Messages
126
I'm going through Wu's book "Understanding Numbers" and there's a chapter on the Euclidean Algorithm. An example is:

[math]gcd(3008, 1344)[/math]
It proceeds with the following:
[math]3008 = (2 \times 1344) + 320[/math][math]1344 = (4 \times 320) + 64[/math][math]320 = (5 \times 64) + 0[/math]
Indicating that [imath]gcd(3008, 1344) = 64[/imath]. It provides a reference to an earlier Lemma which is helpful in understanding why the remainder is also divisible by a common factor:

Lemma 32.1. Suppose A, B, C are integers which satisfy A = B + C, and suppose a nonzero integer x
divides any two of A, B, and C. Then x must also divide the third.​
It then states:

The key observation is that gcd(3008, 1344) is the same as the gcd of the two smaller numbers 1344 and 320.
This is so because the set of all common divisors of 3008 and 1344 happens to coincide with
the set of all common divisors of 1344 and 320 (and therefore the biggest common divisor is the same for either set).
​
I understand the algebraic part of the algorithm and that it works, but my questions are 1) Even if we know that 64 is "A" factor of both 3008 and 1344, how do we know that it's "THE BIGGEST" factor of the two? And 2) In the excerpt immediately above it states, "This is so because the set of all common divisors of 3008 and 1344 happens to coincide with the set of all common divisors of 1344 and 320 (and therefore the biggest common divisor is the same for either set)." Emphasis on "all" in that sentence. How do we know that ALL common divisors are the same for both pairs of numbers? I find it difficult to grasp how ALL common divisors can be the same for both pairs. How can we be sure that there isn't a larger divisor of 3008 and 1344 than there is for 1344 and 320 in the more general case of [imath]gcd(a, b)[/imath]. I get there isn't for these two numbers specifically, but more generally how can we prove this?
 
jpanknin said:
my questions are 1) Even if we know that 64 is "A" factor of both 3008 and 1344, how do we know that it's "THE BIGGEST" factor of the two?
Click to expand...
One way to know \(\displaystyle 64\) is biggest factor of \(\displaystyle 3008 \ \text{and} \ 1344\) is to use the Euclidean Algorithm which you already did and it told you \(\displaystyle 64\).

Another way is to list the prime factors of both numbers and take the common primes.

\(\displaystyle 3008 = 2^6 \times 47\)
\(\displaystyle 1344 = 2^6 \times 3 \times 7\)

We can see that they only have \(\displaystyle 2^6 = 64\) in common, so it is the biggest factor of both numbers.
 
jpanknin said:
1) Even if we know that 64 is "A" factor of both 3008 and 1344, how do we know that it's "THE BIGGEST" factor of the two?
Click to expand...
Suppose there were a bigger common factor, say f, of 3008 and 1344. Then 3008 = af and 1344 = bf for some positive integers a and b. But since 3008 - 2(1344) = 320 and 1344 - 4(320) = 64, then af - 2(bf) = 320 = (a - 2b)f, and bf - 4(a - 2b)f = 64 = (b - 4a + 8b)f is a multiple of f. So, no, f is not bigger than 64!

In other words, what was shown was that ANY common factor f of 3008 and 1344 is a factor of 64, so 64 is the greatest common factor.

jpanknin said:
2) In the excerpt immediately above it states, "This is so because the set of all common divisors of 3008 and 1344 happens to coincide with the set of all common divisors of 1344 and 320 (and therefore the biggest common divisor is the same for either set)." Emphasis on "all" in that sentence. How do we know that ALL common divisors are the same for both pairs of numbers?
Click to expand...
See if you can answer this question now.
 
Euclid's algorithm:
gcd(a, b)

Let a = xm and b = ym (m is gcf/gcd)
a - b = xm - ym = m(x - y)
Let b < a
So gcd(a, b) = gcd(b, a - b)
Continue until b = a - b

gcd(16, 8) = gcd(8, 8) = 8

gcd(36, 14) = gcd(14, 12) = gcd(12, 6) = gcd(6, 6) = 6
 
You must log in or register to reply here.
Top