Chapter 5

Modular Arithmetic Advanced

Now that we have a grip on the basics of modular arithmetic, we will discuss some more
interesting ideas in this chapter.

5.1 Solving Equations

At the end of the day, solving some sort of equation is one of the key goals of mathematicians.
That is what lead them to discover Z, Q, R and C. This is what we have done in the last
chapter too. For instance, in solving the equation ax − b ≡ 0 (mod p), we were lead to the
concept of inverses. We now talk about some other equations.

5.2 Quadratic Residues

One of the equations that lead humanity to discover irrationals was x2 = 2. In general, it
was x2 = a for a > 0. So we ask when does the equation

x2 ≡ a (mod p)

have a solution. Turns out not all a lead to a solution x. So we have 2 terms defined for this
purpose:

Definition 5.2.1. Let p be a prime. A number a is called a quadratic residue mod p if

there exists an integer x such that x2 ≡ a (mod p). It is called a quadratic non-residue
otherwise.

For instance, if p = 7, then 2 is a quadratic residue since 32 ≡ 2 (mod 7). However, 3 is

not a quadratic residue (you can check this by listing all 02 , 12 , 22 , . . . , 62 and observing that
3 never appears.)
Quadratic residues are very interesting. Hence, I have dedicated a different chapter to
them and so won’t talk about them anymore for now.

133
 5. Modular Arithmetic Advanced

5.3 Square root of -1?

Now let’s consider the equation that lead to humans discovering the complex numbers:
x2 = −1. However, this time it’s modulo p :

x2 ≡ −1 (mod p),

where p is a prime. So, we basically consider the set of numbers {a2 + 1} where a ∈
{0, 1, . . . , p − 1}, and if any element here is 0, we are done. Let’s investigate:

1. For p = 2, clearly 12 ≡ −1 (mod 2), so we ignore this case. Further, we assume p > 2
for the rest of the chapter.

2. For p = 3,
{a2 + 1}2a=0 = {1, 2, 5} ≡ {1, 2, 2} (mod 3).
So, x2 ≡ −1 (mod 3) has no solution.

3. For p = 5,
{a2 + 1}4a=0 = {1, 2, 5, 10, 17} ≡ {1, 2, 0, 0, 2} (mod 5).
So, x2 ≡ −1 (mod 5) has the solution x ≡ 3, 4. These are also the only solutions.

For cases after this, we can ease our work. Firstly, we don’t need to consider a = 0, since
02 + 1 6≡ 0 (mod p) for an prime p. Next, since a2 + 1 ≡ (−a)2 + 1 (mod p), hence we only
need to consider the first half residues mod p.

1. For p = 7,
{a2 + 1}3a=1 = {2, 5, 10} ≡ {2, 5, 3} (mod 7).
So, x2 ≡ −1 (mod 7) has no solution.

2. For p = 11,

{a2 + 1}5a=1 = {2, 5, 10, 16, 26} ≡ {2, 5, 10, 5, 4} (mod 11).

So, x2 ≡ −1 (mod 11) has no solution.

3. For p = 13,

{a2 + 1}6a=1 = {2, 5, 10, 16, 26, 37} ≡ {2, 5, 10, 3, 0, 11} (mod 13).

So, x2 ≡ −1 (mod 13) has the solutions x ≡ 5, 8. These are also the only solutions
(why?).

So we observe that x2 ≡ −1 (mod p) has solutions for some primes p, but not for the rest.

Question 5.3.1. Prove that when it has a solution, it has exactly 2.

Question 5.3.2. Check that x2 ≡ −1 (mod p) has a solution when p = 17, 29 also. Check
that there is no solution when p = 19, 23.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 134
5. Modular Arithmetic Advanced

Do you see a pattern? Can you now guess for which primes would it have a solution?
If you guessed it has a solution when p ≡ 1 (mod 4) but does not have a solution when
p ≡ 3 (mod 4), then well done. In order to prove our conjecture, we would have to show
two things: (1) there is no solution when p ≡ 3 (mod 4), and (2) there is always a solution
when p ≡ 1 (mod 4).
Now, also note that any odd prime is either 1 (mod 4), or it is 3 (mod 4). Thus our
conjecture is that x2 ≡ −1 (mod p) is equivalent to p ≡ 1 (mod 4). I will spoil it for you,
and tell you that this is true. This is often called Fermat’s Christmas Theorem1 :
Theorem 5.3.1 (Fermat’s Christmas Theorem). Let p be a prime. Then there exists an x
such that
p | x2 + 1
if and only if p = 2 or p ≡ 1 (mod 4).
Let’s first prove that p | x2 + 1 =⇒ p ≡ 1 (mod 4), which isn’t very hard.
Suppose there exists an x such that p | x2 + 1, where p > 2. Then
x2 ≡ −1 (mod p)
p−1 p−1
⇐⇒(x2 ) 2 ≡ (−1) 2 (mod p)
p−1
xp−1 ≡
⇐⇒ |{z} (−1) 2 (mod p)
≡1
p−1
where we wrote x ≡ 1 (mod p) using Fermat’s Little Theorem (note that x 6≡ 0 (mod p),
as we already rejected that case). This implies p−1
2
is even, which is the same as saying p ≡ 1
(mod 4), as needed. So this part has been proven.
Question 5.3.3. Where did we use p > 2?
Now we just have to show that for any prime p ≡ 1 (mod 4), there exists an x such that
p | x2 + 1. For this, we take the following x :
 
p−1
x= !.
2
This works, since
   
2 p−1 p−3 p−1 p−3
x = · ...1 · · ...1
2 2 2 2
      
p−1 p−3 p+1 p+3
≡ · ...1 · − · − . . . (−(p − 1))
2 2 2 2
p−1
= (−1) 2 (p − 1)! ≡ −1 (mod p)
by Wilson’s Theorem. So, this is a valid construction.
1
Actually this is not Fermat’s Christmas Theorem, the real christmas theorem is Theorem 9.3.1. However
in this book, we will use ”The Christmas Theorem” for this theorem and ”The Two Square Theorem” for
Theorem 9.3.1.
Historical note: The proof to that result (two square theorem) was announced by Fermat in a letter to
Marin Mersenne dated December 25, 1640, a Christmas Day. Hence the name.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 135
 5. Modular Arithmetic Advanced

Question 5.3.4. Where did we use the fact that p ≡ 1 (mod 4)?
Yes, I agree this is a magical construction. But if you keep Wilson’s theorem in mind,
it’s not too hard to come up with. But now, we introduce some theory which would help us
prove Theorem 5.3.1 much more naturally.

5.4 Orders
Consider a prime p. We know by Fermat’s Little Theorem that ap−1 ≡ 1 (mod p) for every
a 6≡ 0 (mod p). Also, ak(p−1) ≡ 1 for any k, i.e. a multiple of (p − 1) works too. However,
does the converse hold? That is, should aX ≡ 1 (mod p) imply X = (p − 1) or a multiple of
it?
The answer is no. For instance, when p = 5, we have 12 ≡ 1, 42 ≡ −1 (mod 5). However
these are trivial examples, since 12 , (−1)2 = 1 is always true (not just modulo p). Let me
give you some better examples
23 ≡ 1 (mod 7), 35 ≡ 1 (mod 11), 54 ≡ 1 (mod 13).
So we define something known as the order:
Definition 5.4.1. Let p be a prime and a 6≡ 0 (mod p). Then the order of a modulo p
is defined to be the smallest positive integer n such that an ≡ 1 (mod p).
We will denote it by ordp (a). Note that we take the order to be positive. It cannot be 0
(because that gives nothing useful).
Question 5.4.1. Why does the order always exist for every a? That is, why can’t we have
an a with no finite number n with an ≡ 1?
Let me give you a list of orders of a modulo 13 :

a ord
1 1
2 12
3 3
4 6
5 4
6 12
7 12
8 4
9 3
10 6
11 12
12 2
One thing we can observe is that the order always divides 12.
We can clearly see that if ordp (a) | n for some n, then an ≡ 1 (mod p). However, the
converse is also true, which makes the order a very useful concept:

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 136
5. Modular Arithmetic Advanced

Theorem 5.4.1 (Fundamental Theorem of Orders). For a prime p and any integer a 6≡ 0
(mod p), we have
an ≡ 1 (mod p) ⇐⇒ ordp (a) | n.

Proof. One direction is simple. If ordp (a) | n, then n = k · ordp (a) for some k, so an =

k
aordp (a) ≡ 1k ≡ 1 (mod p). The interesting part is the other direction.
Assume that an ≡ 1 (mod p), however ordp (a) - n. Write n = ordp (a)k + r, where
0 < r < ordp (a) (why not 0 ≤ r?). So

k
1 ≡ an ≡ ak·ordp (a)+r = aordp (a) · ar ≡ ar (mod p).

So, ar ≡ 1 (mod p). However, since 0 < r < ordp (a), we have a contradiction to the fact
that ordp (a) is the smallest positive integer satisfying aX ≡ 1 (mod p).

Comment 5.4.1: The above proof is elegant, no doubt (and the same idea which
occurred frequently in the first chapter). However another proof which is perhaps
easier to come up with is:

an ≡ 1 (mod p) and aordp (a) ≡ 1 (mod p).

So, by Example 2.12.1, we find agcd(n,ordp (a)) ≡ 1 (mod p). But if ordp (a) - n, we will
have gcd(n, ordp (a)) < ordp (a) (why?), contradicting minimality. Hence, ordp (a) | n.

This gives us a characterization of ALL numbers n such that an ≡ 1 (mod p)! In partic-
ular, we have the following:

Corollary 5.4.1 (Order divides (p − 1)). We have ordp (a) | p − 1.

Question 5.4.2. Prove the above using Fermat’s Little Theorem.

Now let’s see the power of this. We have a direct proof of one direction of Theorem 5.3.1:

Proof. Suppose that x2 ≡ −1 (mod p). Then squaring gives x4 ≡ 1 (mod p). Hence, ordp (x) |
4 =⇒ ordp (x) ∈ {1, 2, 4}. Since x2 ≡ −1 (mod p), hence the first two aren’t possible
(why?). So ordp (x) = 4.
Hence, we find that 4 | p − 1 by Corollary 5.4.1, which is what we wanted.

Example 5.4.1 (Classic)

Find all n such that n | 2n − 1.

Pick a prime p of n, so that p | 2n − 1. Then 2n ≡ 1 (mod p), so that ordp (2) | n. But
also, ordp (2) | p − 1, hence ordp (2) divides gcd(p − 1, n) (why?). So if we can select p such
that we can control gcd(p − 1, n), then we are good to go.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 137
 5. Modular Arithmetic Advanced

The idea is this: gcd(p − 1, n) is less than p − 1, and a divisor of n. So any prime factor
of this must be less than p. Hence, if we pick p to be the smallest prime factor of n, then
gcd(p − 1, n) = 1 and so ordp (2) must equal 1 (why?). Hence, p | 21 − 1 = 1, which is
impossible as p is a prime.
So is the answer no value of n? If we try n = 1, 2, 3, . . . , then we observe n = 1 works.
Question 5.4.3. Where did we miss the possibility of n = 1?
So, n = 1 is the only solution to this equation.

Example 5.4.2

Prove that every prime divisor of 2p − 1 is greater than p.

Pick a prime divisor q of 2p − 1 (like in the previous problem, why must this have a prime
divisor?). Then 2p ≡ 1 (mod q) and so ordq (2) | p. What do you notice here?
Yes, since p is a prime, hence ordq (2) ∈ {1, p}. If ordq (2) = 1, then q | 21 − 1 = 1,
impossible. So ordq (2) = p. So p | q − 1, which shows p ≤ q − 1 < q. Hence we are done!

Example 5.4.3
n
Prove that any prime factor of 22 + 1 is congruent to 1 modulo 2n+1 .
n n n+1
Suppose p | 22 + 1. Then 22 ≡ −1 (mod p), which show 22 ≡ 1 (mod p). Hence,
ordp (2) | 2n+1 . What more can we say about the order?
k
Suppose ordp (2) = 2k with k ≤ n, Then 22 ≡ 1 (mod p), but since k < n, hence this
n
shows 22 ≡ 1 (mod p), which shows p = 2 (why?), which is impossible. Hence ordp (2) is in
fact exactly equal to 2n+1 ! Hence, 2n+1 | p − 1, which is what we wanted to prove.

5.5 Primitive Roots

Clearly we have seen examples for which the order is less than p − 1. The interesting case
is when the order is p − 1. Suppose g has order (p − 1) modulo p. This means that none
of {g 1 , g 2 , g 3 . . . g p−2 } is 1. Further, this means that all these are distinct modulo p, since
g i ≡ g j ⇔ g i−j ≡ 1 (mod p). However, 0 < i 6= j < p − 1 implies 0 < i − j < p − 1,
which contradicts the fact that the order of g is p − 1. Thus, the powers of g generate all the
(non-zero) remainders modulo p. Hence we call g a generator. Another common name is a
primitive root. Before saying anything else, let’s state the definition and our observation
formally:
Definition 5.5.1. Let p be a prime. Then a residue g 6= 1 is called a primitive root mod
p if g has order (p − 1) modulo p.
Lemma 5.5.1 (Primitive Roots Generate all Non-zero Residues). Let g be a primitive root
modulo p. Then
{g 1 , g 2 , g 3 , . . . , g p−1 } ≡ {1, 2, 3, . . . , p − 1} (mod p).

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 138
5. Modular Arithmetic Advanced

Note that g x ≡ 1 (mod p) does imply (p − 1) | x, unlike what we saw in the previous
section.
Before we all fall in the flow of these and blindly start using them, here’s a question we
did not address: Does a primitive root always exist modulo p? Look at Table 5.4 and see if
there exists a primitive root modulo 13.
Question 5.5.1. List the orders of residues modulo 7, 11, 17 and see if primitive roots exist
in each case.
As you may have guessed by solving the above question, there always does exist a prim-
itive root modulo p. This is true, and it’s a very strong result in itself:
Theorem 5.5.1 (Primitive Roots Always Exists modulo p). Let p > 2 be a prime. Then
there always exists a primitive root modulo p.
We omit the proof for now. This is not very easy to prove, however you can just state
this on a contest without proof.
Primitive roots ”generate” all the residue and give us a better control over the residues
in many scenarios. Let’s see it in action now.

Example 5.5.1 (Sum of Powers mod p)

Let p > 2 be a prime. Then for any integer x,

(
−1 if p − 1 | x
1x + 2x + · · · + (p − 1)x ≡ (mod p).
0 otherwise

If x = 1, then the left side is p(p − 1)/2. Since 2 | (p − 1), hence this is p × some integer
and so 0 (mod p). Use the formula for sum of squares and sum of cubes to confirm the result
for x ∈ {2, 3}.
But in general, we don’t have a (nice) formula for sum of xth powers. So we try something
else. We can use Lemma 5.5.1 to get

1x + 2x + · · · + (p − 1)x ≡ g x + g 2x + · · · + g (p−1)x
g (p−1)x − 1
= gx · (mod p).
gx − 1
This is true unless the denominator is 0 (mod p). That happens when g x ≡ 1 (mod p),
which is the same as saying (p − 1) | x. So excluding that possibility, (g x − 1)−1 exists and
so the sum evaluates to
g (p−1)x − 1 gx
x
gx · g p−1


= · −1 ≡0 (mod p).
gx − 1 gx − 1
What about the case when (p − 1) | x? Well, in that case Fermat’s Little Theorem gives us
ax ≡ 1 (mod p) so every term in the sum is 1, so the sum becomes 1+1+· · ·+1 = (p−1) ≡ −1
(mod p). So done!

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 139
 5. Modular Arithmetic Advanced

This problem was very easy to do using primitive roots, however challenging to do oth-
erwise. Further, this is a very very important result. Always keep this in mind when dealing
with sums of powers. Also, this is an important result so remember this.

Problems for Practice

Problem 5.5.1. Let g be a primitive root modulo an odd prime p. If p = 2m + 1, then show
that
g m ≡ −1 (mod p).

Problem 5.5.2. Prove that if r is a primitive root modulo m, then so is the inverse of r
modulo m.

Problem 5.5.3. Show that there are exactly ϕ(p − 1) primitive roots modulo p.

Problem 5.5.4. Show that for any prime p, the quadratic residues mod p are exactly the
numbers g 0 , g 2 , g 4 , . . . for a primitive roots g mod p.

5.6 Some more applications

Now let’s see the power of this in proving the other direction of Theorem 5.3.1:

Proof. We want an x such that x2 ≡ −1 (mod p), if p ≡ 1 (mod 4) is a prime. Instead of

finding x, we look for a y such that (g y )2 ≡ −1 (mod p).
p−1
We can now guess a value of y; simply take y = 4
, since then g 2y = g (p−1)/2 ≡ −1
(mod p) by Problem 5.5.1, and we are home free!

Question 5.6.1. Where was the fact that 4 | p − 1 used?

Primitive roots are thus very useful in construction type problems too. Also, here’s a
lemma that you should keep an eye out since it helps to use Fermat’s Christmas Theorem:

Lemma 5.6.1. Let x ≡ 3 (mod 4). Then x has at least one prime divisor p ≡ 3 (mod 4)
which has an odd exponent.

Proof. Assume not. Then

x = pα1 1 . . . pαk ≡ 1 (mod 4)
since 1u ≡ 1 and 3even ≡ 1 (mod 4).

Example 5.6.1

Prove Wilson’s Theorem.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 140
5. Modular Arithmetic Advanced

Firstly, the case p = 2 is obvious. Now assume p is odd. Clearly we can use Lemma 5.5.1
to get:

(p − 1)! = (p − 1) · (p − 2) . . . 1
≡ g 1 · g 2 . . . g p−1
= g p(p−1)/2
= (g p−1/2 )p
≡ (−1)p = −1 (mod p).

Where g (p−1)/2 ≡ −1 follows by Problem 5.5.1.

Problems for Practice

Problem 5.6.1 (Generating numbers with orders). Let p be a prime and d be any
divisor of p − 1. Show that there exists an integer a such that ordp (a) = d.

5.7 General Orders and Primitive Roots

We have defined orders modulo a prime. However, they can easily be generalised to orders
modulo any number.

Definition 5.7.1. Let a, m be coprime integers. Then the order of a modulo m is the smallest
integer x > 0 such that ax ≡ 1 (mod m).

The theorem that aN ≡ 1 (mod m) implies ordm (a) | N also holds here, and the proof
is analogous. In particular, we find that ordm (a) | ϕ(m).
Time for a very famous example

Example 5.7.1 (Saint Petersburg Mathematical Olympiad)

Prove that for all positive integers a > 1 and n we have n | ϕ(an − 1)

The ϕ function is not easy to deal with, especially ϕ(an − 1). However, since we want
n | ϕ(an − 1), we could try to find a number which has order n modulo an − 1. The most
logical guess is a. So if we can show ordan −1 (a) = n, we are done.
However, this is not too hard. It is easy to see that the smallest integer d > 0 such that
ad ≡ 1 (mod an − 1) is n (why?), and so we are done! What an amazing application of
orders.
Similarly, we can define primitive roots in general:

Definition 5.7.2. A residue g is called a primitive root modulo m is the order of g

modulo m is ϕ(m).

However, there is some restriction:

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 141
 5. Modular Arithmetic Advanced

Theorem 5.7.1. A primitive root modulo m exists if and only if m ∈ {2, 4, pk , 2pk } for some
integer k and some prime p.

This means that if, for instance m = 57 , then there does exist a primitive root modulo
m. If m = 2 · 3 · 5, then there won’t exist a primitive root modulo m. We again, omit the
proof of this theorem.
The other properties are analogous. For instance, {g 1 , g 2 , . . . , g ϕ(m) } is the set of residues
that are coprime to m (this is the same set S we had in Theorem 2.9.1.)
Here’s a simple problem:

Example 5.7.2

Suppose that m does not have a primitive root. Show that

ϕ(m)
a 2 ≡1 (mod m)

for every a relatively prime to m.

The condition is weird, however, looking at the φ(m) we are obviously reminded of Euler’s
Totient Function. We have aϕ(m) ≡ 1 (mod m). Hence, if aϕ(m)/2 = x (mod m), then x2 ≡ 1
(mod m), i.e.  φ(m)   φ(m) 
m | a 2 − 1 a 2 + 1 = (x + 1)(x − 1).
At this point, we can now make more sense of the weird condition in the problem. Clearly
if p were a prime, then the above would imply m | (x − 1) or m | (x + 1), the former being
the one we would want.
Now if m = xy with x, y coprime and x, y > 2, then
ϕ(m) ϕ(y)
a 2 = aϕ(x)· 2 ≡1 (mod x).
ϕ(m)
Similarly it is ≡ 1 (mod y). Combining, we get a 2 ≡ 1 (mod xy). The case m = 2k with
k > 2 is left to reader.

Problems for Practice

Problem 5.7.1. Complete the proof above.

Problem 5.7.2. Show that there are ϕ(ϕ(n)) primitive roots.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 142
5. Modular Arithmetic Advanced

5.8 Example Problems

Our first example is a long one, although there aren’t a lot of clever steps involved. It’s
straightforward in the sense that each step gives a conclusion, and that conclusion gives the
next step, eventually leading us to a solution. However, this is an instructive problem and
an excellent practice for using orders.

Example 5.8.1 (USA TST 2003)

Find all ordered prime triples (p, q, r) such that p | q r + 1, q | rp + 1, and r | pq + 1.

First of all, let’s analyze only the condition p | q r + 1 (since the others are symmetric).
Now, this gives q r ≡ −1 (mod p). Hence, q 2r ≡ 1 (mod p) and so ordp (q) | 2r. Since r is a
prime, hence ordp (q) ∈ {1, 2, r, 2r}. Not too shabby. Let’s deal with each case properly:

1. Suppose ordp (q) = 1. Then p | q − 1. However, then q r ≡ 1 (mod p) combined with

p | q r + 1 implies 1 ≡ −1 (mod p), i.e. p = 2.

2. Suppose ordp (q) = 2. Then p | q 2 − 1 = (q − 1)(q + 1). As before p | q − 1 is impossible

(unless p = 2). So p | q + 1.

3. Suppose ordp (q) = r. Then q r ≡ 1 (mod p). This as before implies p = 2 (why?)

4. Suppose ordp (q) = 2r. Then 2r | p − 1. In particular, p is an odd prime and r | p − 1.

The rest of the problem is smart casework now. For now, suppose all p, q, r are odd. So, we
have obtained the following result:

Lemma 5.8.1. For odd primes x, y, z,

(
ordx (y) = 2 =⇒ x | y + 1
x | y z − 1 =⇒
ordx (y) = 2z =⇒ 2z | x − 1

Suppose ordp (q) = 2r, which gives r | p − 1. This means r | pq − 1 (why?). However,
then r | pq + 1 is impossible, since r is odd. Similarly, ordq (r) = 2p of ordr (p) = 2q are not
possible.
So ordp (q), ordq (r), ordr (p) = 2 implying p | q + 1, q | r + 1, r | p + 1. However, this doesn’t
feel to be possible for primes, because the chain seems to be ”too close”. This intuition is
formalized by using inequalities, since these three give p ≤ q + 1, q ≤ r + 1, r ≤ p + 1 and we
can’t find such primes.
At the end of all this discussion, we can conclude that our assumption that p, q, r are
all odd gives no solution. So, one of p, q, r is even, say p = 2. Then 2 | q r + 1 implies q
is odd (and nothing more, so this condition is useless now, i.e. we can’t extract anymore
information from here). Also, q | r2 + 1 implies ordq (r) = 4 (why?) implying 4 | q − 1. Lastly
r | 2q + 1 implies r is odd. So using the lemma we obtain either r | 2 + 1 = 3, or 2q | r + 1.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 143
 5. Modular Arithmetic Advanced

If r = 3, then q | 32 + 1 = 10 and so q = 5 (since we obtained q is odd). If 2q |

r + 1, then we try to combine it with q | r2 + 1. We get q | r + 1, r2 + 1 which implies
q | r2 + 1 − (r + 1)(r − 1) = 2, which is again impossible since q was odd. So if p = 2, then
(r, q) = (3, 5). Similarly we have two more solutions for the cases when q = 2 or r = 2. Hence
the solutions are:
(p, q, r) = (2, 5, 3), (3, 2, 5), (5, 3, 2).

Example 5.8.2 (Schinzel)

Find all integers n ≥ 1 such that n divides 2n−1 + 1

This has a very short solution, however is hard to come up with. Assume on the contrary
that for some n > 1 we have n|2n−1 + 1. Let p1 < p2 < · · · < pk be the prime divisors of n.
Write pi = 2ri mi + 1 with mi odd for all 1 ≤ i ≤ k. Let t = rj be the minimum of all ri . The
advantage of doing this is
Y
n= (2ri mi + 1) ≡ 1 (mod 2t ).
i

So we can write n = 2t m + 1 with m odd. Since pj = 2t mj + 1, hence

 m
n−1 mj (2t m)mj 2t mj

m
mj
≡ 2pj −1


−1 ≡ (−1) ≡ 2 =2 ≡ 2 ≡1 (mod pj ).

Hence pj = 2, which is clearly impossible.

Example 5.8.3 (Chinese TST 2005)

n
Prove that for any n > 2, the greatest prime factor of 22 + 1 is greater than or equal
to n · 2n+2 + 1.

This problem, just like the previous one, is tricky despite having a simple solutions. In
fact our solution will prove a stronger bound (try to point out how and where). Suppose
n
22 + 1 = pα1 1 . . . pαk k . Now a standard order argument shows pi ≡ 1 (mod 2n+1 ) (we saw this
in Example 5.4.3).
Hence write pi = 2n+1 xi + 1 for each i. Now firstly since pi ≥ 2n+1 + 1, hence
n
22 + 1 ≥ (2n+1 + 1)α1 +···+αk > 2(n+1)(α1 +···+αk ) .
2n
Hence, α1 + · · · + αk < n+1
.
Now if we can show xi ≥ 2(n + 1) for some i, then we are done. For this, it is enough to
show that xi (α1 + · · · + αk ) ≥ 2n+1 . How do we get terms of the form xi αi ? The answer is
binomial theorem. We get the following:

pαi i = (2n+1 xi + 1)αi ≡ 2n+1 αi xi + 1 (mod 22n+2 ).

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 144
5. Modular Arithmetic Advanced

(since 2n ≥ 2n + 2 for n ≥ 3. The cases n ≤ 2 can be checked manually). Thus

n
Y
22 = pαi i ≡ (2n+1 αi xi + 1) (mod 22n+2 )

and so 2n+1 (x1 α1 + · · · + xk αk ) ≡ 0 (mod 22n+2 ). So if xr is the largest from all of xi , then

xr (α1 + · · · + αk ) ≥ x1 α1 + · · · + xk αk ≥ 2n+1

which gives the desired bound.

Lastly, we (again) conclude with a problem which is intertwined between Number Theory
and Combinatorics:

Example 5.8.4 (ELMO 2010/5)

2010 MOPpers are assigned numbers 1 through 2010. Each one is given a red slip and
a blue slip of paper. Two positive integers, A and B, each less than or equal to 2010
are chosen. On the red slip of paper, each MOPper writes the remainder when the
product of A and his or her number is divided by 2011. On the blue slip of paper, he
or she writes the remainder when the product of B and his or her number is divided
by 2011. The MOPpers may then perform either of the following two operations:

1. Each MOPper gives his or her red slip to the MOPper whose number is written
on his or her blue slip.

2. Each MOPper gives his or her blue slip to the MOPper whose number is written
on his or her red slip.

Show that it is always possible to perform some number of these operations such that
each MOPper is holding a red slip with his or her number written on it.

We generalize the result by replacing 2011 by p for any odd prime p. It is best done by
experimenting yourself, so do that before reading the solution. Firstly, we define a few terms
for convenience:
1. Let M denote the ordered set {1, 2, · · · p − 1}. For any real constant 0 < c < p, define
cM := {c, 2c, · · · c(p − 1)}. Note that cM is a complete residue class modulo p. But
for any two 0 < a 6= b < p, the sequences aM, bM are different permutations of M .
2. Call a permutation π of M good if there exists a constant C such that π(M ) = CM .
(Note that not every permutation of M is good.)
3. Next, if we perform the first move (Each MOPper gives his or her red slip to the
MOPper whose number is written on his or her blue slip), then say that we fix blue
and move red. Similar terms exist for the second move.
We have the following claim:
Claim. At any moment, if we have two good permutations, then fixing any one of them and
moving the other will also result in a good permutation.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 145
 5. Modular Arithmetic Advanced

Proof. Let’s suppose the permutations are xM, yM . Suppose we fix yM and move xM .
Then, by definition, the number k at the ith spot in xM will move to jth spot, where j is
the number written at the ith spot in yM .
But clearly j ≡ i · y (mod p) and k = i · x (mod p). Hence the new number at the jth
spot is k = x · i = x · (jy −1 ) = j · (xy −1 ). Hence if set t = xy −1 , then k = tj is the new
number at the jth spot.
Hence, the new sequence obtained is tM , which is clearly good.
Also, as proved above, if we have the sequences xM, yM , then we can get to (x · y −1 )M
in the next move by fixing yM .

Claim. Let g be a primitive root modulo p. Then from the original sequences AM, BM , we
can get to BM, gM .

Proof. Set A = g k and B = g ` . Let gcd(k − 1, `) = d and write ` = d`0 and p − 1 = dz.
Then consider the following moves by fixing BM :
0
A = g k 7→ g k · g −l 7→ g k · g −2` · · · g k · g −dz`
0 `0 0 0
Here, since g −dz` = (g p−1 ) ≡ g ` , hence we have obtained the sequence (g k · g ` )M .
`0
By repeating this process, we can further reduce `0 to gcd(p−1,`0 )
and so on until we get
reach a number L such that gcd(L, p − 1) = 1.
Then again by fixing BM , we can get to g k · g −L , · · · g k · g −Ln ≡ g, where k − Ln ≡ 1
modulo p−1 (note that this number n exists since gcd(L, p−1) = 1). Hence we have reached
gM without disturbing B and we are done.
To finish it, we have the two sequences BM, gM . Now fix BM and perform moves to get
these p − 1 sequences: BM, (Bg −1 )M, (Bg −2 )M · · · (Bg −(p−1) )M .
Note that {B, Bg −1 , Bg −2 , · · · Bg −(p−1) } forms a complete residue class modulo p, hence
there will exist the sequence 1M in the sequences listed above, and we are done.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 146
5. Modular Arithmetic Advanced

5.9 Practice Problems

Problem 5.9.1. Find all n such that 3n + 1 is divisibly by n2 .

Problem 5.9.2. Show than any prime factor q of pp − 1 is ≡ 1 (mod p).

2p +1
Problem 5.9.3 (Fermat). Let p > 3 be a prime. Prove that any positive divisor of 3
is
of the form 2kp + 1.

Problem 5.9.4 (IMO Shortlist 2006 N2). For x ∈ (0, 1) let y ∈ (0, 1) be the number
whose n-th digit after the decimal point is the 2n -th digit after the decimal point of x. Show
that if x is rational then so is y.

Problem 5.9.5. Suppose that k ≥ 2 and n1 , n2 , · · · , nk ≥ 1 be natural numbers having the

property
n2 | 2n1 − 1, n3 | 2n2 − 1, · · · , nk | 2nk−1 − 1, n1 | 2nk − 1.
Show that n1 = n2 = · · · = nk = 1. Hints: 408 16

Problem 5.9.6 (Iran 3rd round 2017 Numbers theory final exam P1). Let x and y
be integers and let p be a prime number. Suppose that there exist relatively prime positive
integers m and n such that
xm ≡ y n (mod p)
Prove that there exists an unique integer z modulo p such that

x ≡ zn (mod p) and y ≡ z m (mod p).

Hints: 193

Problem 5.9.7 (China TST 2006). Find all positive integers a and n such that

(a + 1)n − an
n
is an integer. Hints: 415

Problem 5.9.8. Let g be a Fibonacci primitive root (mod p). i.e. g is a primitive root
(mod p) satisfying g 2 ≡ g + 1 (mod p). Prove that
1. g − 1 is also a primitive root (mod p).

2. Show that if p ≡ 3 (mod 4), then g − 2 is also a primitive root (mod p).
Hints: 219 354

Problem 5.9.9 (PUTNAM 1976 B6). Prove that if n is an integer such that σ(n) =
2n + 1, then n is the square of an odd integer. Hints: 106 86 388 278

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 147
 5. Modular Arithmetic Advanced

Problem 5.9.10 (China 2009). Find all prime numbers p, q such that pq | 5p + 5q . Hints:
163 476 176 88

Problem 5.9.11. Suppose that p > 3 is prime. Prove that the products of the primitive
roots of p between 1 and p − 1 is congruent to 1 modulo p. Hints: 50 461

Problem 5.9.12 (Bulgaria National Olympiad). Find all positive integers m and n such
that
m
n
22 + 1 22 + 1

is divisible by mn. Hints: 322

Problem 5.9.13. Determine all the pairs (p, n) of a prime number p and a positive integer
n for which
np + 1
∈ Z.
pn + 1
Hints: 141 396

Problem 5.9.14 (Iran MO 3rd round 2016 finals Number Theory P1). Let p and q
be prime numbers (q is odd). Prove that there exists an integer x such that

q | (x + 1)p − xp

if and only if
q≡1 (mod p).
Hints: 331 320 56 Sol: pg. 290

Problem 5.9.15 (China TST 4 2018 Day 2 Q4). Let p be a prime and k be a positive
integer. Set S contains all positive integers a satisfying 1 ≤ a ≤ p − 1, and there exists
positive integer x such that xk ≡ a (mod p).
Suppose that 3 ≤ |S| ≤ p − 2. Prove that the elements of S, when arranged in increasing
order, does not form an arithmetic progression. Hints: 257 179

Problem 5.9.16 (IMO Shortlist 1998 N5). Determine all positive integers n for which
there exists an integer m such that 2n − 1 is a divisor of m2 + 9. Hints: 102 368 143 183

Problem 5.9.17 (USA TST for EGMO 2019, Problem 3). Let n be a positive integer
such that the number
1k + 2k + · · · + nk
n
is an integer for any k ∈ {1, 2, . . . , 99}. Prove that n has no divisors between 2 and 100,
inclusive. Hints: 28 338 376 387 335 Sol: pg. 291

Problem 5.9.18 (IMO Shortlist 2014 N6). Let a1 < a2 < · · · < an be pairwise coprime
positive integers with a1 being prime and a1 ≥ n + 2. On the segment I = [0, a1 a2 · · · an ] of

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 148
5. Modular Arithmetic Advanced

the real line, mark all integers that are divisible by at least one of the numbers a1 , . . . , an .
These points split I into a number of smaller segments. Prove that the sum of the squares
of the lengths of these segments is divisible by a1 . Hints: 375 170 256 26 4 242 222 62 Sol: pg.
291

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 149
 5. Modular Arithmetic Advanced

z Identical Polynomials in Fp[X]

By Fp [X], we denote the set of polynomials with coefficients modulo p. The key idea here
is that X has no meaning of its own, i.e. it is just a way to write the polynomial. The
coefficients are the ones that interest us (just like in generating functions). We say that X
is just a ”formal variable” here.
So, if we are given two polynomials f, g, then we could have f = g in Fp , or we could
have f = g in Fp [X], and these are two different things. For example, f = g in Fp means
f (x) ≡ g(x) (mod p) for all values of x ∈ Fp . For instance, xp ≡ x (mod p) is true by
Fermat’s little Theorem, and so xp , x are the same in Fp .
In Fp [X], we need to look at the coefficients only. So x2 +5x+2, x2 +2x+2 and x2 −x−1
are all the same in F3 [X]. Also, xp 6= x in Fp [X] (since one has degree p and the other has
degree 1). So, f = g in Fp means they are equal value-wise (modulo p), but f = g in Fp [X]
means they are the same polynomials (coefficients modulo p).

Problem 5.9.19. Show that if f = g in Fp [X], then f = g in Fp holds too.

Comment 5.9.1: We often use f ≡ g to denote they are identical polynomials. So if

f, g are polynomials in Fp [X], then f ≡ g would mean the coefficients are same modulo
p.

Now that you have understood this, we can discuss the following:

Freshman’s Dream
We stated and proved Freshman’s dream in Example 2.12.3, where we said (a + b)p ≡ ap + bp
(mod p). There’s a more useful way of writing this:

(X + 1)p ≡ X p + 1 (mod p)

for any X (I think you can see where I am going with this). So we know that the polynomials
(X + 1)p and X p + 1 are equal in Fp . However, this is stupid, since Fermat’s Little Theorem
gives (X + 1)p ≡ X + 1 ≡ X p + 1 (mod p) anyway. So why is this any useful?
Here’s the reason. Go back and take a look at the proof we had given while discussing
this originally in Example 2.12.3. If we write the proof here again, then it’s
     
p p p p−1 p p−1 p
(X + 1) = X + X + X + ··· + X + 1 ≡ X p + 1 (mod p).
1 2 p−1

The fact used here in the proof treats X as a formal variable and doesn’t need it’s value, and
we only worked with coefficients! What this means is the stronger fact that (X + 1)p and
X p + 1 are equal polynomials in Fp [X] (why is this stronger?). So, we have the following:

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 150
5. Modular Arithmetic Advanced

Theorem 5.9.1 (Freshman’s Dream). For any prime p, we have

(X + 1)p ≡ X p + 1

in Fp [X]. We can generalize this to

i i
(X + 1)p ≡ X p + 1

in Fp [X].

This is very useful, much more useful than the earlier Freshman’s dream (which followed
from Fermat’s Little Theorem directly). Let’s see an application, which we had promised
earlier:

Proof of Lucas’s Theorem

Before we skip to the general proof, it is better to work with an example first. Suppose
n = 66 and m = 13. Also, let p = 5. Write n = 231(3) and m = 23(3) . The key idea again is
to use generating functions since it covers all the coefficients at once. So
2 1 0
(X + 1)66 = (X + 1)2·5 +3·5 +1·5
 2  3  1
52 51 50
= (X + 1) (X + 1) (X + 1)
 2 2  1 3  0 1
5 5 5
≡ X +1 X +1 X +1 ,

where the last equality is in F5 [X]. Further, this equals

! ! ! ! ! ! ! ! ! ! ! !
2 2 2 2 2 0·52 3 1 3 1 3 1 3 0·51 1 0 1 0·50
= X 2·5 + X 1·5 + X X 3·5 + X 2·5 + X 1·5 + X X 1·5 + X .
0 1 2 0 1 2 3 0 1

b
We want the coefficient of X 13 here (why?). Note that each exponent is of the form X a·5 .
So, on multiplying out all the brackets, the power of X would be something of the form
a1 5b1 + a2 5b2 + . . . , so a base 5 number. Since 13 = 0 · 52 + 2 · 51 + 3 · 50 , hence we have to
choose the right terms from each bracket. Doing this, we would get
     
66 2 3 1
≡ (mod 5)
13 2 1 3

(note that we chose 13 from the third bracket since there weren’t enough terms). So, we

proved Lucas’s theorem for this case. Let’s look at the general case now.
Write
n = nk pk + nk−1 pk−1 + · · · + n1 p + n0
and
m = mk pk + mk−1 pk−1 + · · · + m1 p + m0

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 151
 5. Modular Arithmetic Advanced

as the base p expansions of m and n respectively. Then (we work in Fp [X])

X n
X m = (X + 1)n
0≤m≤n
m
k k−1 +···+n
= (X + 1)nk p +nk−1 p 0

k 
i ni
Y 
= (X + 1)p
i=0

Now, we use Freshman’s dream on each bracket to get

k  ni
i
Y
≡ Xp + 1
i=0
kni  
YX ni i
= X p mi .
i=0 m =0
mi
i

At this point, note that we can change the upper index of the sum to (p − 1) since xy = 0 if

y > x (why must we do this? Look back at our proof for the n = 66 example and point out
where we did this). Then, to obtain the coefficient of X m , we collect the right terms from
each sum to multiply so that we get m = mk pk + mk−1 pk−1 + · · · + m1 p + m0 (we can do this
since the base p representation of m is unique). So we write

k Xp−1  
Y ni i
= X p mi .
i=0 mi =0
mi
n Y k  
X ni
= X m.
m=1 i=0
m i

And so, by comparing the coefficients of X m on both the sides, we are done!
We can nicely summarize this as:

X n k k−1
X m = (X + 1)n = (X + 1)nk p +nk−1 p +···+n0
0≤m≤n
m
k  ni k  ni
pi pi
Y Y
= (X + 1) ≡ X +1
i=0 i=0
k X ni   k Xp−1  
Y ni pi mi
Y ni i
= X = X p mi .
i=0 mi =0
mi i=0 mi =0
mi
n Y k  
X ni
= X m.
m=1 i=0
m i

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 152
5. Modular Arithmetic Advanced

Lagrange’s Theorem
Define the polynomials f, g ∈ Fp [X] by
f (x) = xp − x, g(x) = x(x − 1)(x − 2) . . . (x − (p − 1)).
We saw in Example 2.12.4 that f (x) and g(x) are equal in Fp , i.e. always give the same
value modulo p. The question we promised to answer was if they are equal as polynomials
too, i.e., equal in Fp [X].
Turns out the answer is yes, and it goes by the name Lagrange’s Theorem.
Theorem 5.9.2 (Lagrange’s Theorem). Let p be a prime. Then the polynomials
xp − x ≡ x(x − 1) . . . (x − (p − 1))
holds in Fp [X].
The sharp-eyed reader might say that this follows by the factor theorem; i.e., f (x) has
the roots 0, 1, 2, . . . , p − 1 in Fp and is monic, so f (x) = x(x − 1) . . . (x − (p − 1)) in Fp [X].
This is a perfect argument, however as a technical issue: we know that the factor theorem
holds in C[X]. Does it also hold in Fp [X]?
The answer is yes, and it depends on two key properties of Fp [X] which distinguishes it
from other sets that don’t have factor theorem:
1. If f g = 0 for two polynomials f, g ∈ Fp [X], then one of f, g must be 0.
2. Euclid’s Division Algorithm holds in Fp [X] (see Comment 7.1.3.)
A number a is called a zero divisor if there is a non-zero number x such that ax = 0.
Hence, the first property says that Fp [X] has no zero divisors. In fact, for this to hold, the
hypothesis that p is a prime is essential. For instance, 2 · 5 ≡ 0 (mod 10) even though both
are non-zero in Z/10Z.
The second property says that if f, g ∈ Fp [X] are two polynomials, then there exist
polynomials q, r ∈ Fp [X] such that
f (x) = g(x)q(x) + r(x), deg r < deg q.
We need to take some care with deg here. For instance, deg(5x2 + 2x + 1) = 1 in F5 [X] since
5x2 is just 0 in F5 [X]. However, deg(5x2 + 2x + 1) = 2 in F2 [X].
Question 5.9.1. Convince yourself that Euclid’s algorithm holds in Fp [X]. Take a few ex-
amples, if needed (hint: polynomial division, see Comment 7.1.3.)
Now, we can prove the factor theorem:
Theorem 5.9.3 (Factor Theorem). Let f ∈ Fp [X] have n distinct roots x1 , . . . , xm , where
deg f = n. Then there exists a polynomial g(x) such that deg g = n − m and
f (x) = (x − x1 ) . . . (x − xm )g(x)
holds identically in Fp [X].

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 153
 5. Modular Arithmetic Advanced

Proof. Say f is non-constant (else there is nothing to prove). Write

f (x) = (x − x1 )q(x) + r(x).

Since deg r < deg(x − x1 ), hence r must be a constant. Further, f (x1 ) = 0 implies r = 0
in Fp . If n = 1, then we are done. Otherwise there is a second root x2 . Then f (x2 ) = 0
implies (x2 − x1 )q(x2 ) = 0 in Fp [X]. We have seen earlier that this means either x2 − x1 = 0,
or q(x2 ) = 0. The first one is not possible (since we assume roots to be distinct.) Hence
q(x2 ) = 0. Now since deg q < deg f, hence we can finish by induction now.

Question 5.9.2. In Z/6Z[X], consider x2 − 5x. It has the roots x = 0, 2, 3, 5. However,

x2 − 5x 6= (x − 0)(x − 2)(x − 3)(x − 5) for degree reasons. Why do we face this issue here?

Hence, we have the following corollary (by looking at the degree)

Corollary 5.9.1. Let f ∈ Fp [X] have n distinct roots x1 , . . . , xn , where deg f = n. Let c 6= 0
be the leading coefficient of f. Then

f (x) = c(x − x1 ) . . . (x − xn )

holds identically in Fp [X].

This corollary proves Lagrange’s theorem. Lagrange’s theorem has many amazing appli-
cations. For instance:

Problem 5.9.20. Prove Wilson’s Theorem by comparing coefficients.

Problem 5.9.21. Using Newton’s sum identities, prove the result in Example 5.5.1.

Roots of Polynomials in Fp [X]

Now that we are discussing polynomials and their roots, let’s talk about them properly. A
natural question is how many roots does a polynomial have mod m? If deg f = d, then does
it have d roots (like polynomials in C[X])? Turns out the answer isn’t very simple. Consider
the following two polynomials:

f (x) = xp − x + 1 ∈ Fp [X], g(x) = x2 − 5x ∈ Z/6Z[X], h(x) = 5x2 + 10x ∈ F5 [X].

In the first example, we see that modulo p, the polynomial has 0 roots (why?) despite
having degree p. In the second example (which we have seen before), we find 4 roots modulo
6, which is more than the degree. In the last example, we see that every number is a root of
the polynomial. So is there any good result?
The answer is yes, but only when m is a prime. We have the following analogue of
the Fundamental Theorem of Algebra (before presenting it, recall that if deg f = n for a
polynomial f ∈ Fp [X], then the coefficient of xn is not 0 in Fp , i.e. not divisible by p. So the
degree of h(x) above is not defined).

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 154
5. Modular Arithmetic Advanced

Theorem 5.9.4 (Lagrange’s Theorem). Let f ∈ Fp [X] be a polynomial with deg f = n.

Then, f has at most n distinct roots in Fp .

One proof directly follows from the factor theorem above. We present a second proof:
Proof. We prove this by induction on deg f. The base case is clear, so suppose we have the
result till some deg f = k − 1. Now consider a polynomial f of degree k, and suppose it has
more than k roots mod p, say x1 , . . . , x` with ` > k. Let c 6= 0 be the leading coefficient of
f. Then define
g(x) = f (x) − c(x − x1 ) . . . (x − xk ).
Now if deg g is not identically 0 in Fp [X], then deg g < k and hence it has at most deg g < k
roots by the induction hypothesis. However, x1 , . . . , xk are all its roots, and we have a
contradiction.
So it must be identically zero in Fp [X]. However, this is impossible as deg f > k =
deg (c(x − x1 ) . . . (x − xk )) , and so we are done.
This gives the following important corollary:

Corollary 5.9.2. Let f ∈ Fp [X] be a polynomial with more than deg f roots. Then f is
identically zero in Fp [X].

When does a polynomial have exactly deg f roots? The answer to this question is in the
following theorem:

Theorem 5.9.5. Let f ∈ Fp [X] be a polynomial. Then f has exactly deg f roots if and only
if f (x) divides xp − x.

Proof. Suppose f has deg f roots. Write xp − x = f (x)q(x) + r(x) with deg r < deg f. Now
since each root of f is also a root of xp − x, we find that r(x) = 0 for deg f values. However,
since deg f > deg r, hence by Corollary 5.9.2 we find r ≡ 0, and so f (x) | xp − x.
Conversely, suppose f (x) divides xp − x. Write xp − x = f (x)q(x) + pr(x) in Z[X]. Here,
deg f = n and deg g = p − n, and so by Theorem 5.9.4, f has at most n roots, and g has at
most p − n roots, implying that f (x)g(x) has at most n + (p − n) = p roots. However, we
see that for all p numbers in Fp , xp − x vanishes. Hence, f (x)g(x) = 0 for all x ∈ Fp . Thus,
equality holds above, showing that f has n roots.

c
Aditya Khurmi 2020. All rights reserved. (Published on 11/2020) 155