1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Greatest Common Divisor Theorems definition clarification.

  1. Apr 21, 2017 #1

    I read definition of GCD theorem, from book and from mathWorld website.

    There are two different statements, each separately known as the greatest common divisor theorem.
    This does not make sanse
    1. Given positive integers Inline1.gif and Inline2.gif , it is possible to choose integers Inline3.gif and Inline4.gif such that Inline5.gif , where Inline6.gif is the greatest common divisor of Inline7.gif and Inline8.gif (Eynden 2001).
    This make sense

    2. If Inline9.gif and Inline10.gif are relatively prime positive integers, then there exist positive integers Inline11.gif and Inline12.gif such that Inline13.gif (Johnson 1965).

    if I take 2nd definition from above Inline13.gif
    and take
    then divisors:


    and according to second definition.
    xm - ny = 1
    (12x3 ) - (7x5) = 1
    36 -35 = 1
    it make sense.
    but 1st definition says
    Inline5.gif ,
    we take again
    m=12 and

    no matter what values of 'x' and 'y' we pick, we can not make d smaller so it can become '1'.
    Unless we select negative x and y.
  2. jcsd
  3. Apr 21, 2017 #2


    User Avatar
    2017 Award

    Staff: Mentor

    So? The sign doesn't play any role in here, since ##\pm 1## are both unities (inverible elements). The emphasis on positive integers in definition 2 isn't really necessary here. Maybe Johnson needed it for further proofs in his context. But as the entire concept deals with the nature of integers, there is simply no meaning in dividing them into positive and negative numbers.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted