A famous theorem of number theory goes like this:<\/p>\n
For the integers a and b, there exists a solution with integers x and y to<\/p>\n
ax+by=1<\/p>\n
if and only if a and b are relatively prime.<\/i><\/p>\n
Another way to state the same theorem:<\/p>\n
ax+by=1 has integer solutions x, y iff gcd(a,b)=1 (a,b,x,y all integers).<\/em><\/p>\n 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<\/em> means “if and only if.”<\/p>\n Looking at the forward implication first, we have<\/p>\n ax+by=1→gcd(a,b)=1<\/p>\n Proof<\/u>: Suppose not; that is, suppose that ax + by=1 but gcd(a,b)=k≠1.<\/p>\n Then a=km, b=kn for integers n, m:<\/p>\n kmx+kny=1→k(mx+ny)=1→k is a factor of 1→k=1.<\/p>\n Now, let’s look the other way:<\/p>\n gcd(a,b)=1→ax+by=1 for some integers x,y.<\/p>\n Proof<\/u>: Suppose not; that is, suppose gcd(a,b)=1, but ax+by≥d for some integer d>1<\/p>\n Then there can’t be a solution for aw+dz=d+1, for, if so, then<\/p>\n 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:<\/p>\n ap+bq=md<\/p>\n Therefore, let p=1, q=d:<\/p>\n a+bd=fd<\/p>\n Then<\/p>\n a=fd-bd=d(f-b)→d is a factor of a.<\/p>\n Next, consider<\/p>\n ad+b=hd<\/p>\n Then<\/p>\n b=hd-ad=d(h-a)→d is a factor of b.<\/p>\n 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.<\/p>\n I’ll be talking more about number theory:)<\/p>\n Source:<\/p>\n Dudley, Underwood. Elementary Number Theory<\/u>. New York:<\/br> W H Freeman and Company, 1978.<\/p>\n