Is it possible to prove that if given two integers `c` and `d` , then we can find two integers `a` and `b` such that `ac+bd=1`? If there is a way to prove this, then provide formal proof. If not, explain why.

The statement is not true, however, with some additional requirements, the statement can be true, which is proved using the Euclidean algorithm.

Expert Answers

An illustration of the letter 'A' in a speech bubbles

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.

Last Updated by eNotes Editorial on