Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A Proof involving the GCD and divisibility

  1. Sep 8, 2011 #1
    1. The problem statement, all variables and given/known data

    If two integers a and b are relatively prime and if each divides an integer n, prove that their product ab divides n

    2. Relevant equations

    1=sa+tb for some integers s and t (thm 1.35)



    3. The attempt at a solution

    I have tried many many different ways to show that ab divides n, even tried a proof by induction. None of my methods seemed to be making any progress toward showing that ab divides n. Here is an example of something I tried:

    Let gcd(a,b)=1 and let both a and b divide n.
    Then by thm 1.35 sa+tb=1 for some integers s and t
    Also we have n=aa'=bb' for some integers a' and b'
    By the division algorithm, we have unique integers q,r such that ab=nq+r with r being a non-negative integer strictly less than n. Now I want to show that r=0 but haven't found a good way to do this. Clearly we must use the fact that 1=sa+tb and n=aa'=bb', but doing this does not give me that r=0 in any way that I have found.

    If anybody has a hint or possibly a different strategy for this proof I would be very grateful!
  2. jcsd
  3. Sep 8, 2011 #2


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Have you considered using other characterizations of the GCD? Or even just using the properties of the GCD itself?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook