Modular Arithmetic (AIME / USAJMO / AMO)

Proof-style AIME / USAJMO / AMO statements — develop a full argument; type only the final answer.

Proof track: treat each problem as a full olympiad writeup on paper. Here you only enter the final answer (integer or short expression).

Modular Arithmetic: core idea

Orders and Fermat.

**(Proof track.)** Prove Fermat’s little theorem for prime $p$ and then compute $2^{100}\bmod 101$ . Enter the remainder.

Hint: $2^{100}\equiv1\pmod{101}$ since $101\nmid2$ . Answer: 1.

No proof submission required — answers only.

1. **(Proof track.)** Prove the Chinese Remainder Theorem for pairwise coprime moduli, then find the unique $n\in(0,5\cdot7\cdot8]$ with $n\equiv1\pmod5$ , $n\equiv2\pmod7$ , $n\equiv3\pmod8$ . Enter $n$ .
2. **(Proof track.)** Prove that the order of $a$ modulo $n$ (when $\gcd(a,n)=1$ ) divides $\varphi(n)$ . Enter the order of $3$ modulo $14$ .
3. **(Proof track.)** Using Wilson’s theorem, prove $(p-1)!\equiv-1\pmod p$ for prime $p$ . Enter $12!\bmod 13$ .
4. **(Proof track.)** Prove a formula for the number of solutions to $x^2\equiv1\pmod{p^k}$ for odd prime $p$ . For $p=5$ , $k=2$ (mod $25$ ), how many solutions in $0\le x<25$ ?
5. **(Proof track.)** Prove Euler’s criterion or use successive squaring: enter $5^{16}\bmod 17$ .
6. **(Proof track.)** Show that if $p$ is an odd prime, then $\sum_{k=1}^{p-1}k^{p-2}\equiv-1\pmod p$ or compute the concrete case: enter $\sum_{k=1}^{6}k^{5}\bmod 7$ .
7. **(Proof track.)** Prove the lifting-the-exponent lemma (LTE) for $v_2(x^n\pm y^n)$ in the standard case, then enter $v_2(3^{8}-1)$ .
8. **(Proof track.)** Prove that there are infinitely many primes $p\equiv3\pmod4$ (Euclid-style). As a computational check related to the construction, enter the smallest prime $p>20$ with $p\equiv3\pmod4$ .
9. **(Proof track.)** Prove $\varphi$ is multiplicative and compute $\varphi(504)$ . Enter the value.