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

GCD question

  1. Sep 6, 2012 #1
    Given two numbers m and n, I need to prove that if a linearly manipulate them I can reduce them to their gcd.
    example:- 5 and 3. 3+3-5=1 which is their gcd.

    For that I assumed m as gx and n as gy where g is their gcd and x&y are co-prime. So if I am able to prove that linear combination of x&y(any co-prime numbers) can produce 1 then I am done.

    Am I making a simple question too complicated?
    Anyways thank you
    Last edited: Sep 6, 2012
  2. jcsd
  3. Sep 6, 2012 #2
    Looks like a homework question. No you stated exactly what you must do. Not too complicated at all. Try looking at multiples of x with respect to y+a.
    Last edited: Sep 6, 2012
  4. Sep 6, 2012 #3
    Not a homework question at all. Anyways, what is a?
  5. Sep 6, 2012 #4
    a is a number coprime to y such as 1 mod y
  6. Sep 6, 2012 #5
    Well I'm going nowhere. I need to prove that linear combination of x&y(two co-prime numbers) gives one for some specific combination, right? How do I proceed with that?
  7. Sep 6, 2012 #6
    Note that x == (1+y)x mod y. Let 1 <=i,j <y and assume ix-jx = 0 mod y Since y > i,j and y does not divide x then i must equal j. Therefore there must be y-1 distinct numbers N between 0 and y such that N ==kx mod y. and 1 must be one of them.
  8. Sep 6, 2012 #7
    There is a method of finding the GCD of two numbers it is called the Euclidean Algorithm. Once the GCD is found the steps of the algorithmn can be reversed to find the GCD as a linear combination of the two numbers. Try searching for Euclidean Algorithm.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook