# Fermat's little theorem described

1) Briefly describe the argument for why

a^p ? a (modp)

when p is a prime number and a any whole number.

What goes wrong with the argument if p is not a prime number?

2) Find each of the following remainders:

- The remainder of 2^113 when divided by 17.

- The remainder of 2^2578 when divided by 13.

- The remainder of 2^115666 when divided by 17.

Explain carefully what makes these calculations more feasible than asking to find the numbers 2^113, 2^2578, 2^115666.

3) If a and n are whole numbers and n does not divide (a^n) - a, is it possible that n is prime? Explain.

If (a^n) - a is divisible by n, is n necessarily a prime number? Explain.

4) Explain, using Fermat's little theorem, why the number of repeating decimals in the decimal expansion of 1/19 must be a factor of 18.

a. Using Fermat's theorem, find how many repeating decimals the fraction 1/19 has without computing the decimal expansion of 1/19.

b. Explain, using Fermat's little theorem, the result that states when p is a prime number other than 2 or 5, the entire decimal of 1/p repeats, instead of only part of it.

#### Solution Preview

Please find the solution attached in .docx and .pdf formats.

1) Briefly describe the argument for why a^p?a ("mod" p) when p is a prime number and a any whole number. What goes wrong with the argument if p is not a prime number?

Solution: We have a^p-a=a(a^(p-1)-1). If a=0 or a=1, then a(a^(p-1)-1)=0 and so p | a^p-a. Thus a^p?a ("mod" p) for a=0 or a=1.

Now suppose a^p?a ("mod" p) for some positive integer a. Then by the Binomial Theorem, we have

?(a+1)?^p=?_(k=0)^p?(?(p@k)) a^(p-k)=a^p+(?(p@1)) a^(p-1)+?+(?(p@p-1))a+1

Now for 0<k<p, we have

(?(p@k))=p!/(p-k)!k!

Thus we have

p!=(p-k)!k!(?(p@k))

Since p divides the left side, p must divide the right sides. Now p?(p-k)! and p?k!. Then since p is prime, it follows that p must divide (?(p@k)). Therefore,

?(a+1)?^p=a^p+(?(p@1)) a^(p-1)+?+(?(p@p-1))a+1?a+0+?+0+1?a+1 ("mod" p).

Therefore, by mathematical induction, we have

a^p?a ("mod" p) for every whole number a.

Note that the argument is not valid if p is not a prime number since in this case p does not necessarily divide (?(p@k)). For example,

?(a+1)?^6=a^6+6a^5+15a^4+20a^3+15a^2+6a+1

We see that 5^6?1 ("mod" 6), so the congruence does not hold if p is not prime.

2) Find each of the following remainders:

- The remainder of 2^113 when divided by 17. ...

#### Solution Summary

Fermat's little theorem is thoroughly modeled in this guide.