Fermat's little theorem described

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