Proving Linear Manipulation to Reduce to GCD of Two Numbers

[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

 

[ramsey2879]

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 and gx and n as gy where is 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

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.

 

[Avichal]

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.

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

 

[ramsey2879]

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

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

 

[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?

 

[ramsey2879]

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?

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.

 

[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.