Results 1 to 6 of 6

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

  1. #1
    Newbie
    Joined
    Aug 2011
    Posts
    3

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

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

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member abhishekkgp's Avatar
    Joined
    Jan 2011
    From
    India
    Posts
    495
    Thanks
    1

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

    Quote Originally Posted by jackson1 View Post
    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 d=(a_1,a_2). Then \exists x,y \in \mathbb{Z} \, such \, that \, a_1x+a_2y=d. From this its easy to see that t|a_1, t|a_2 \Rightarrow t|d
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

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

    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.
    Last edited by emakarov; August 30th 2011 at 03:02 PM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Aug 2011
    Posts
    3

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

    @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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

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

    Quote Originally Posted by jackson1 View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Newbie
    Joined
    Aug 2011
    Posts
    3

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

    Thank you!!!
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum