Math 314 - Number Theory
Lecture Notes #8
Chapter 9 - Fermat's Little Theorem

The goal of this chapter is to discuss a method of computing the value of numbers raised to large powers in the context of modula arithmetic. The author displays tables of powers for prime numbers 3,5, and 7. The observation is that one of the columns in each of the tables has all ones (except for the first row which corresponds to 0). Upon further investigation, it is observed that the column corresponds to the power of p-1. That is a2 for 3, a4 for 5, and a6 for 7.

We are leading up to the observation that ap-1 º 1 (mod p) for every integer a ¹ 0. The first thing we want to demonstrate is that we need only worry about the integers 1,2,3,..,p-1 . That's the essence of the following theorem.

Theorem 37. If a and b are integers such that  a º b (mod m), then  an º bn (mod m) for any power n.

Proof: To be done in class. (Hint: look at an- bn can it be factored?)

We now want to state the main theorem of this chapter.

Theorem 38 (Fermat's Little Theorem). Let p be a prime number and a any integer between 0 and p, then ap-1 º 1 (mod p)

Now let's use Fermat's Little Theorem to compute powers. For example, let's compute 338(mod 13)

Now let's see if we can find an integer x such that x º 255 (mod 13).

Let's solve the following exponential equation: x2 º 3 (mod 13)

Exercise 9.2 on p. 63 is essentially the theorem called by the name Wilson's Theorem in the literature. As it turns out, it is a little more difficult to prove than Fermat's Little Theorem. For the record we'll record it as follows:

Theorem 39 (Wilson's Theorem). The integer p is a prime if and only if (p-1)! º -1 (mod p).

Proof. We may or may not prove this theorem in class.

If you attempt to work exercise 9.2, you will probably observe that (p-1)! º p-1 (mod p) but this is the same as the statement of the theorem since (p-1) º -1 (mod p).

Self Test:
  1. Exercise 9.1 p. 63
  2. Show that a30º 1 (mod 77) for any a such that gcd(a,77) = 1
  3. Show that a7 º a (mod 42)
  4. If gcd(a,30)=1, show that 60 divides a4 + 59
  5. Find the units digit of 3100 (Units digit = mod 10) .
  6. For any integer a, verify that a5 and a have the same units digit.

rak - 7/02