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
You must be logged in to post a comment.