Number Theory: Modular Arithmetic

Why it works. If $a = b + mn$ and $c = d + kn$, then $a + c$ and $b + d$ differ by a multiple of $n$, and so do $ac = bd + n(bk + dm + mkn)$ and $bd$. So the remainder of a sum or product depends only on the remainders of the pieces. Powers are repeated products, which is why a power's remainder cycles: there are only $n$ possible remainders, so the sequence $a, a^2, a^3, \dots$ must eventually repeat, and from then on it repeats forever.

Spotting it. "Last digit" means "remainder mod $10$", and powers of a fixed number cycle mod $10$. Find the cycle, then reduce the exponent modulo its length.

Step 1. $7^1 \equiv 7$, $7^2 = 49 \equiv 9$, $7^3 \equiv 63 \equiv 3$, $7^4 \equiv 21 \equiv 1$. The cycle $7, 9, 3, 1$ has length $4$.

Step 2. $2027 = 4 \cdot 506 + 3$, so $7^{2027} = (7^4)^{506} \cdot 7^3 \equiv 3$. The last digit is $3$.

Spotting it. From some point on, every term is a multiple of $12$ and contributes nothing. Find that point.

Step 1. $4! = 24$ is divisible by $12$, and every later factorial is a multiple of $4!$.

Step 2. Only $1! + 2! + 3! = 9$ matters, so the remainder is $9$.

Spotting it. Whether $5$ divides $n^2 + 1$ depends only on $n \bmod 5$, so check the five residues once and then count.

Step 1. $n \equiv 0, 1, 2, 3, 4$ give $n^2 + 1 \equiv 1, 2, 0, 0, 2 \pmod 5$. So $n \equiv 2$ or $3 \pmod 5$.

Step 2. Each block of five consecutive integers contains exactly two such $n$, and $1$ to $100$ is twenty blocks: $40$ values.

Solve by substitution: from $x \equiv 2 \pmod 5$ write $x = 5t + 2$, substitute into $x \equiv 3 \pmod 7$ to get $5t \equiv 1 \pmod 7$, so $t \equiv 3 \pmod 7$ and $x \equiv 17 \pmod{35}$. Checking both congruences at the end costs seconds and catches the common slip of inverting the wrong coefficient.

Last two digits means modulo $100$: $3^{2026} = 3^{40\cdot50 + 26} \equiv 3^{26} \pmod{100}$, and squaring up gives $3^{26} \equiv 29 \pmod{100}$, so the last two digits are $29$. The trap is applying Euler when $\gcd(a,n) \ne 1$ — for $2^k \bmod 100$ the cycle still exists but starts later, so compute $2^k$ modulo $4$ and modulo $25$ and recombine.

Step 1 — $x = 5t + 2$.

Step 2 — $5t + 2 \equiv 3 \pmod 7$, so $5t \equiv 1 \pmod 7$.

Step 3 — $5^{-1} \equiv 3 \pmod 7$ (since $15 \equiv 1$), so $t \equiv 3 \pmod 7$ and the smallest is $t = 3$, $x = 17$. Check: $17 = 3\cdot5 + 2$ and $17 = 2\cdot7 + 3$ ✓

Spotting it. Last two digits means mod $100$. Euler would reduce the exponent mod $40$, but squaring a couple of times shows $57$ cycles much faster: $57^2 = 3249 \equiv 49$, and $49^2 = 2401 \equiv 1$.

Step 1. $57^4 \equiv 1 \pmod{100}$.

Step 2. $2027 = 4 \cdot 506 + 3$, so $57^{2027} \equiv 57^3 \equiv 49 \cdot 57 = 2793 \equiv 93 \pmod{100}$. The last two digits are $93$.

Spotting it. $\gcd(2, 100) \ne 1$, so Euler's theorem does not apply mod $100$. Split $100 = 4 \cdot 25$ into coprime parts, work in each, and recombine with CRT.

Step 1. Mod $4$: $2^{100} \equiv 0$.

Step 2. Mod $25$: $\gcd(2, 25) = 1$ and $\varphi(25) = 20$, so $2^{100} = (2^{20})^5 \equiv 1$.

Step 3. Find $x \equiv 0 \pmod 4$ with $x \equiv 1 \pmod{25}$: among $1, 26, 51, 76$ only $76$ is a multiple of $4$. The last two digits are $76$.

Why it works. Only the remainder of $n$ matters, so check each residue once: $(2k)^2 = 4k^2 \equiv 0 \pmod 4$, and $(2k + 1)^2 = 4k(k + 1) + 1 \equiv 1 \pmod 8$ because one of $k, k + 1$ is even. An equation that holds for integers must hold mod every $n$, so a single modulus where it fails rules out every integer solution at once. A modulus can prove impossibility; it can never prove that a solution exists.

Spotting it. A sum of two squares is a sum of two numbers from $\{0, 1\}$ mod $4$, so it is $0$, $1$ or $2 \pmod 4$.

Step 1. $2027 = 4 \cdot 506 + 3 \equiv 3 \pmod 4$.

Step 2. No: $3$ is not a possible remainder.

Spotting it. $a^2 - b^2 = (a - b)(a + b)$, and the two factors $a - b$ and $a + b$ have the same parity (they differ by $2b$). That decides which $n$ are possible.

Step 1. If $n$ is odd, $n = \left(\tfrac{n + 1}{2}\right)^2 - \left(\tfrac{n - 1}{2}\right)^2$. If $4 \mid n$, $n = \left(\tfrac n4 + 1\right)^2 - \left(\tfrac n4 - 1\right)^2$.

Step 2. If $n \equiv 2 \pmod 4$: two factors of the same parity multiply to an odd number or to a multiple of $4$, never to $2 \pmod 4$. So these $n$ fail.

Step 3. The failures are $2, 6, 10, \dots, 98$, which is $25$ numbers, so $100 - 25 = 75$ can be written.

Spotting it. Mod $4$ is too coarse for three squares (three terms from $\{0, 1\}$ reach every residue). Mod $8$ squares are $0, 1, 4$, and three of them can make every residue EXCEPT $7$: sums of three values from $\{0, 1, 4\}$ give $0, 1, 2, 3, 4, 5, 6$ and then $8, 9, 12$.

Step 1. $2023 = 8 \cdot 252 + 7 \equiv 7 \pmod 8$, so $2023$ is impossible.

Step 2. The others do work, for instance $2024 = 38^2 + 24^2 + 2^2$, $2025 = 45^2 + 0^2 + 0^2$ and $2026 = 45^2 + 1^2 + 0^2$. (The mod-$8$ test alone could not have shown that; examples do.)