Modular Arithmetic

Today is Tuesday. What day is it $100$ days from now? Days repeat every $7$, so only $100 \bmod 7$ matters: $100 = 14\cdot7 + 2$. Fourteen whole weeks bring us back to Tuesday, and $2$ more days reach Thursday.

Find $2^{100} \bmod 7$. Look for a small power that is $\equiv 1$: $2^3 = 8 \equiv 1 \pmod 7$. Then write the exponent in multiples of $3$: $2^{100} = (2^3)^{33}\cdot2 \equiv 1^{33}\cdot2 = 2$. Multiplying congruences is what licenses replacing $2^3$ by $1$ inside the power. Answer $2$.

Find the remainder of $3^{50} + 5^{50}$ on division by $8$. Squares first: $3^2 = 9 \equiv 1$ and $5^2 = 25 \equiv 1 \pmod 8$. So $3^{50} = (3^2)^{25} \equiv 1$ and $5^{50} = (5^2)^{25} \equiv 1$, and the sum is $\equiv 2$. The remainder is $2$ — no need to know that $3^{50}$ has $24$ digits.

Show that $n^2 + 2$ is never divisible by $5$. Square each residue: $0 \to 0$, $1 \to 1$, $2 \to 4$, $3 \to 9 \equiv 4$, $4 \to 16 \equiv 1$. So $n^2 \in \{0, 1, 4\}$ mod $5$ and $n^2 + 2 \in \{2, 3, 1\}$ — never $0$. Notice that $2$ and $3 = -2$ land together, as do $1$ and $4 = -1$: $n$ and $-n$ always have the same square.

Since $6 = 2\cdot3$ with $\gcd(2, 3) = 1$, it suffices to show $2 \mid n^3 - n$ and $3 \mid n^3 - n$. Mod $2$: $0^3 - 0 = 0$ and $1^3 - 1 = 0$. Mod $3$: $0 - 0 = 0$, $1 - 1 = 0$, $8 - 2 = 6 \equiv 0$. Every class gives $0$, so both primes divide $n^3 - n$, and so does $6$. (Factored, $n^3 - n = (n - 1)n(n + 1)$ is a product of three consecutive integers.)

If $a^2 + b^2 = c^2$ in integers, show that $3$ divides $a$ or $b$. Squares mod $3$ are $0$ (for $n \equiv 0$) or $1$ (for $n \equiv \pm1$). If neither $a$ nor $b$ were a multiple of $3$, then $a^2 + b^2 \equiv 1 + 1 = 2$, but $c^2$ can only be $0$ or $1$. So one of $a, b$ is a multiple of $3$ — as in $3, 4, 5$ and $5, 12, 13$.

$\gcd(7, 20) = 1$, so $7$ has an inverse and there is exactly one solution. Find the inverse by trying multiples of $7$ until one is $1$ more than a multiple of $20$: $7\cdot3 = 21 \equiv 1$, so $7^{-1} \equiv 3$. Multiply both sides by $3$: $x \equiv 3\cdot3 = 9$. Check: $7\cdot9 = 63 = 3\cdot20 + 3$. ✓

$\gcd(6, 10) = 2$ divides $4$, so there are $2$ solutions. Divide everything, modulus included, by $2$: $3x \equiv 2 \pmod 5$. Now $3^{-1} \equiv 2$ (as $3\cdot2 = 6 \equiv 1$), so $x \equiv 4 \pmod 5$. Back mod $10$ that is $x = 4$ or $x = 9$. The figure shows why: $6x \bmod 10$ only ever lands on even residues, each one twice.

$\gcd(12, 21) = 3$ and $3 \mid 9$: three solutions. Divide by $3$: $4x \equiv 3 \pmod 7$. Since $4\cdot2 = 8 \equiv 1$, $4^{-1} \equiv 2$ and $x \equiv 6 \pmod 7$. Mod $21$ the solutions are $x = 6, 13, 20$. Check $x = 13$: $156 = 7\cdot21 + 9$. ✓ By contrast $10x \equiv 5 \pmod{14}$ has NO solution: $\gcd(10, 14) = 2$ does not divide $5$ (an even number cannot be $5$ more than a multiple of $14$).