Share
Explore BrainMass

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.

$2.19