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: Question on finding the GCD of 4 numbers

  1. Jul 4, 2012 #1
    1. The problem statement, all variables and given/known data

    a_1, a_2, b_1, b_2 are all positive integers greater than one.

    Given that (a_2-1)/(a_1*a_2-1)=(b_2-1)/(b_1*b_2)

    Show that GCD(a_2-1,a_1*a_2-1,b_2-1,b_1*b_2)=1


    2. Relevant equations

    (a_2-1)/(a_1*a_2-1)=(b_2-1)/(b_1*b_2)

    3. The attempt at a solution

    If I let the GCD=d, then d|a_2-1 and d|a_1*a_2-1, so this implies that d|a_1*a_2-a_2+1-1

    -> d|a_1*a_2-a_2
    -> d|a_2(a_1-1)
    -> d|a_1-1 since d does not divide a_2

    Also, since d|b_1*b_2, and d does not divide b_2 (due to the fact that d|b_2-1), d|b_1.
    1. The problem statement, all variables and given/known data



    2. Relevant equations



    3. The attempt at a solution
     
  2. jcsd
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted