In general, this statement is not true. Indeed, if the given integers c and d have a nontrivial common divisor, then the expression `a c + b d ` also has this divisor and therefore cannot be 1. In letters, let `c = k x ` and `d = k y , ` then `a c + b d = k ( a x + b y ) != 1 .`

The interesting fact is that if c and d are relatively prime, or have no nontrivial common divisors, then the equation `a c + b d = 1 ` has an integer solution. In a more general form, there is a solution of `a c + b d = k ` where `k = gcd ( b , d ) . ` It is called Bézout's identity.

To prove this, one uses the Euclidean algorithm. In the simplest form, this algorithm replaces a pair `( c , d ) ` with the pair `( c , d - c ) ` if `c lt d ` and `( d , c - d ) ` if `c gt d . ` It is clear that such operation preserves the greatest common divisor; in other words, `gcd ( c , d ) = gcd ( c , d - c ) .`

The steps of this algorithm preserve gcd while the numbers in pairs become smaller. At some step, the pair becomes `( k , k ) ` and we conclude that `k ` is the gcd of c and d.

The steps may be traced in the reverse order, after which k will be expressed as a linear combination of each pair, including the starting pair, which is what we want.

## See eNotes Ad-Free

Start your **48-hour free trial** to get access to more than 30,000 additional guides and more than 350,000 Homework Help questions answered by our experts.

Already a member? Log in here.

**Further Reading**