In the first lecture, I gave two reasons for studying different algebraic structures. One was that by examining other structures that satisfied some or all of the field laws, we would gain a better understanding of what these laws mean for teaching secondary algebra. In that vein, I hope you have gained a better understanding of the role of law 8 on the existence of multiplicative inverses. For any field, we can find a unique solution of any linear equation. If law 8 fails, then trying to solve linear equations becomes much more complicated and we are not guaranteed that a solution exists, or if it exists that it is unique.

The second reason I gave was that, having built different algebraic structures, we could apply them in different circumstances. That is what we will now start working on. We will develop the RSA public key cryptosystem, which is based on properties of exponents in modular arithmetic. We will begin with some classic results from the 17^th and 18^th centuries. In the next lecture, we will see how these were applied to modern problems in the last 25 years.

When raising elements to powers in Z_n, we will find some useful patterns. Consider Z₇. Raising 1 through 6 to various powers (mod 7) gives us the following table:

10 º 1	20 º 1	30 º 1	40 º 1	50 º 1	60 º 1
11 º 1	21 º 2	31 º 3	41 º 4	51 º 5	61 º 6
12 º 1	22 º 4	32 º 2	42 º 2	52 º 4	62 º 1
13 º 1	23 º 1	33 º 6	43 º 1	53 º 6	63 º 6
14 º 1	24 º 2	34 º 4	44 º 4	54 º 2	64 º 1
15 º 1	25 º 4	35 º 5	45 º 2	55 º 3	65 º 6
16 º 1	26 º 1	36 º 1	46 º 1	56 º 1	66 º 1

We can readily observe various patterns in this table. The powers of 6 repeat every other term. The powers of 2 and 4 repeat every three terms. The powers of 3 and 5 will repeat every 6 terms. Actually everything will repeat every 6 terms; it’s just that some of the elements repeat even more frequently. This pattern was first noted by Pierre de Fermat, who stated the following theorem.

Theorem (Fermat’s little theorem): Suppose p is prime and gcd(a,p) = 1. Then

This theorem is called Fermat’s little theorem in contrast to Fermat’s last theorem. The result is not "little," it is very important. Fermat was a 17^th century French jurist and amateur mathematician. As an amateur, he often didn’t publish the proofs of the theorems he stated. The first published proof of Fermat’s little theorem was given by Euler (after whom e = 2.718281828459045… is named) about a century after Fermat stated his result.

Proof (Euler): Euler based his proof on patterns in the multiplication tables for Z_p. Consider the multiplication table for Z₅. As before, the elements with multiplicative inverses are in bold.

´	0	1	2	3	4
0	0	0	0	0	0
1	0	1	2	3	4
2	0	2	4	1	3
3	0	3	1	4	2
4	0	4	3	2	1

If we look at any row corresponding to a bold number, we see that row contains every element of Z₅ exactly once. Our first step in proving Fermat’s little theorem is to prove that this pattern always holds for every non-zero row for every multiplication table for every prime p.

Suppose for some non-zero a, a ´ b º a ´ c. Then a ´ b – a ´ c º 0. By the distributive rule, a ´ (b - c) º 0. Since a is invertible, we must have b - c º 0, or b º c. So every product of a with different numbers must give a different answer. There are exactly p-1 non-zero elements of Z_p, so there are exactly p-1 different products of a with the non-zero elements of Z_p. Counting up, we find that every non-zero element of Z_p must appear exactly once in the row of the multiplication table corresponding to a.

Now that we have that pattern proved, we use it to prove Fermat’s little theorem. Consider the non-zero products in the row of the multiplication table corresponding to a: 1 ´ a, 2 ´ a, 3 ´ a, …, (p-1) ´ a. By our pattern, we know these are just the numbers 1, 2, 3, …, p-1 in some order. Since order doesn’t matter when we multiply, the products of all the elements in these two collections are the same:

Reordering the terms on the left we get

Now we can divide out by 1, 2, 3, …, (p-1), since they all have inverses in Z_p. Canceling out these terms leaves

which completes the proof of Fermat’s little theorem.

Euler then noticed that he had actually proved something more than Fermat had stated. The keys to the proof are the patterns in the multiplication table, and the fact that you can cancel out all the terms 1, 2, 3, …, (p-1). If we restrict our attention to the numbers with multiplicative inverses, the same patterns hold for Z_n, where n doesn’t have to be prime. For example, if we look at the multiplication table for Z₁₅ (or any other Z_n), we see that in every row for an invertible element (red in the applet below), every number appears exactly once, and the red numbers appear in all the red columns. This is the same pattern as we needed in the proof of Fermat’s little theorem, and Euler saw that he could prove it was true in the exact same way.

A result similar to Fermat’s result must also hold now, except that instead of dealing with all n-1 elements, you are only dealing with the elements that have inverses.

Theorem (Euler): Suppose gcd(a,n) = 1. Let j(n) be the number of elements of Z_n that have multiplicative inverses. Then

Proof: You should work out the proof yourself. It is exactly the same as the proof of Fermat’s little theorem, with the obvious modifications for using just the j(n) numbers which have inverses rather than all the elements.

Note that if p is prime, then j(p) = p-1 so Euler’s theorem includes Fermat’s little theorem as a special case. Euler’s theorem is the key to building the RSA public key cryptosystem, which is the topic we will cover in the next lecture.