Đồng dư, chia hết và hàm số cộng tính

When cycles line up

• One gear repeats every 4 minutes, another every 7. "Position 2 on the first and 3 on the second" is the pair $x \equiv 2 \pmod 4$, $x \equiv 3 \pmod 7$.
• GRE number theory tests linear congruences 同余, inverses, the Chinese remainder theorem 中国剩余定理 and Euler's theorem.

Solving $ax \equiv b \pmod n$

• Let $d = \gcd(a, n)$. Solvable $\iff d \mid b$; then there are $d$ solutions modulo $n$.
• Divide $a$, $b$ and $n$ by $d$, solve, then lift back to modulus $n$.

Inverses by Euclid

• The extended Euclidean algorithm writes $\gcd(a,n) = ua + vn$; when it is 1, $u$ is $a^{-1} \bmod n$.
• $1 = 15 \cdot 7 - 4 \cdot 26$, so $7^{-1} \equiv 15 \pmod{26}$. Check: $105 = 4 \cdot 26 + 1$.

Chinese remainder theorem

• Coprime $m, n$: exactly one solution modulo $mn$. Substitute $x = r + mk$ into the second congruence.
• $x = 2 + 4k$, $4k \equiv 1 \pmod 7$, $k \equiv 2$: $x \equiv 10 \pmod{28}$. Non-coprime moduli need the residues to agree mod $\gcd$, with uniqueness mod lcm.

Euler's theorem

• The totient 欧拉函数 $\varphi(n) = n\prod_{p \mid n}(1 - \tfrac1p)$. If $\gcd(a, n) = 1$: $a^{\varphi(n)} \equiv 1 \pmod n$ (Fermat when $n$ is prime).
• $3^{100} \bmod 10$: $\varphi(10) = 4$, $3^{100} = (3^4)^{25} \equiv 1$.

Recap