Math: number theory: linear combinations that sum to 1

The tutor tackles an age-old proof in a new (to him, anyway) manner.

A famous theorem of number theory goes like this:

For the integers a and b, there exists a solution with integers x and y to

ax+by=1

if and only if a and b are relatively prime.

Another way to state the same theorem:

ax+by=1 has integer solutions x, y iff gcd(a,b)=1 (a,b,x,y all integers).

gcd(a,b) means the greatest common divisor of a and b; if it’s 1, a and b must be relatively prime (and vice versa). iff means “if and only if.”

Looking at the forward implication first, we have

ax+by=1→gcd(a,b)=1

Proof: Suppose not; that is, suppose that ax + by=1 but gcd(a,b)=k≠1.

Then a=km, b=kn for integers n, m:

kmx+kny=1→k(mx+ny)=1→k is a factor of 1→k=1.

Now, let’s look the other way:

gcd(a,b)=1→ax+by=1 for some integers x,y.

Proof: Suppose not; that is, suppose gcd(a,b)=1, but ax+by≥d for some integer d>1

Then there can’t be a solution for aw+dz=d+1, for, if so, then

aw+dz-(ax+by)=1, and we have a linear combination of a and b summing to 1. It follows that any linear combination of a and b is a multiple of d:

ap+bq=md

Therefore, let p=1, q=d:

a+bd=fd

Then

a=fd-bd=d(f-b)→d is a factor of a.

Next, consider

ad+b=hd

Then

b=hd-ad=d(h-a)→d is a factor of b.

By our original assumption, d≥1. Also from our original assumption, gcd(a,b)=1. However, d is a factor of both a and b. The contradiction proves that when gcd(a,b)=1, there is an integer solution to ax+by=1.

I’ll be talking more about number theory:)

Source:

Dudley, Underwood. Elementary Number Theory. New York:
  W H Freeman and Company, 1978.

Jack of Oracle Tutoring by Jack and Diane, Campbell River, BC.

Leave a Reply