Thread: d>=0 is the GCD of a1,...,ar if d|ai (1<= i <= r) and t|ai (1<= i <= r) => t|d

Originally Posted by jackson1

I have to prove that in the case of r = 2 the above definition equals the "normal" definition of the GCD.


Could you please help me?
THANK YOU.

let . Then . From this its easy to see that

The regular definition says that d = GCD(a1, a2) if d | a1, d | a2 and for all t, if t | a1 and t | a2, then t <= d.

If d | a1, d | a2 and for all t, if t | a1 and t | a2, then t | d, then d = GCD(a1, a2) because t | d implies t <= d.

For the converse, you can see from the Euclid's algorithm that the number obtained in each step, including the GCD obtained in the last step, is divisible by every common divisor of a1 and a2. The same fact follows from the Bézout's Identity.

@abhishekkgp
Thank you for your reply,
but your solution assumes that a1x + a2y = d .... if I write that down, I think I have to prove that first. (?)


@emakarov
Thank you for your help,
so this is all I have to write down? is it the full solution

Originally Posted by jackson1

so this is all I have to write down? is it the full solution

I can't say which level of detail is sufficient for you. You should be convinced by the proof (e.g., you should feel comfortable convincing other people that this fact holds). It also depends on the requirements of the course.

One starts each step of Euclid's algorithm with a pair of numbers (a, b). One finds the remainder r when a is divided by b:

a = qb + r

and goes to the following step with (b, r) instead of (a, b). The important point is that the whole set of common divisors (not just GCD) of a and b is the same as for b and r. Eventually, the algorithm stops with a pair (d, 0). It follows that the set of common divisors of the very first pair (a, b) coincides with the set of common divisors of (d, 0); in particular, GCD(a, b) = GCD(d, 0). It is obvious that GCD(d, 0) = d, which therefore is GCD(a, b). Also, if t | a and t | b, then t | d. Thus, for all t, if t | a1 and t | a2, then t | GCD(a, b)

Here is another proof of this fact that does not rely on Euclid's algorithm. Let LCM(a1, a2) stand for the least common multiple of a1, a2.

Lemma 1. LCM(a1, a2) >= a1, a2 and if neither a1 | a2 nor a2 | a1, then LCM(a1, a2) > a1, a2.

Proof. The >= part is obvious because a1 | LCM(a1, a2) and LCM(a1, a2) > 0 by the definition of LCM, so a1 <= LCM(a1, a2), and similarly for a2. If LCM(a1, a2) = a1, then a2 | a1, and similarly for LCM(a1, a2) = a2.

Lemma 2. If d1, d2 | a, then LCM(d1, d2) | a.

Proof. Let r be the remainder when a is divided by LCM(d1, d2): a = q * LCM(d1, d2) + r, r < LCM(d1, d2). Assume that r > 0. Then r = a - q * LCM(d1, d2), and since both terms in the right-hand side are divisible by d1, d2, so it r. Thus r is a common multiple of d1, d2 that is smaller than LCM(d1, d2), a contradiction with the assumption that r > 0.

Theorem. For all t, if t | a1 and t | a2, then t | GCD(a, b).

Proof. Let d = GCD(a, b). If t does not divide d, then by Lemma 1, LCM(t, d) > d and by Lemma 2, LCM(t, d) is a common divisor of (a, b), which contradicts the assumption that d is the greatest common divisor.

Thank you!!!