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!

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?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: A Proof involving the GCD and divisibility