# GCD question

1. Sep 6, 2012

### Avichal

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. Sep 6, 2012

### ramsey2879

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
3. Sep 6, 2012

### Avichal

Not a homework question at all. Anyways, what is a?

4. Sep 6, 2012

### ramsey2879

a is a number coprime to y such as 1 mod y

5. Sep 6, 2012

### Avichal

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?

6. Sep 6, 2012

### ramsey2879

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.

7. Sep 6, 2012

### mathsman1963

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.