[#mod](mod) 加算・減算・乗算 定義 $\mathbb{Z}_m$を集合${0, 1, 2, ..., m-1}$とする。$\mathbb{Z}_m$における加算$+_m$、減算$-_m$、乗算$\cdot_m$を次のように定義する - $a +_m b = (a+b) \bmod m$ - $a -_m b = (a-b) \bmod m$ - $a \cdot_m b = (a \cdot b) \bmod m$ 乗法逆元 定義 ある整数$a$は、$a \cdot_m b = (ab \bmod m) = 1$であるような整数$b$が存在するとき、$m$を法とする[[乗法逆元]]をもつという。$\mathbb{Z}_m$の[[単元]]とは、$m$を法とする逆元を持つ整数$a$のことである。 - 例: $3 \cdot_7 5 = 1$より、3は$\mathbb{Z}_7$に乗法逆元5をもつ。(逆も一緒) - $m$を法とする逆元のペアを見つけるテクニック - $k \bmod m = 1$の形をした数$k$を因数分解する - 例: $55 \bmod 27 = 1$ → $55 = 11 \cdot 5$ → 11と5は、$\mathbb{Z}_{27}$におけるお互いの乗法逆元 - $ab = 1 \ (\bmod \ m)$なら$(-a)(-b) = 1 \ (\bmod \ m)$でもある - 例: 11と5が$\mathbb{Z}_{27}$におけるお互いの乗法逆元 → $27-11 = 16$ 、$27-5 = 22$もお互いの$\mathbb{Z}_{27}$における乗法逆元 - 結合法則・分配法則を利用する - 例: $2 \cdot_{27} 14 = 1, 4 \cdot_{27} 7 = 1$を利用し - $(2 \cdot_{27} 14) \cdot_{27} (4 \cdot_{27} 7) = 1 \cdot_{27} 1$ ⤵交換・結合 - $(2 \cdot_{27} 4) \cdot_{27} (14 \cdot_{27} 7) = 1 \cdot_{27} 1$ - $8 \cdot_{27} (98 \bmod 27 = 11) = 1$ - 8, 11がお互いに$\mathbb{Z_{27}}$における乗法逆元とわかる 零因子 定義: $a \cdot_m b = 0$を満たす元$b \ (0 \lt b \lt m)$が存在するような元$a \ (0 \lt a \lt m)$のことを[[零因子]]と呼ぶ - 例: $2 \cdot_6 3 = 0$、$3 \cdot_6 4 = 0$より、2, 3, 4は$\mathbb{Z_6}$の零因子 合同 定義: $m$を0より大きい整数とする。2つの整数$a$と$b$が、ある整数$t$を用いて$a = b + mt$と表せるとき(つまり$b + mの倍数$)、$a$と$b$は$m$を法(モジュラス)として合同であるという。 - 例: $55 \equiv 1 \pmod{27}$ 同値関係: mを法とする合同は、[[同値関係]]である。 - [[反射律]]: $a \equiv a \pmod m$ - [[対称律]]: $a \equiv b \pmod m$ならば、$b \equiv a \pmod m$ - [[推移律]]: $a \equiv b \pmod m$かつ$b \equiv c \pmod m$ならば、$a \equiv c \pmod m$ また、もし$a \equiv b \pmod m$かつ$a' \equiv b' \pmod m$ならば、次が成り立つ - 加算: $a + a' \equiv b + b' \pmod m$ - 乗算: $aa' \equiv bb' \pmod m$ というわけで、方程式とかも解ける(kekeho)