モジュラ計算
加算・減算・乗算
定義 $ \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}
反射律: $ 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.icon