# Some Number Theory Basics

#### A linear combination theorem about divisors

If c|a and c|b, then c|(ax+by) for arbitrary integers x and y.

If c|a then there exists an integer n such that a=cn, similarly, b=cm for some m.

Given any integers x and y, ax+by = cnx+cmy = c(nx+my). Since n, m, x, and y are integers, then so is nx+my.

#### Concerning the gcd of a and b

Given integers a and b, there exist integers u and v such that au+bv= gcd(a,b).

Now consider the set S={ ax+by | ax+by > 0 and x and y are integers }

S is non empty since if y=0, then ax+b*0=|a| if we choose x to be 1 or -1 as necessary. The set S must contain some smallest number, say d. There exist u and v such that d=au+bv.

Now let’s apply the Division Algorithm. We can find q and r so that a=qd+r, where 0 <= r <= d.

So, r = a-qd = a-q(au+bv) = a(1-qu)+b(-qv).

Suppose r is positive. Then r is in S. This contradicts the Division Algorithm, since r<d. Hence r=0 and a=qd. Now, d|a and similarly, d|b, so d is a common divisor of a and b.

Take c to be any common divisor of a and b. c|(au+bv) and so c|d. This implies that c <= d and d must be the gcd(a,b).

Now that we know values exist, the Euclidean Algorithm for finding the gcd of two numbers can be used to find values for u and v.

#### Linear Combinations of Relatively Prime Integers

a and b are relatively prime, if and only if there exist integers x and y such that ax+by=1.