Thread: Euclidean Algorithm

Prove that 7 has no expression as an integral linear combination of 18209 and 19043.

Originally Posted by JCIR

Prove that 7 has no expression as an integral linear combination of 18209 and 19043.

You should know that the gcd(a,b) divides any linear combination a and b. Now just prove that the gcd(19043,18209) does not divide 7...

Actually the gcd is quite larger than 7.