Inverses Modulo $p$

Author

Patrik Bak

1Introduction

We assume familiarity with congruences modulo a prime $p$ . In this handout we build a small theory of multiplicative inverses modulo $p$ and use it to solve problems.

2Theory

Throughout, $p$ denotes a prime.

2.1Recap

We freely use the following standard facts about congruences modulo $p$ :

Congruences may be added, subtracted, and multiplied: if $a \equiv b$ and $c \equiv d \pmod{p}$ , then $a \pm c \equiv b \pm d$ and $ac \equiv bd \pmod{p}$ .
Cancellation: if $a \not\equiv 0 \pmod{p}$ and $ax \equiv ay \pmod{p}$ , then $x \equiv y \pmod{p}$ .
For any $a \not\equiv 0 \pmod{p}$ , the residues $a, 2a, \ldots, (p-1)a$ are a permutation of $1, 2, \ldots, p-1$ modulo $p$ .
Fermat's Little Theorem: for any $a \not\equiv 0 \pmod{p}$ , we have $a^{p-1} \equiv 1 \pmod{p}$ .
Order: the order of $a \not\equiv 0 \pmod{p}$ is the smallest positive integer $d$ with $a^d \equiv 1 \pmod{p}$ . It divides $p - 1$ .
Primitive root: there exists $g \not\equiv 0 \pmod{p}$ of order $p - 1$ . Every $a \not\equiv 0 \pmod{p}$ equals $g^k$ for some $k$ .

2.2Inverses

Theorem 1

Existence and Uniqueness of Inverse

Let $a \not\equiv 0 \pmod{p}$ . Then there exists a unique residue $a^{-1} \pmod{p}$ with

a \cdot a^{-1} \equiv 1 \pmod{p}.

We write $\frac{1}{a}$ for $a^{-1}$ , and $\frac{b}{a}$ for $b \cdot a^{-1}$ .

Theorem 2

Inverses Add Like Fractions

Let $b, d \not\equiv 0 \pmod{p}$ . Then for any $a, c$ , we have

\frac{a}{b} + \frac{c}{d} \equiv a \cdot b^{-1} + c \cdot d^{-1} \equiv (ad + bc) \cdot (bd)^{-1} \equiv \frac{ad + bc}{bd} \pmod{p},

just like normal fractions.

Theorem 3

Inverses Multiply Like Fractions

Let $b, d \not\equiv 0 \pmod{p}$ . Then for any $a, c$ , we have

\frac{a}{b} \cdot \frac{c}{d} \equiv (a \cdot b^{-1}) \cdot (c \cdot d^{-1}) \equiv (ac) \cdot (bd)^{-1} \equiv \frac{ac}{bd} \pmod{p},

just like normal fractions.

3Problems

The problems below all benefit from the theory above — working with fractions modulo $p$ as if they were ordinary numbers. They are ordered roughly by difficulty.

Problem 1

Wilson

Let $p$ be a prime. Prove that

(p-1)! \equiv -1 \pmod{p}.

1Hint

In the product $1 \cdot 2 \cdots (p-1)$ , try to pair factors with their inverse. Which numbers do not have a pair?

2Hint

The numbers without the pair are those satisfying $k \equiv 1/k \mod p$ . Find them all.

Problem 2

Let $p$ be a prime. Prove that there exist integers $a, b$ , neither divisible by $p$ , with $p \mid a^2 + b^2$ if and only if $p = 2$ or $p \equiv 1 \pmod{4}$ .

1Hint

The condition $p \mid a^2 + b^2$ rewrites as $(a/b)^2 \equiv -1 \pmod{p}$ . So the question becomes: for which primes is $-1$ a square modulo $p$ ?

2Hint

For one direction, raise the relation $(a/b)^2 \equiv -1$ to the $(p-1)/2$ -th power. The left side becomes $(a/b)^{p-1}$ .

3Hint

Apply Fermat's Little Theorem to the left side. What does the resulting equation force on $p \mod 4$ ?

4Hint

For the converse with $p \equiv 1 \pmod{4}$ , you need an explicit square root of $-1$ modulo $p$ . A natural source: Wilson's theorem, $(p-1)! \equiv -1 \pmod{p}$ .

5Hint

In the product $(p-1)!$ , pair $k$ with $p - k \equiv -k$ . What does the result look like for $p \equiv 1 \pmod{4}$ ?

Problem 3

Let $p \equiv 2 \pmod{3}$ be a prime. Show that if $p \mid a^2 + ab + b^2$ , then $p \mid a$ and $p \mid b$ .

1Hint

Note that $a^3 - b^3 = (a - b)(a^2 + ab + b^2)$ , so $p \mid a^3 - b^3$ . Assume for contradiction that $p \nmid b$ . This is similar to the previous problem.

2Hint

Raise to the $(p-2)/3$ -th power, which is a positive integer since $p \equiv 2 \pmod{3}$ . The left side becomes $(a/b)^{p-2}$ .

3Hint

Multiply both sides by $a/b$ to get $(a/b)^{p-1} \equiv a/b \pmod{p}$ . Apply Fermat's Little Theorem to conclude $a \equiv b \pmod{p}$ . Substitute this back.

Problem 4

Let $p$ be a prime and let $0 \leq k \leq p-1$ be an integer. Prove that

\binom{p-1}{k} \equiv (-1)^k \pmod{p}.

1Hint

Expand the binomial coefficient as $\binom{p-1}{k} = \frac{(p-1)(p-2) \cdots (p-k)}{k!}$ .

2Hint

Reduce each factor in the numerator modulo $p$ : $p - j \equiv -j \pmod{p}$ . Aren't we left with something familiar?

Problem 5

Let $p \geq 3$ be a prime. Show that if

\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p-1} = \frac{m}{n},

then $p \mid m$ .

1Hint

Looking at this modulo $p$ , we have the sum of inverses of all possible non-zero values mod $p$ .

2Hint

Realize that this sum is actually the sum of all values from $1$ to $p-1$ , not necessarily in this order.

Problem 6

IMO 2005

Determine all positive integers $n$ that are coprime to every term of the sequence

a_m = 2^m + 3^m + 6^m - 1, \quad m \geq 1.

1Hint

Show that for every prime $p$ , some $a_m$ is divisible by $p$ . Then the only valid $n$ is $n = 1$ .

2Hint

Small primes are easy: $a_1 = 10$ handles $p = 2, 5$ and $a_2 = 48$ handles $p = 3$ . Focus on $p \geq 5$ and try to choose $m$ depending on $p$ so that the four terms collapse.

3Hint

For $p \geq 5$ , take $m = p - 2$ . Then $2^m \equiv 1/2$ , $3^m \equiv 1/3$ , $6^m \equiv 1/6 \pmod{p}$ . Compute $a_{p-2} \pmod{p}$ .

Problem 7

Poland

Let $p > 3$ be a prime with $p \equiv 2 \pmod{3}$ , and let $a_k = k^2 + k + 1$ for $k = 1, 2, \ldots, p-1$ . Prove that

a_1 a_2 \cdots a_{p-1} \equiv 3 \pmod{p}.

1Hint

For $k \neq 1$ , factor $k^2 + k + 1 = \frac{k^3 - 1}{k - 1}$ . Isolate the $k = 1$ term, which contributes $3$ .

2Hint

The product becomes $3 \cdot \frac{\prod_{k=2}^{p-1}(k^3 - 1)}{(p-2)!}$ . We need to calculate the numerator and denominator mod $p$ separately.

3Hint

It would be great if the product of all the numbers $k^3-1$ was actually something we could calculate.

Problem 8

Singapore 2012

Let $p$ be an odd prime. Prove that

\sum_{i=1}^{(p-1)/2} i^{p-2} \equiv \frac{2 - 2^p}{p} \pmod{p}.

1Hint

Since $i^{p-2} \equiv 1/i \pmod{p}$ , the left-hand side is $\sum_{i=1}^{(p-1)/2} 1/i$ . Now work on the right-hand side to get the hint.

2Hint

Expand $2^p = (1+1)^p = \sum_{k=0}^{p} \binom{p}{k}$ , so $\frac{2^p - 2}{p} = \frac{1}{p} \sum_{k=1}^{p-1} \binom{p}{k}$ .

3Hint

Use $\binom{p}{k} = \frac{p}{k} \binom{p-1}{k-1}$ to rewrite each summand: $\frac{2^p - 2}{p} = \sum_{k=1}^{p-1} \frac{\binom{p-1}{k-1}}{k}$ .

4Hint

Apply $\binom{p-1}{k-1} \equiv (-1)^{k-1} \pmod{p}$ from a previous problem to simplify.

5Hint

The right-hand side reduces to $-\sum_{k=1}^{p-1} (-1)^{k-1}/k \pmod{p}$ . Split this into even and odd $k$ , and use $\sum_{k=1}^{p-1} 1/k \equiv 0 \pmod{p}$ from a previous problem.

Problem 9

Show that for every prime $p$ ,

\binom{2p}{p} \equiv 2 \pmod{p^2}.

1Hint

Write $\binom{2p}{p} = \frac{(2p)(2p-1)\cdots(p+1)}{p!}$ . Pull out the factor $2p$ in the numerator and the $p$ in $p! = p \cdot (p-1)!$ to get $\binom{2p}{p} = \frac{2 \prod_{k=1}^{p-1}(p+k)}{(p-1)!}$ .

2Hint

Factor each numerator term as $p + k = k\bigl(1 + \frac{p}{k}\bigr)$ , so $\prod_{k=1}^{p-1}(p+k) = (p-1)! \cdot \prod_{k=1}^{p-1}\bigl(1 + \frac{p}{k}\bigr)$ .

3Hint

Expand $\prod\bigl(1 + \frac{p}{k}\bigr)$ modulo $p^2$ : only the constant and linear-in- $p$ terms survive, giving $1 + p \sum_{k=1}^{p-1} 1/k$ .

4Hint

By P4, $\sum_{k=1}^{p-1} 1/k \equiv 0 \pmod{p}$ , so $p \sum 1/k \equiv 0 \pmod{p^2}$ .

Problem 10

Let $p \geq 5$ be a prime and let $e$ be a positive integer with $(p-1) \nmid e$ . Show that if

\frac{1}{1^e} + \frac{1}{2^e} + \frac{1}{3^e} + \cdots + \frac{1}{(p-1)^e} = \frac{m}{n},

then $p \mid m$ .

1Hint

The claim is $\sum_{k=1}^{p-1} \frac{1}{k^e} \equiv 0 \pmod{p}$ . The trick is to look for an $a$ such that multiplying every $k$ by $a$ shuffles the terms but rescales the whole sum.

2Hint

Use the assumption $(p-1) \nmid e$ to find $a$ with $a^e \not\equiv 1 \pmod{p}$ . The trick is to consider a primitive root.

Problem 11

Wolstenholme

Let $p \geq 5$ be a prime. Show that if

\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p-1} = \frac{m}{n},

then $p^2 \mid m$ .

1Hint

Pair $k$ with $p - k$ .

2Hint

This gives $\sum_{k=1}^{p-1} 1/k = p \sum_{k=1}^{(p-1)/2} 1/(k(p-k))$ . We need the right-hand factor to be divisible by $p$ .

3Hint

Modulo $p$ , $1/(k(p-k)) \equiv -1/k^2$ . So it suffices that $\sum_{k=1}^{(p-1)/2} 1/k^2 \equiv 0 \pmod{p}$ .

4Hint

Note $(p-k)^2 \equiv k^2 \pmod{p}$ , so $\sum_{k=1}^{p-1} 1/k^2 = 2 \sum_{k=1}^{(p-1)/2} 1/k^2$ . Can we now use a previous problem?

Comments

Inverses Modulo $p$

Author

Patrik Bak

1Introduction

We assume familiarity with congruences modulo a prime $p$ . In this handout we build a small theory of multiplicative inverses modulo $p$ and use it to solve problems.

2Theory

Throughout, $p$ denotes a prime.

2.1Recap

We freely use the following standard facts about congruences modulo $p$ :

Congruences may be added, subtracted, and multiplied: if $a \equiv b$ and $c \equiv d \pmod{p}$ , then $a \pm c \equiv b \pm d$ and $ac \equiv bd \pmod{p}$ .
Cancellation: if $a \not\equiv 0 \pmod{p}$ and $ax \equiv ay \pmod{p}$ , then $x \equiv y \pmod{p}$ .
For any $a \not\equiv 0 \pmod{p}$ , the residues $a, 2a, \ldots, (p-1)a$ are a permutation of $1, 2, \ldots, p-1$ modulo $p$ .
Fermat's Little Theorem: for any $a \not\equiv 0 \pmod{p}$ , we have $a^{p-1} \equiv 1 \pmod{p}$ .
Order: the order of $a \not\equiv 0 \pmod{p}$ is the smallest positive integer $d$ with $a^d \equiv 1 \pmod{p}$ . It divides $p - 1$ .
Primitive root: there exists $g \not\equiv 0 \pmod{p}$ of order $p - 1$ . Every $a \not\equiv 0 \pmod{p}$ equals $g^k$ for some $k$ .

2.2Inverses

Theorem 1

Existence and Uniqueness of Inverse

Let $a \not\equiv 0 \pmod{p}$ . Then there exists a unique residue $a^{-1} \pmod{p}$ with

a \cdot a^{-1} \equiv 1 \pmod{p}.

We write $\frac{1}{a}$ for $a^{-1}$ , and $\frac{b}{a}$ for $b \cdot a^{-1}$ .

Theorem 2

Inverses Add Like Fractions

Let $b, d \not\equiv 0 \pmod{p}$ . Then for any $a, c$ , we have

\frac{a}{b} + \frac{c}{d} \equiv a \cdot b^{-1} + c \cdot d^{-1} \equiv (ad + bc) \cdot (bd)^{-1} \equiv \frac{ad + bc}{bd} \pmod{p},

just like normal fractions.

Theorem 3

Inverses Multiply Like Fractions

Let $b, d \not\equiv 0 \pmod{p}$ . Then for any $a, c$ , we have

\frac{a}{b} \cdot \frac{c}{d} \equiv (a \cdot b^{-1}) \cdot (c \cdot d^{-1}) \equiv (ac) \cdot (bd)^{-1} \equiv \frac{ac}{bd} \pmod{p},

just like normal fractions.

3Problems

The problems below all benefit from the theory above — working with fractions modulo $p$ as if they were ordinary numbers. They are ordered roughly by difficulty.

Problem 1

Wilson

Let $p$ be a prime. Prove that

(p-1)! \equiv -1 \pmod{p}.

1Hint

In the product $1 \cdot 2 \cdots (p-1)$ , try to pair factors with their inverse. Which numbers do not have a pair?

2Hint

The numbers without the pair are those satisfying $k \equiv 1/k \mod p$ . Find them all.

Problem 2

Let $p$ be a prime. Prove that there exist integers $a, b$ , neither divisible by $p$ , with $p \mid a^2 + b^2$ if and only if $p = 2$ or $p \equiv 1 \pmod{4}$ .

1Hint

The condition $p \mid a^2 + b^2$ rewrites as $(a/b)^2 \equiv -1 \pmod{p}$ . So the question becomes: for which primes is $-1$ a square modulo $p$ ?

2Hint

For one direction, raise the relation $(a/b)^2 \equiv -1$ to the $(p-1)/2$ -th power. The left side becomes $(a/b)^{p-1}$ .

3Hint

Apply Fermat's Little Theorem to the left side. What does the resulting equation force on $p \mod 4$ ?

4Hint

For the converse with $p \equiv 1 \pmod{4}$ , you need an explicit square root of $-1$ modulo $p$ . A natural source: Wilson's theorem, $(p-1)! \equiv -1 \pmod{p}$ .

5Hint

In the product $(p-1)!$ , pair $k$ with $p - k \equiv -k$ . What does the result look like for $p \equiv 1 \pmod{4}$ ?

Problem 3

Let $p \equiv 2 \pmod{3}$ be a prime. Show that if $p \mid a^2 + ab + b^2$ , then $p \mid a$ and $p \mid b$ .

1Hint

Note that $a^3 - b^3 = (a - b)(a^2 + ab + b^2)$ , so $p \mid a^3 - b^3$ . Assume for contradiction that $p \nmid b$ . This is similar to the previous problem.

2Hint

Raise to the $(p-2)/3$ -th power, which is a positive integer since $p \equiv 2 \pmod{3}$ . The left side becomes $(a/b)^{p-2}$ .

3Hint

Multiply both sides by $a/b$ to get $(a/b)^{p-1} \equiv a/b \pmod{p}$ . Apply Fermat's Little Theorem to conclude $a \equiv b \pmod{p}$ . Substitute this back.

Problem 4

Let $p$ be a prime and let $0 \leq k \leq p-1$ be an integer. Prove that

\binom{p-1}{k} \equiv (-1)^k \pmod{p}.

1Hint

Expand the binomial coefficient as $\binom{p-1}{k} = \frac{(p-1)(p-2) \cdots (p-k)}{k!}$ .

2Hint

Reduce each factor in the numerator modulo $p$ : $p - j \equiv -j \pmod{p}$ . Aren't we left with something familiar?

Problem 5

Let $p \geq 3$ be a prime. Show that if

\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p-1} = \frac{m}{n},

then $p \mid m$ .

1Hint

Looking at this modulo $p$ , we have the sum of inverses of all possible non-zero values mod $p$ .

2Hint

Realize that this sum is actually the sum of all values from $1$ to $p-1$ , not necessarily in this order.

Problem 6

IMO 2005

Determine all positive integers $n$ that are coprime to every term of the sequence

a_m = 2^m + 3^m + 6^m - 1, \quad m \geq 1.

1Hint

Show that for every prime $p$ , some $a_m$ is divisible by $p$ . Then the only valid $n$ is $n = 1$ .

2Hint

Small primes are easy: $a_1 = 10$ handles $p = 2, 5$ and $a_2 = 48$ handles $p = 3$ . Focus on $p \geq 5$ and try to choose $m$ depending on $p$ so that the four terms collapse.

3Hint

For $p \geq 5$ , take $m = p - 2$ . Then $2^m \equiv 1/2$ , $3^m \equiv 1/3$ , $6^m \equiv 1/6 \pmod{p}$ . Compute $a_{p-2} \pmod{p}$ .

Problem 7

Poland

Let $p > 3$ be a prime with $p \equiv 2 \pmod{3}$ , and let $a_k = k^2 + k + 1$ for $k = 1, 2, \ldots, p-1$ . Prove that

a_1 a_2 \cdots a_{p-1} \equiv 3 \pmod{p}.

1Hint

For $k \neq 1$ , factor $k^2 + k + 1 = \frac{k^3 - 1}{k - 1}$ . Isolate the $k = 1$ term, which contributes $3$ .

2Hint

The product becomes $3 \cdot \frac{\prod_{k=2}^{p-1}(k^3 - 1)}{(p-2)!}$ . We need to calculate the numerator and denominator mod $p$ separately.

3Hint

It would be great if the product of all the numbers $k^3-1$ was actually something we could calculate.

Problem 8

Singapore 2012

Let $p$ be an odd prime. Prove that

\sum_{i=1}^{(p-1)/2} i^{p-2} \equiv \frac{2 - 2^p}{p} \pmod{p}.

1Hint

Since $i^{p-2} \equiv 1/i \pmod{p}$ , the left-hand side is $\sum_{i=1}^{(p-1)/2} 1/i$ . Now work on the right-hand side to get the hint.

2Hint

Expand $2^p = (1+1)^p = \sum_{k=0}^{p} \binom{p}{k}$ , so $\frac{2^p - 2}{p} = \frac{1}{p} \sum_{k=1}^{p-1} \binom{p}{k}$ .

3Hint

Use $\binom{p}{k} = \frac{p}{k} \binom{p-1}{k-1}$ to rewrite each summand: $\frac{2^p - 2}{p} = \sum_{k=1}^{p-1} \frac{\binom{p-1}{k-1}}{k}$ .

4Hint

Apply $\binom{p-1}{k-1} \equiv (-1)^{k-1} \pmod{p}$ from a previous problem to simplify.

5Hint

The right-hand side reduces to $-\sum_{k=1}^{p-1} (-1)^{k-1}/k \pmod{p}$ . Split this into even and odd $k$ , and use $\sum_{k=1}^{p-1} 1/k \equiv 0 \pmod{p}$ from a previous problem.

Problem 9

Show that for every prime $p$ ,

\binom{2p}{p} \equiv 2 \pmod{p^2}.

1Hint

2Hint

Factor each numerator term as $p + k = k\bigl(1 + \frac{p}{k}\bigr)$ , so $\prod_{k=1}^{p-1}(p+k) = (p-1)! \cdot \prod_{k=1}^{p-1}\bigl(1 + \frac{p}{k}\bigr)$ .

3Hint

Expand $\prod\bigl(1 + \frac{p}{k}\bigr)$ modulo $p^2$ : only the constant and linear-in- $p$ terms survive, giving $1 + p \sum_{k=1}^{p-1} 1/k$ .

4Hint

By P4, $\sum_{k=1}^{p-1} 1/k \equiv 0 \pmod{p}$ , so $p \sum 1/k \equiv 0 \pmod{p^2}$ .

Problem 10

Let $p \geq 5$ be a prime and let $e$ be a positive integer with $(p-1) \nmid e$ . Show that if

\frac{1}{1^e} + \frac{1}{2^e} + \frac{1}{3^e} + \cdots + \frac{1}{(p-1)^e} = \frac{m}{n},

then $p \mid m$ .

1Hint

The claim is $\sum_{k=1}^{p-1} \frac{1}{k^e} \equiv 0 \pmod{p}$ . The trick is to look for an $a$ such that multiplying every $k$ by $a$ shuffles the terms but rescales the whole sum.

2Hint

Use the assumption $(p-1) \nmid e$ to find $a$ with $a^e \not\equiv 1 \pmod{p}$ . The trick is to consider a primitive root.

Problem 11

Wolstenholme

Let $p \geq 5$ be a prime. Show that if

\frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{p-1} = \frac{m}{n},

then $p^2 \mid m$ .

1Hint

Pair $k$ with $p - k$ .

2Hint

This gives $\sum_{k=1}^{p-1} 1/k = p \sum_{k=1}^{(p-1)/2} 1/(k(p-k))$ . We need the right-hand factor to be divisible by $p$ .

3Hint

Modulo $p$ , $1/(k(p-k)) \equiv -1/k^2$ . So it suffices that $\sum_{k=1}^{(p-1)/2} 1/k^2 \equiv 0 \pmod{p}$ .

4Hint

Note $(p-k)^2 \equiv k^2 \pmod{p}$ , so $\sum_{k=1}^{p-1} 1/k^2 = 2 \sum_{k=1}^{(p-1)/2} 1/k^2$ . Can we now use a previous problem?