中国剰余定理 (CRT)

• n と m が互いに素なとき、$\mathbb{Z}/nm\mathbb{Z} \cong \mathbb{Z}/n\mathbb{Z} \times \mathbb{Z}/m\mathbb{Z}$
• 3つ以上にも拡張できる (ACL にある)
• 詳細: ‣ を参照
• 互いに素じゃない場合に 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$ は $\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}$ の周期性について

• $M$ と $N$ が互いに素な場合
  • 最初から周期する。周期は $\varphi(N)$ の約数になる。
    • この周期は $(\mathbb{Z}/N\mathbb{Z})^\times$ における位数 $\operatorname{ord}(M)$ である。
  • $2^k \pmod{7}$ の場合
• $M$ と $N$ が互いに素ではない場合
  • 最初、または途中から周期する。周期は $\varphi(N)$ の約数になる。
  • $2^k \pmod{10}$ の場合
  • $2^k \pmod{20}$ や一般のケースの場合