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`.

Leave a Reply