中国剰余定理 (CRT)

• $n$ と $m$ が互いに素なとき、$\mathbb{Z}/nm\mathbb{Z} \cong \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$
• 証明
• 環による一般化
• 帰納的に3つ以上にも拡張できる (ACL にある)
• 競技プログラミングにおける CRT
• 互いに素じゃない場合に CRT をしたい場合

オイラーのトーシェント関数

• $\varphi(n)$ は $n$ 未満の自然数で $n$ と互いに素なものの数
• $\varphi(n) = \lvert (\mathbb{Z}/n\mathbb{Z})^\times\rvert$ が成り立つ
  • $\mathrm{mod}\ n$ で逆元を持つのは $n$ と互いに素なときであることが不定方程式の話からわかる
• $n = {p_1}^{e_1} \cdots {p_r}^{e_r}$ と素因数分解できるとき、$\varphi(n) = n \prod_{i=1}^r (1-1/p_i)$
  • 証明は中国剰余定理だったり、包除原理だったり、メビウスの反転公式だったり。
• $\sum_{d \mid n} \varphi(d) = n$
  • $\{0,1,\ldots, n-1\}$ を $n$ との $\gcd$ で分割する。 $\gcd(i, n) = n/d$ となる $i \in \{0,1,\ldots, n\}$ は $\varphi(d)$ 個ある

オイラーの定理・フェルマーの小定理

• オイラーの定理
  • $a$ と $n$ が互いに素なとき、$a^{\varphi(n)} \equiv 1 \pmod{n}$
  • 証明: ラグランジュの定理から言える。
  • $a$ の $\operatorname{mod} n$ での逆元は $a^{\varphi(n) - 1}$ で求まる ( $a$ と $n$ が互いに素なとき)
• フェルマーの小定理
  • $p$ が素数で、$a$ と $p$ が互いに素なとき、$a^{p-1} \equiv 1 \pmod{p}$
    • オイラーの定理の一般化
  • $a$ が $p$ の倍数の場合も含めて、$a^p \equiv a \pmod{p}$
  • $a$ の $\operatorname{mod} p$ での逆元は $a^{p -2}$ で求まる

べき乗 mod N の周期

$M^k \pmod{N}$ の周期性について