Number Theory — CheriMathLab

Key Theorems & Concepts

Fundamental Theorem of Arithmetic: Every integer $> 1$ has a unique prime factorization.
Fermat's Little Theorem: If $p$ is prime and $\gcd(a, p) = 1$, then $$a^{p-1} \equiv 1 \pmod{p}$$
Euler's Theorem: If $\gcd(a, n) = 1$, then $$a^{\phi(n)} \equiv 1 \pmod{n}$$
Euler's Totient: $$\phi(n) = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right)$$ for each prime $p$ dividing $n$
GCD & LCM: $$\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b$$
Bézout's Identity: There exist integers $x, y$ such that $$ax + by = \gcd(a, b)$$
Chinese Remainder Theorem: If $\gcd(m, n) = 1$, the system $x \equiv a \pmod{m}$, $x \equiv b \pmod{n}$ has a unique solution mod $mn$.
Wilson's Theorem: $$(p-1)! \equiv -1 \pmod{p}$$ iff $p$ is prime

1 Modular Arithmetic Medium

Find the remainder when $7^{100}$ is divided by 13.

Show Hint

By Fermat's Little Theorem, $7^{12} \equiv 1 \pmod{13}$. Write $100 = 12 \times 8 + 4$, so $7^{100} \equiv 7^4 \pmod{13}$. Compute $7^4$.

2 GCD & Bézout's Identity Medium

Find $\gcd(252, 198)$ using the Euclidean algorithm. Then find integers $x, y$ such that $252x + 198y = \gcd(252, 198)$.

Show Hint

$252 = 1 \times 198 + 54$; $198 = 3 \times 54 + 36$; $54 = 1 \times 36 + 18$; $36 = 2 \times 18$. So $\gcd = 18$. Back-substitute to find $x$ and $y$.

3 Euler's Totient Medium

Compute $\phi(360)$ and use it to find $7^{100} \mod 360$.

Show Hint

$360 = 2^3 \times 3^2 \times 5$. So $\phi(360) = 360 \times (1-\frac{1}{2})(1-\frac{1}{3})(1-\frac{1}{5}) = 96$. Then use Euler's theorem.

4 Diophantine Equation Hard

Find all positive integer solutions to $3x + 5y = 47$.

Show Hint

Find one particular solution (e.g., $x = 4, y = 7$). The general solution is $x = 4 + 5t$, $y = 7 - 3t$. Find which values of $t$ give positive $x$ and $y$.

5 Chinese Remainder Theorem Hard

Find the smallest positive integer $n$ such that $n \equiv 2 \pmod{3}$, $n \equiv 3 \pmod{5}$, and $n \equiv 4 \pmod{7}$.

Show Hint

By CRT, a unique solution exists mod 105. Start with $n \equiv 2 \pmod{3}$: $n = 3k + 2$. Substitute into the second congruence and solve, then the third.

6 Perfect Numbers Medium

Show that 496 is a perfect number. What is the form of all even perfect numbers according to the Euclid-Euler theorem?

Show Hint

Find all divisors of 496 and verify they sum to 496. Even perfect numbers have the form $2^{p-1}(2^p - 1)$ where $2^p - 1$ is a Mersenne prime.

7 Divisor Function Hard

How many positive divisors does $10!$ have?

Show Hint

First find the prime factorization of $10!$. Use the formula: if $n = p_1^{a_1} \times p_2^{a_2} \times \cdots$, then the number of divisors is $(a_1+1)(a_2+1)\cdots$

8 Last Digits Hard

Find the last two digits of $3^{2026}$.

Show Hint

We need $3^{2026} \mod 100$. Since $\phi(100) = 40$, and $\gcd(3,100) = 1$, we have $3^{40} \equiv 1 \pmod{100}$. Write $2026 = 40 \times 50 + 26$.

9 Sum of Digits Olympiad

Prove that no perfect square ends in the digits 2, 3, 7, or 8 (in base 10).

Show Hint

Check all possible values of $n \mod 10$ (from 0 to 9). Compute $n^2 \mod 10$ for each. The only possible last digits of $n^2$ are 0, 1, 4, 5, 6, 9.

10 Primality & Factoring Medium

Prove that if $n > 1$ is composite, then $n$ has a prime factor $\leq \sqrt{n}$.

Show Hint

If $n = ab$ with $1 < a \leq b < n$, then $a \leq \sqrt{n}$ (otherwise $a \times b > n$). The smallest factor of $a$ is a prime $\leq a \leq \sqrt{n}$.

11 Wilson's Theorem Application Hard

Find the remainder when $12!$ is divided by 13.

Show Hint

By Wilson's Theorem, $(13-1)! = 12! \equiv -1 \pmod{13}$. So $12! \equiv 12 \pmod{13}$.

12 Infinite Primes Olympiad

Prove that there are infinitely many primes of the form $4k + 3$.

Show Hint

Assume finitely many such primes: $p_1, p_2, \ldots, p_n$. Consider $N = 4p_1 p_2 \cdots p_n - 1$. Show $N \equiv 3 \pmod{4}$ and that $N$ must have a prime factor of the form $4k + 3$ not in the list (since a product of numbers $\equiv 1 \pmod{4}$ is $\equiv 1 \pmod{4}$).