Elementary Number Theory — Reference Exercises

This post collects 30 elementary number theory exercises, covering congruences, quadratic residues, primitive roots, Diophantine equations, cyclotomic polynomials, Dirichlet density, and more.

Problem 1. Let $p$ be an odd prime. For each integer $1 \le i \le p-1$, let $a_i$ be a positive integer satisfying $i a_i \equiv 1 \pmod{p}$.

1. Prove that $\displaystyle\sum_{i=1}^{p-1} a_i \equiv 0 \pmod{p}$.
2. Let $S$ be the sum of the first $p-1$ positive integers: $S = 1 + 2 + \cdots + (p-1)$. Prove that for all primes $p > 3$, $(p-1)! \not\equiv -1 \pmod{S}$.

Problem 2. Let $p$ and $q$ be odd primes. Suppose $q$ divides the Mersenne number $M_p = 2^p - 1$. Prove that $q > p$.

Problem 3. Consider the quadratic congruence $x^2 \equiv a \pmod{p^2}$, where $p$ is an odd prime and $\gcd(a, p) = 1$.

1. Let $x_0$ be a solution to $x^2 \equiv a \pmod{p}$. Prove that there exists a unique integer $t$ modulo $p$ such that $x_1 = x_0 + tp$ is a solution to the congruence modulo $p^2$.
2. Prove that for every positive integer $k$, the equation $x^2 \equiv a \pmod{p^k}$ has a solution.

Problem 4. Consider the Diophantine equation $x^3 + 2y^3 = 7z^3$.

1. Prove that the cube of any integer is congruent to $0, 1$, or $-1$ modulo $7$.
2. Prove that $x^3 + 2y^3 = 7z^3$ has only the trivial solution $x = y = z = 0$.

Problem 5. Consider the equation $x^2 - 3y^2 = 1$.

1. Find the smallest positive integer solution $(x_1, y_1)$.
2. Define the sequence of solutions by $(x_n + y_n\sqrt{3}) = (x_1 + y_1\sqrt{3})^n$. Prove that $x_n$ is always odd.
3. Prove that $\{(x_n, y_n) \mid n \in \mathbb{Z}_{>0}\}$ is the set of all positive integer solutions.

Problem 6. Let $\mu(n)$ denote the Möbius function, and let $\Phi_n(x)$ denote the $n$-th cyclotomic polynomial. We have $x^n - 1 = \prod_{d \mid n} \Phi_d(x)$.

1. Express $\Phi_n(x)$ as a rational function of terms of the form $x^d - 1$.
2. Let $p$ be a prime. Prove that $\Phi_{p^k}(x) = \Phi_p(x^{p^{k-1}})$.

Problem 7. Find the remainder of $7^{7^7}$ upon division by $100$.

Problem 8. Let $a \in \mathbb{Z}$ be coprime to $10$. Prove that $a^{20} \equiv 1 \pmod{100}$.

Problem 9. Let $p > 3$ be a prime. Suppose there exists an integer $a$ whose multiplicative order modulo $p$ is $3$.

1. Prove that $p \equiv 1 \pmod{3}$.
2. Prove that $a^2 + a + 1 \equiv 0 \pmod{p}$.
3. Determine the multiplicative order of $a + 1$ modulo $p$, and prove your answer.

Problem 10. Let $p$ be an odd prime with $p \nmid 2026$. Determine the condition on $p$ for the congruence $x^2 \equiv 2026 \pmod{p}$ to have a solution.

Problem 11. Solve the Diophantine equation $x^2 + y^2 + z^2 = 615$.

Problem 12.

1. Prove that for any prime $p$ and positive integer $k$, the equation $x^2 \equiv x \pmod{p^k}$ has exactly two solutions, and write them down.
2. Find all solutions to $x^2 \equiv x \pmod{100}$.

Problem 13. Let $p$ be an odd prime.

1. Prove that for all integers $0 \le k \le p-1$, the binomial coefficient satisfies $\binom{p-1}{k} \equiv (-1)^k \pmod{p}$.
2. Compute $\displaystyle\sum_{k=0}^{p-1} \binom{p-1}{k}^2$ modulo $p$.

Problem 14. Consider the linear system over the finite field $\mathbb{F}_p$ (with $p > 3$ prime):

For which $a \in \mathbb{F}_p$ does this system have a solution?

Problem 15. Let $p$ be an odd prime and $g$ a primitive root modulo $p$.

1. Prove that $g^{(p-1)/2} \equiv -1 \pmod{p}$.
2. For which odd primes $p$ is $-g$ still a primitive root modulo $p$? Provide a proof.

Problem 16. Let $n$ be an integer strictly greater than $1$. Prove that $n^4 + 4^n$ is never prime. (Hint: use the identity $a^4 + 4b^4 = (a^2 + 2b^2 + 2ab)(a^2 + 2b^2 - 2ab)$.)

Problem 17. Find all rational solutions to $x^2 + y^2 = 2$. (Hint: use the substitution $u = \frac{x+y}{2}$, $v = \frac{x-y}{2}$.)

Problem 18. Let $p$ be an odd prime and $a$ an integer not divisible by $p$.

1. Prove that $\displaystyle\sum_{y=0}^{p-1} \left(\frac{y^2 + a}{p}\right) = -1$, where the parentheses denote the Legendre symbol.
2. Count the number of solutions $(x_0, y_0)$ to $x^2 - y^2 \equiv a \pmod{p}$.

Problem 19. Consider the Diophantine equation $x^2 + y^2 = z^3$.

1. Prove that if $(x_0, y_0, z_0)$ is an integer solution with $\gcd(x_0, y_0) = 1$, then $x_0$ is odd and $y_0$ is even.
2. Prove that in the Gaussian integer ring $\mathbb{Z}[\sqrt{-1}]$, the elements $x_0 + y_0\sqrt{-1}$ and $x_0 - y_0\sqrt{-1}$ are coprime.
3. Prove that there exist integers $a, b$ such that $$\begin{cases} x_0 = a(a^2 - 3b^2), \\ y_0 = b(3a^2 - b^2), \\ z_0 = a^2 + b^2. \end{cases}$$

Problem 20. Consider the system of linear congruences:

1. Prove that this system has a solution if and only if $a \equiv 5 \pmod{6}$.
2. For $a = 11$, find all solutions.

Problem 21. Find all odd primes $p > 7$ such that $105$ is a quadratic residue modulo $p$. What is the Dirichlet density of this set of primes?

Problem 22. Let $a_1, a_2, \ldots, a_{\frac{p-1}{2}}$ be all the quadratic residues modulo $p$. Prove that

Problem 23. Prove that the equation $(x^2 - 2)(x^2 - 3)(x^3 - 6) = 0$ has no integer solutions, yet for every prime $p$, this equation has a solution modulo $p$.

Problem 24. Consider the ring of Eisenstein integers $\mathbb{Z}[\omega]$, where $\omega = e^{2\pi i/3}$. For any $x = a + b\omega \in \mathbb{Z}[\omega]$, define its norm by $N(x) = a^2 - ab + b^2$. Let $\alpha, \beta \in \mathbb{Z}[\omega]$ such that neither $N(\alpha)$ nor $N(\beta)$ is divisible by $3$. Suppose $\alpha$ and $\beta$ are coprime in $\mathbb{Z}[\omega]$.

1. Must $N(\alpha)$ and $N(\beta)$ be coprime in $\mathbb{Z}$? If true, prove it; if false, provide a counterexample.
2. Let $g$ be the greatest common divisor of $N(\alpha)$ and $N(\beta)$ in $\mathbb{Z}$. Prove that $g \equiv 1 \pmod{3}$.

Problem 25. Prove that for any given positive integer $k$, there exist infinitely many primes whose decimal representation ends in $k$ digits all equal to $1$.

Problem 26. Let $A$ be the set of primes $p$ such that $p \equiv 1 \pmod{3}$, and $B$ the set of primes $p$ such that $p \equiv 3 \pmod{4}$. Find the Dirichlet density of $A$, of $B$, and of $A \cap B$.

Problem 27. Prove that every arithmetic progression

must contain a composite number.

Problem 28.

1. Let $m$ be a positive integer. Prove that if $p = 2^m + 1$ is prime, then $m$ is a power of $2$.
2. For $n \ge 0$, let $F_n = 2^{2^n} + 1$, called the Fermat numbers. Prove that if $m > n$, then $F_n \mid (F_m - 2)$.
3. Prove that if $m \neq n$, then $\gcd(F_m, F_n) = 1$. Use this to prove that there are infinitely many primes.

Problem 29. Find the last two decimal digits of $2026^{618}$.

Problem 30. Let $p$ be an odd prime. Prove that every primitive root modulo $p$ is a quadratic non-residue modulo $p$. For which odd primes $p$ are all quadratic non-residues also primitive roots?