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$.

📝 Full Solution

Step 1: Since 13 is prime and $\gcd(7, 13) = 1$, by Fermat's Little Theorem: $7^{12} \equiv 1 \pmod{13}$.

Step 2: Write $100 = 12 \times 8 + 4$, so $7^{100} = (7^{12})^8 \cdot 7^4 \equiv 1^8 \cdot 7^4 \equiv 7^4 \pmod{13}$.

Step 3: Compute $7^2 = 49 \equiv 49 - 3(13) = 49 - 39 = 10 \pmod{13}$.

Step 4: $7^4 = (7^2)^2 \equiv 10^2 = 100 \equiv 100 - 7(13) = 100 - 91 = 9 \pmod{13}$.

Answer: The remainder is $9$

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$.

📝 Full Solution

Step 1 (Euclidean Algorithm):

$252 = 1 \times 198 + 54$

$198 = 3 \times 54 + 36$

$54 = 1 \times 36 + 18$

$36 = 2 \times 18 + 0$

So $\gcd(252, 198) = 18$.

Step 2 (Back-substitution):

$18 = 54 - 1 \times 36$

$= 54 - 1 \times (198 - 3 \times 54) = 4 \times 54 - 1 \times 198$

$= 4 \times (252 - 1 \times 198) - 1 \times 198 = 4 \times 252 - 5 \times 198$

Step 3: Verify: $4(252) - 5(198) = 1008 - 990 = 18$. Correct.

Answer: $\gcd(252, 198) = 18$, with $x = 4$ and $y = -5$

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.

📝 Full Solution

Step 1: Factor: $360 = 2^3 \times 3^2 \times 5$.

Step 2: Apply the totient formula: $$\phi(360) = 360\left(1 - \frac{1}{2}\right)\left(1 - \frac{1}{3}\right)\left(1 - \frac{1}{5}\right) = 360 \times \frac{1}{2} \times \frac{2}{3} \times \frac{4}{5} = 96$$

Step 3: Since $\gcd(7, 360) = 1$, by Euler's theorem: $7^{96} \equiv 1 \pmod{360}$.

Step 4: Write $100 = 96 + 4$, so $7^{100} = 7^{96} \cdot 7^4 \equiv 1 \cdot 7^4 \pmod{360}$.

Step 5: Compute: $7^2 = 49$. $7^4 = 49^2 = 2401$. $2401 = 6 \times 360 + 241$, so $7^4 \equiv 241 \pmod{360}$.

Answer: $\phi(360) = 96$ and $7^{100} \equiv 241 \pmod{360}$

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$.

📝 Full Solution

Step 1: Find one solution by inspection. Try $x = 4$: $12 + 5y = 47 \Rightarrow y = 7$. So $(4, 7)$ works.

Step 2: General solution of $3x + 5y = 47$: $x = 4 + 5t$, $y = 7 - 3t$ for any integer $t$.

Step 3: Require $x > 0$: $4 + 5t > 0 \Rightarrow t > -\frac{4}{5} \Rightarrow t \geq 0$ (since $t$ is an integer).

Step 4: Require $y > 0$: $7 - 3t > 0 \Rightarrow t < \frac{7}{3} \Rightarrow t \leq 2$.

Step 5: So $t \in \{0, 1, 2\}$, giving solutions: $(4, 7)$, $(9, 4)$, $(14, 1)$.

Answer: $(x, y) = (4, 7),\; (9, 4),\; (14, 1)$

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.

📝 Full Solution

Step 1: From $n \equiv 2 \pmod{3}$: $n = 3k + 2$ for some integer $k$.

Step 2: Substitute into $n \equiv 3 \pmod{5}$: $3k + 2 \equiv 3 \pmod{5} \Rightarrow 3k \equiv 1 \pmod{5}$. Since $3 \times 2 = 6 \equiv 1 \pmod{5}$, we get $k \equiv 2 \pmod{5}$, so $k = 5j + 2$.

Step 3: Then $n = 3(5j + 2) + 2 = 15j + 8$.

Step 4: Substitute into $n \equiv 4 \pmod{7}$: $15j + 8 \equiv 4 \pmod{7} \Rightarrow j + 1 \equiv 4 \pmod{7} \Rightarrow j \equiv 3 \pmod{7}$.

Step 5: So $j = 7m + 3$ and $n = 15(7m + 3) + 8 = 105m + 53$.

Step 6: The smallest positive value is $m = 0$: $n = 53$. Verify: $53 = 17(3)+2$, $53 = 10(5)+3$, $53 = 7(7)+4$.

Answer: $n = 53$

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.

📝 Full Solution

Step 1: Factor 496: $496 = 2^4 \times 31$.

Step 2: List all proper divisors: 1, 2, 4, 8, 16, 31, 62, 124, 248.

Step 3: Sum: $1 + 2 + 4 + 8 + 16 + 31 + 62 + 124 + 248 = 496$. Since the sum of proper divisors equals the number, 496 is perfect.

Step 4: Note that $496 = 2^4(2^5 - 1) = 16 \times 31$, where $p = 5$ and $2^5 - 1 = 31$ is indeed prime (a Mersenne prime).

Step 5: By the Euclid-Euler theorem, all even perfect numbers have the form $2^{p-1}(2^p - 1)$ where $2^p - 1$ is a Mersenne prime.

Answer: 496 is perfect (sum of proper divisors = 496). Even perfect numbers have the form $2^{p-1}(2^p - 1)$ where $2^p - 1$ is 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$

📝 Full Solution

Step 1: Find the prime factorization of $10!$ using Legendre's formula. For each prime $p$, the exponent is $\sum_{i=1}^{\infty}\lfloor\frac{10}{p^i}\rfloor$.

Step 2: For $p = 2$: $\lfloor\frac{10}{2}\rfloor + \lfloor\frac{10}{4}\rfloor + \lfloor\frac{10}{8}\rfloor = 5 + 2 + 1 = 8$.

For $p = 3$: $\lfloor\frac{10}{3}\rfloor + \lfloor\frac{10}{9}\rfloor = 3 + 1 = 4$.

For $p = 5$: $\lfloor\frac{10}{5}\rfloor = 2$. For $p = 7$: $\lfloor\frac{10}{7}\rfloor = 1$.

Step 3: So $10! = 2^8 \times 3^4 \times 5^2 \times 7^1$.

Step 4: Number of divisors $= (8+1)(4+1)(2+1)(1+1) = 9 \times 5 \times 3 \times 2 = 270$.

Answer: $10!$ has 270 positive divisors

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$.

📝 Full Solution

Step 1: We need $3^{2026} \pmod{100}$. Since $\phi(100) = 100(1 - \frac{1}{2})(1 - \frac{1}{5}) = 40$ and $\gcd(3, 100) = 1$, Euler's theorem gives $3^{40} \equiv 1 \pmod{100}$.

Step 2: $2026 = 40 \times 50 + 26$, so $3^{2026} \equiv 3^{26} \pmod{100}$.

Step 3: Compute $3^{26}$ by repeated squaring modulo 100:

$3^2 = 9$, $3^4 = 81$, $3^8 = 81^2 = 6561 \equiv 61$, $3^{16} = 61^2 = 3721 \equiv 21$.

Step 4: $3^{26} = 3^{16} \times 3^8 \times 3^2 = 21 \times 61 \times 9$.

$21 \times 61 = 1281 \equiv 81 \pmod{100}$. Then $81 \times 9 = 729 \equiv 29 \pmod{100}$.

Answer: The last two digits of $3^{2026}$ are 29

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.

📝 Full Solution

Step 1: The last digit of $n^2$ depends only on the last digit of $n$. We check all possible last digits $d = 0, 1, \ldots, 9$:

$0^2 = 0$, $1^2 = 1$, $2^2 = 4$, $3^2 = 9$, $4^2 = 16 \to 6$, $5^2 = 25 \to 5$, $6^2 = 36 \to 6$, $7^2 = 49 \to 9$, $8^2 = 64 \to 4$, $9^2 = 81 \to 1$.

Step 2: The set of possible last digits of perfect squares is $\{0, 1, 4, 5, 6, 9\}$.

Step 3: The digits 2, 3, 7, and 8 are not in this set. Therefore, no perfect square can end in 2, 3, 7, or 8.

Answer: Proven by exhaustive check of all residues mod 10. The only quadratic residues mod 10 are $\{0, 1, 4, 5, 6, 9\}$, excluding 2, 3, 7, 8.

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}$.

📝 Full Solution

Step 1: Since $n$ is composite, we can write $n = ab$ where $1 < a \leq b < n$.

Step 2: Suppose for contradiction that $a > \sqrt{n}$. Then $b \geq a > \sqrt{n}$, so $ab > \sqrt{n} \cdot \sqrt{n} = n$. But $ab = n$, a contradiction.

Step 3: Therefore $a \leq \sqrt{n}$. Since $a > 1$, it has a prime factor $p$ with $p \leq a$.

Step 4: This prime $p$ divides $a$, which divides $n$, so $p$ is a prime factor of $n$ with $p \leq a \leq \sqrt{n}$.

Answer: Proven: every composite $n > 1$ has a prime factor $\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}$.

📝 Full Solution

Step 1: Wilson's Theorem states that if $p$ is prime, then $(p-1)! \equiv -1 \pmod{p}$.

Step 2: Since 13 is prime: $12! \equiv -1 \pmod{13}$.

Step 3: Now $-1 \equiv 12 \pmod{13}$.

Step 4: Therefore $12! \equiv 12 \pmod{13}$, meaning the remainder is 12.

Answer: The remainder when $12!$ is divided by 13 is $12$

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}$).

📝 Full Solution

Step 1: Assume for contradiction that there are only finitely many primes of the form $4k + 3$: call them $p_1, p_2, \ldots, p_n$ (note $p_1 = 3$).

Step 2: Consider $N = 4p_1 p_2 \cdots p_n - 1$. Then $N \equiv -1 \equiv 3 \pmod{4}$, so $N$ is of the form $4k + 3$.

Step 3: Every odd number greater than 1 is a product of odd primes. Each odd prime is either $\equiv 1 \pmod{4}$ or $\equiv 3 \pmod{4}$.

Step 4: A product of primes all $\equiv 1 \pmod{4}$ is itself $\equiv 1 \pmod{4}$. Since $N \equiv 3 \pmod{4}$, at least one prime factor of $N$ must be $\equiv 3 \pmod{4}$.

Step 5: But $N = 4p_1 p_2 \cdots p_n - 1$, so for any $p_i$ in our list, $N \equiv -1 \pmod{p_i}$, meaning $p_i \nmid N$. This prime factor of the form $4k+3$ is not in our list -- a contradiction.

Answer: Proven by contradiction: there are infinitely many primes of the form $4k + 3$.