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.

Quick answer:

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.

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.

Get 48 Hours Free Access
Approved by eNotes Editorial