Fermat’s Little Theorem Solutions

Joseph Zoller
September 27, 2015

Solutions
1. Find 331 mod 7.
[Solution: 331 ≡ 3 mod 7]
By Fermat’s Little Theorem, 36 ≡ 1 mod 7. Thus, 331 ≡ 31 ≡ 3 mod 7.
2. Find 235 mod 7.
[Solution: 235 ≡ 4 mod 7]
By Fermat’s Little Theorem, 26 ≡ 1 mod 7. Thus, 235 ≡ 25 ≡ 32 ≡ 4 mod 7.
3. Find 128129 mod 17.
[Solution: 128129 ≡ 9 mod 17]
By Fermat’s Little Theorem, 12816 ≡ 916 ≡ 1 mod 17. Thus, 128129 ≡ 91 ≡ 9 mod 17.
4. (1972 AHSME 31) The number 21000 is divided by 13. What is the remainder?
[Solution: 21000 ≡ 3 mod 13]
By Fermat’s Little Theorem, 212 ≡ 1 mod 13. Thus, 21000 ≡ 2400 ≡ 240 ≡ 24 ≡ 16 ≡ 3 mod
13.
5. Find 2925 mod 11.
[Solution: 2925 ≡ 10 mod 11]
By Fermat’s Little Theorem, 2910 ≡ 710 ≡ 1 mod 11. Thus, 2925 ≡ 75 ≡ 7(−4)4 ≡ 7 · 256 ≡
7 · 3 ≡ 21 ≡ 10 mod 11.
6. Find 220 + 330 + 440 + 550 + 660 mod 7.
[Solution: 220 + 330 + 440 + 550 + 660 ≡ 0 mod 7]
By Fermat’s Little Theorem, 26 ≡ 36 ≡ 46 ≡ 56 ≡ 66 ≡ 1 mod 7. Thus, 220 + 330 + 440 + 550 +
660 ≡ 22 + 30 + 44 + 52 + 60 ≡ 4 + 1 + 28 + 25 + 1 ≡ 4 + 1 + 4 + 4 + 1 ≡ 14 ≡ 0 mod 7.
7. Let

a1 = 4 , an = 4an−1 , n > 1

Find a100 mod 7.

[Solution: a100 ≡ 4 mod 7]
By Fermat’s Little Theorem, 46 ≡ 1 mod 7. Now, 4a ≡ 4 mod 6 for all positive a. Thus,
4ak ≡ 4 mod 6 for all positive k, which also means that ak+1 ≡ 4 mod 6 for all positive k. Let
a99 = 4 + 6t for some integer t. Then,

1
a100 ≡ 4a99 ≡ 44+6t ≡ 44 (46 )t ≡ 256 ≡ 46 ≡ 4 mod 7

(Actually an ≡ 4 mod 7 for all n ≥ 1.)

8. Solve the congruence

x103 ≡ 4 mod 11.

[Solution: x ≡ 5 mod 11]

By Fermat’s Little Theorem, x10 ≡ 1 mod 11. Thus, x103 ≡ x3 mod 11. So, we only need to
solve x3 ≡ 4 mod 11. If we try all the values from x = 1 through x = 10, we find that 53 ≡ 4
mod 11. Thus, x ≡ 5 mod 11.
9. Find all integers x such that x86 ≡ 6 mod 29.
[Solution: x ≡ 8, 21 mod 29]
By Fermat’s Little Theorem, x28 ≡ 1 mod 29. Thus, x86 ≡ x2 mod 29. So, we only need
to solve x2 ≡ 6 mod 29. This is the same as x2 ≡ 64 mod 29, which means that x2 − 64 ≡
(x − 8)(x + 8) ≡ 0 mod 29. Thus, x ≡ 8, 21 mod 29.

10. What are the possible periods of the sequence x, x2 , x3 , ... in mod 13 for different values of x?
Find values of x that achieve these periods.
[Solution: 1, 2, 3, 4, 6, 12]
By Fermat’s Little Theorem, x12 ≡ 1 (mod 13). Thus, every cyclic length has to be a factor of
12, because after 12 iterations, every cyclic should be back where it started. Thus, the possible
cycle lengths are: 1, 2, 3, 4, 6, 12.

Cycle length = 1 : x = 1 (1)

Cycle length = 12 : x = 2 (1, 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7)

Since 2 has a maximum side length, we can take powers of 2 to get the other cycle lengths:

Cycle length = 2 : x = 212/2 = 26 = 64 =⇒ x = 12 (1, 12)

Cycle length = 3 : x = 212/3 = 24 = 16 =⇒ x = 3 (1, 3, 9)
Cycle length = 4 : x = 212/4 = 23 = 8 =⇒ x = 8 (1, 8, 12, 5)
Cycle length = 6 : x = 212/6 = 22 = 4 =⇒ x = 4 (1, 4, 3, 12, 9, 10)

100
11. If a googolplex is 1010 , what day of the week will it be a googolplex days from now? (Today
is Sunday)
[Solution: Thursday (4 days from today)]
By Fermat’s Little Theorem, 106 ≡ 1 (mod 7). Thus, we want to find out what 10100 is in
mod 6. Notice that

102 = 100 ≡ 4 ≡ 10 (mod 6)

Thus, by induction it is true that 10k ≡ ‘10 ≡ 4 (mod 6) =⇒ 10100 ≡ 4 (mod 6).
Therefore, I can say that 10100 = 6c + 4 for some positive integer c. By substituting, we get
that
100 100
1010 = 106c+4 = (106 )c 104 =⇒ 1010 ≡ (1)c 1002 ≡ 1002 ≡ 22 ≡ 4 (mod 7)

2
This means that googolplex is 4 more than a multiple of 7, which means the day of the week
will increase by 4. Therefore, in googolplex days it will be a Thursday.
12. Suppose that p and q are distinct primes, ap ≡ a (mod q), and aq ≡ a (mod p). Prove that
apq ≡ a (mod pq).
[Proof:]
By Fermat’s Little Theorem, we know that ap ≡ a (mod p) and aq ≡ a (mod q) no matter
what integer a is. Combining with what is given, we have that

ap ≡ a (mod p) =⇒ (ap )q ≡ aq ≡ a (mod p) =⇒ apq ≡ a (mod p)

aq ≡ a (mod q) =⇒ (aq )p ≡ ap ≡ a (mod q) =⇒ apq ≡ a (mod q)

This means that apq = px + a = qy + a for some integers x and y. However, this then implies
that px = qy =⇒ x = qk, y = pk for some integer k, because p and q are both prime. Thus,
apq = p(qk) + a = q(pk) + a = (pq)k + a =⇒ apq ≡ a (mod pq).
x
13. Find all positive integers x such that 22 +1
+ 2 is divisible by 17.
[Solution: x = 2]
First, we need find when 2a + 2 is divisible by 17, where a is some positive integer. This is
exactly when

2a + 2 ≡ 0 (mod 17) ⇐⇒ 2a ≡ −2 ≡ 15 ≡ 32 (mod 17)

Thus, a = 5 is smallest solution.

By Fermat’s Little Theorem, we know that 216 ≡ 1 (mod 17). Thus, the cycle created by 2
has to have a length divisible by 16. Notice that 24 ≡ 16 ≡ −1 (mod 17) =⇒ 28 ≡ (−1)2 ≡ 1
(mod 17), so the cycle has a length of 8 because this is the smallest power possible. Thus,
2a + 2 ≡ 0 (mod 17) exactly when a ≡ 5 (mod 8).
Next, we need to find all x such that 2x + 1 ≡ 5 (mod 8). Simplify to get

2x + 1 ≡ 5 (mod 8) ⇐⇒ 2x ≡ 4 (mod 8)

This is only true when x = 2, because for all greater powers, 2x is divisible by 8, so the
congruency will never be true again.
x
Thus, 22 +1
+ 2 is divisible by 17 ⇐⇒ x = 2.
14. An alternative proof of Fermat’s Little Theorem, in two steps:
(a) Show that (x + 1)p ≡ xp + 1 (mod p) for every integer x, by showing that the coefficient
of xk is the same on both sides for every k = 0, ..., p.
[Proof:]
p p−1 p−1
X p k p
X p k p
X
p
(x + 1) = x =1+x + x ≡1+x + 0xk (mod p) = 1 + xp (mod
k k
k=0 k=1 k=1
p)
because kp has a factor of p in it when 0 < k < p.

(b) Show that xp ≡ x (mod p) by induction over x.

[Proof:]
First, we must show the base case is true for x = 0: 0p ≡ 0 (mod p). X
Second, we must prove the inductive case. Assume that xp ≡ x (mod p). Then, from
part (a) we know that:

3
(x + 1)p ≡ xp + 1 (mod p) ≡ (x) + 1 (mod p) ≡ (x + 1) (mod p)
Thus, by induction, we have shown that xp ≡ x (mod p) for every integer x

15. Let p be an odd prime. Expand (x − y)p−1 , reducing the coefficients mod p.
p−1
X
[Solution: (x − y)p−1 ≡ xp−1−k y k (mod p)]
k=0
First of all, we know that

p−1 p−1
X p − 1 p−1−k X (p − 1)!
(x − y)p−1
= x (−y)k = (−1)k xp−1−k y k
k k!(p − 1 − k)!
k=0 k=0

By Wilson’s Theorem, we know that (p − 1)! ≡ −1 (mod p).

Also, we can examine k!:

k! = (k)(k − 1)...(1) ≡ (k − p)(k − 1 − p)...(1 − p) (mod p)

≡ (p − k)(p − k + 1)...(p − 1)(−1)k (mod p)
≡ (−1)k (p − 1)...(p − (k − 1))(p − k) (mod p)
=⇒ k!(p − 1 − k)! ≡ (−1)k (p − 1)...(p − (k − 1))(p − k)(p − 1 − k)! (mod p)
≡ (−1)k (p − 1)! (mod p)
=⇒ k!(p − 1 − k)! ≡ (−1)k (p − 1)! (mod p)
(p − 1)!
=⇒ 1 ≡ (−1)k (mod p)
k!(p − 1 − k)!

because k! and (p − 1 − k)! are relatively prime to p, since p is prime and they have no factors
of p. Thus, by substituting, we get that

p−1 p−1
X (p − 1)! X
(x − y)p−1 = (−1)k xp−1−k y k ≡ xp−1−k y k (mod p)
k!(p − 1 − k)!
k=0 k=0

so every coefficient is reduced to 1 in mod p.