Given two numbers m and n, I need to prove that if a linearly manipulate them I can reduce them to their gcd.(adsbygoogle = window.adsbygoogle || []).push({});

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

**Physics Forums | Science Articles, Homework Help, Discussion**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# GCD question

**Physics Forums | Science Articles, Homework Help, Discussion**