Advanced Number Theory

Why it works. For coprime $m$ and $n$, look at the $mn$ numbers $0, 1, \dots, mn - 1$ and record each one's pair of remainders (mod $m$, mod $n$). Two numbers with the same pair differ by a multiple of both $m$ and $n$, hence of $mn$, so no pair is repeated. There are exactly $mn$ possible pairs, so every pair occurs exactly once: each system has a solution, and it is unique mod $mn$. To FIND it, solve one congruence, substitute the general solution into the next, and repeat.

Spotting it. Pairwise coprime moduli with product $1001$: there is exactly one answer below $1001$, and substitution finds it one congruence at a time.

Step 1. $N = 7a + 3$. Mod $11$: $7a \equiv 2$. Since $7 \cdot 8 = 56 \equiv 1 \pmod{11}$, $a \equiv 16 \equiv 5$, so $N \equiv 7 \cdot 5 + 3 = 38 \pmod{77}$.

Step 2. $N = 77b + 38$. Mod $13$: $77 \equiv -1$ and $38 \equiv 12$, so $-b + 12 \equiv 2$ and $b \equiv 10 \pmod{13}$.

Step 3. $N = 770 + 38 = 808$. Check: $808 = 7 \cdot 115 + 3 = 11 \cdot 73 + 5 = 13 \cdot 62 + 2$ ✓

Spotting it. Mod $1000$ is two easier problems: mod $8$ and mod $125$, which are coprime. Solve each, then glue with CRT.

Step 1. Mod $8$: $3^2 = 9 \equiv 1$, so $3^{2026} \equiv 1$.

Step 2. Mod $125$: $\varphi(125) = 100$, so $3^{2026} \equiv 3^{26}$. Build it up: $3^5 = 243 \equiv -7$, $3^{10} \equiv 49$, $3^{20} \equiv 49^2 = 2401 \equiv 26$, $3^{25} \equiv 26 \cdot (-7) = -182 \equiv 68$, and $3^{26} \equiv 204 \equiv 79$.

Step 3. Find $x \equiv 79 \pmod{125}$ with $x \equiv 1 \pmod 8$: try $79, 204, 329$; the remainders mod $8$ are $7, 4, 1$. So the answer is $329$.

Why it works. List the $\varphi(n)$ numbers below $n$ that are coprime to $n$ and multiply each by $a$. The products are still coprime to $n$ and are all different mod $n$ (if $ax \equiv ay$ then $x \equiv y$, because $a$ is invertible), so they are the same list in a new order. The two lists have the same product, so $a^{\varphi(n)} \cdot (\text{product}) \equiv \text{product}$, and cancelling the product (which is invertible) leaves $a^{\varphi(n)} \equiv 1$.

Why the order divides $\varphi(n)$. Let $d$ be the order. Divide: $\varphi(n) = qd + r$ with $0 \le r < d$. Then $1 \equiv a^{\varphi(n)} = (a^d)^q a^r \equiv a^r$, and $r < d$ forces $r = 0$ by the minimality of $d$. The same argument shows $a^k \equiv 1$ exactly when $d \mid k$, which is what makes towers of exponents manageable.

Spotting it. The base $2$ has order $3$ mod $7$ ($2^3 = 8 \equiv 1$), so only the exponent mod $3$ matters. The exponent is itself a power of $2$, and $2 \equiv -1 \pmod 3$.

Step 1. $2^{2026} \equiv (-1)^{2026} = 1 \pmod 3$.

Step 2. So $2^{2^{2026}} \equiv 2^1 = 2 \pmod 7$.

Spotting it. For $n$ coprime to $10$, the decimal of $\tfrac1n$ repeats with period equal to the ORDER of $10$ mod $n$: the remainders of long division are the powers of $10$ mod $n$.

Step 1. The order of $10$ mod $41$ divides $\varphi(41) = 40$. Test small divisors: $10^2 = 100 \equiv 18$, $10^4 \equiv 18^2 = 324 \equiv 37$, $10^5 \equiv 370 \equiv 1$. So the period is $5$ (indeed $1/41 = 0.\overline{02439}$).

Step 2. $287 = 7 \cdot 41$. The order of $10$ mod $7$ is $6$ ($1/7 = 0.\overline{142857}$). A power of $10$ is $1$ mod $287$ exactly when it is $1$ mod $7$ and mod $41$, i.e. when the exponent is a multiple of both $6$ and $5$. The period is $\operatorname{lcm}(6, 5) = 30$.

$100!$ ends in $\left\lfloor\tfrac{100}5\right\rfloor + \left\lfloor\tfrac{100}{25}\right\rfloor = 20 + 4 = 24$ zeros, because fives are scarcer than twos. AIME versions ask for the power of a prime in a binomial coefficient, where Kummer's theorem — the exponent equals the number of carries when adding in base $p$ — turns the computation into base-$p$ addition.

So $\sigma(72) = \sigma(8)\sigma(9) = 15\cdot13 = 195$ and $d(72) = 4\cdot3 = 12$. Problems asking for "the number of divisors of $n$ that are perfect squares" restrict each exponent to even values, giving $\prod\left(\left\lfloor\tfrac{a_i}2\right\rfloor + 1\right)$ — the same product with a floor, and that pattern answers most divisor-counting variants.

Step 1 — zeros come from factors of $10 = 2\cdot5$, and twos are plentiful, so count fives.

Step 2 — $v_5(200!) = \left\lfloor\tfrac{200}5\right\rfloor + \left\lfloor\tfrac{200}{25}\right\rfloor + \left\lfloor\tfrac{200}{125}\right\rfloor = 40 + 8 + 1 = 49$.

Step 3 — so $200!$ ends in $49$ zeros.

Spotting it. $\dbinom{100}{50} = \dfrac{100!}{50!\,50!}$, so its $3$-adic valuation is $v_3(100!) - 2v_3(50!)$, and Legendre computes each piece.

Step 1. $v_3(100!) = 33 + 11 + 3 + 1 = 48$.

Step 2. $v_3(50!) = 16 + 5 + 1 = 22$.

Step 3. $48 - 44 = 4$, so $n = 4$.

Check with Kummer: $50 = 1212_3$, and adding $1212_3 + 1212_3$ produces a carry in each of the four places, so the valuation is $4$ ✓

Spotting it. An odd divisor uses no factor of $2$, so the odd divisors of $360 = 2^3 \cdot 3^2 \cdot 5$ are exactly the divisors of $45 = 3^2 \cdot 5$.

Step 1. $\sigma(45) = \sigma(9)\sigma(5) = (1 + 3 + 9)(1 + 5) = 13 \cdot 6 = 78$.