Number theory algorithms are used in n cryptography e.g. secure data exchange protocols (e.g. ssh, sftp, https). You've used these to communicate with business like your bank, even if you weren't aware of it. Number theory is used to construct random (actually pseudo-random) number functions for randomized data structures (e.g. hash tables), randomized algorithms (e.g. quicksort), and applications (e.g. games) that require randomization.
We won't go very deeply into number theory. We'll primarily use it as an excuse to practice direct proofs.
Here's a really nice algorithm for computing the gcd of two integers, called the Euclidean Algorithm. To keep things simple, I'm assuming that inputs are both positive. It's not hard to extend this code to handle negative inputs.
gcd(a,b)
while (b > 0)
r = remainder(a,b)
a = b
b = r
return a
Notice that this is pseudocode not real computer code. Pseudocode is written for humans. So it often leaves out small details and the syntax isn't precisely defined. That's usually not a problem.
remainder(a,b) is the remainder left when we divide a by b.
If you prefer, we can write this recursively:
gcd(a,b)
r = remainder(a,b)
if (r = 0)
return b
else
return gcd(b,r)
This is an extremely nice algorithm. It's very efficient and it's very easy to simulate by hand. Our job today will be to understand why it works.
First, let's pin down what the remainder function does. Here's a possible definition of quotient and remainder:
Suppose that a and b are integers, with b positive. Then the quotient (q) and the remainder (r) of a divided by b satisfy the equation: \(a = bq + r\)
So if a=15 and b=6, then we can satisfy the equation using q=2 and r=3.
However, notice that this equation doesn't completely pin down the values of q and r. We could also choose q=1 and r=9. Or q=3 and r= -3. So the actual mathematical definition contains two constraints:
Suppose that a and b are integers, with b positive. Then the quotient (q) and the remainder (r) of a divided by b satisfy the equations: \(a = bq + r\) and \(0 \le r < b\)
For example, suppose that we want to compute remainder(-15,4). The only solution to \(a = bq + r\) with b in the correct range is \(-15 = 4\cdot(-4) + 1 \) So remainder(-15,4) = 1. If you're uncertain of the correct value, remember that the remainder is never negative and set up the equation explicitly.
Beware: many programming languages do not follow the mathematical definition, and do a variety of different things when one or both inputs to remainder are negative. Always check the manual before feeding negative inputs to remainder functions.
Let's compute gcd(255,483) by tracing the values in the iterative version.
| a | b | r = remainder(a,b) | |
|---|---|---|---|
| 255 | 483 | 255 | |
| 483 | 255 | 228 | We now have \(a > b\) |
| 255 | 228 | 27 | |
| 228 | 27 | 12 | |
| 27 | 12 | 3 | |
| 12 | 3 | 0 | |
| 3 | 0 | --- | return 3 |
To show that the Euclidean Algorithm is correct, i.e. computes the gcd, we need to show three things:
(1) is true because remainder(a,b) is always strictly smaller than b. So each iteration reduces the size of b. Since the values are positive integers, this means that it must reach zero in a finite number of steps. (This wouldn't necessarily be true if the values were real numbers.)
We'll get back to (2).
To understand why (3) is true, we need to remember exactly how divides is defined in the textbook:
An integer p divides an integer q (written \(p \mid q\)) if and only if q = pn, for some integer n.
I claim that every integer divides 0. To see this, let's set up the equation from the definition: \(0 = pn\). No matter what value p has, we can make this equation balance by setting n to be zero.
Now remember that gcd(a,b) is the largest integer that divides both a and b. Since everything divides zero, a is the largest integer that divides both 0 and a. So \(\gcd(a,0)= a\).
In case you were wondering, gcd(0,0) isn't defined. Since all integers divide zero, there is no maximum divisor.
Now we need to show that resetting the variable values in our loop doesn't change the value of gcd(a,b). That is:
Claim: for any positive integers a and b, gcd(a,b) = gcd(b,remainder(a,b)).
It's actually just as easy to prove a more general claim:
Claim 2: for any integers a, b,q,r, where b is positive, if a = bq + r, then gcd(a,b) = gcd(b,r).
Here's the outline of how to prove this:
We will prove (2) in the next The proof for (3) is extremely similar, and left as an exercise. Proving these will complete the proof that our gcd algorithm is correct.
Claim: For all integers a, b, r, q, k, where b is positive, if a = bq + r and \(k \mid a\) and \(k \mid b\), then \(k \mid r\).
Also remember our definition of "divides":
An integer p divides an integer q (written \(p \mid q\)) if and only if q = pn, for some integer n.
Let's first set up our standard outline for a direct proof: introduce the variables, assume the information in the hypothesis, set out the conclusion as a goal to end the proof.
Proof: Let a, b, r, q, k be integers, with b positive. Suppose that \(a = bq + r\), \(k \mid a\), and \(k \mid b\).
....
Then \(k \mid r\), which is what we needed to show.
Now let's substitute our definition of divides into the statements immediately before and after the gap in the middle.
Proof: Let a, b, r, q, k be integers, with b positive. Suppose that \(a = bq + r\), \(k \mid a\), and \(k \mid b\).
Since \(k \mid a\), \(a = kn\) for some integer n.
Since \(k \mid b\), \(b = km\) for some integer m.
....
So \(r = kt\) where t is an integer.
Then \(k \mid r\), which is what we needed to show.
To fill in the gap, we can take \(a = bq + r\) and solve for r: \( r = a - bq \). Now substitute the values we have for a and b.
\( r = a - bq = kn - (km)q\)
Now peek ahead at the goal at the end of the gap: \(r = kt\). If we want to get the above equation into this form, we need to factor out k. That is:
\( r = a - bq = kn - (km)q = k(n - mq)\)
So t must be \(n - mq\). And t must be an integer because n, m, and q are integers.
Let's get these steps into logical order and use them to fill in the middle of our proof.
Proof: Let a, b, r, q, k be integers, with b positive. Suppose that \(a = bq + r\), \(k \mid a\), and \(k \mid b\).
Since \(k \mid a\), \(a = kn\) for some integer n.
Since \(k \mid b\), \(b = km\) for some integer m.
Since \(a = bq + r\), \( r = a - bq = kn - (km)q = k(n - mq)\).
Let \(t = n - mq\). t must be an integer because n,m,q are integers
So \(r = kt\) where t is an integer.
Then \(k \mid r\), which is what we needed to show.
Now, let's look at our other new definition: congruence mod k. The big idea behind this definition is to treat two two numbers as equivalent if they differ by a multiple of k. So if we set k=5, then
Here is our formal definition:
\(s \equiv t \pmod{k}\) if and only if \( k \mid (s-t) \)
Notice that (mod k) is a modifier on the =. So don't group this in your mind as s = (t mod k).
Sometimes (especially on examlets), we'll ask you to use this equivalent definition, which substitutes in the definition of divides:
\(s \equiv t \pmod{k}\) if and only if s = t + kj, where j is an integer
For understanding what congruence mod k means, it's helpful to know that two equivalent integers have the same remainder mod k:
\(s \equiv t \pmod{k}\) if and only if remainder(s,k) = remainder(t,k)
This isn't a good definition to use in writing proofs, because the definition of remainder is complex (two equations).
Let's do a sample proof using our definition of congruence, and also our defintion of divides. In real life, I'd probably let you avoid some of this complexity by using the alternate definition of congruence. However, I'd like to show you an example of two definitions in succession.
Claim: For any integers $a,b,c,d,k$, where $k > 0$, if \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\), then \(a+c \equiv b+d \pmod{k}\).
Solution:
Proof: let $a,b,c,d,k$ be integers, $k > 0$. Suppose \(a \equiv b \pmod{k}\) and \(c \equiv d \pmod{k}\).In exams and in tutorial we will likely let you use the following form of the definition of congruence mod \(k\): \(x \equiv y \pmod{k}\) if and only if \(x = y + nk\) for some integer \(n\). This definiton is clearly equivalent but avoids the need to expand a second definition in the proof.From the definition of mod we get $ k \mid a-b$ and $k \mid c -d$.
Let's prove the following lemma, which says that divides is linear over addition. That is, for any $a,b,k \in \mathbb{Z}$, if $k \mid a$ and $k \mid b$ then $k \mid (a+b)$.
Proof of lemma: Let $a,b,k \in \mathbb{Z}$ such that $k \mid a$ and $k \mid b$.
Since $k \mid a$ and $k \mid b$ by definition of divides $a = km$ and $b = kn$ for $n,m \in \mathbb{Z}$.
So $a+b = km + kn = k (m+n)$. Since $m,n \in \mathbb{Z}$ then $ m+n$ is also $\in \mathbb{Z}$. Thus $k \mid (a+b)$.
So we have shown that divides is linear over addition.
So since $ k \mid a-b$ and $k \mid c -d$, linearity of division tell us that $k \mid (a-b) + (c-d)$. Rearranging the righthand side gives us $k \mid (a+c) - (b+d)$. So $(a+c) \equiv (b+d) \pmod k$ which is what we needed to show.