# Math Help - Euclidean Algorithm

1. ## Euclidean Algorithm

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

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