モジュラ計算

mod

加算・減算・乗算 定義 ${\mathbb{Z}}_m$を集合$0,1,2,...,m-1$とする。${\mathbb{Z}}_m$における加算${+}_m$、減算${-}_m$、乗算${\cdot }_m$を次のように定義する

• $a{+}_{m}b=(a+b)\mathrm{mod}m$
• $a{-}_{m}b=(a-b)\mathrm{mod}m$
• $a{\cdot }_{m}b=(a\cdot b)\mathrm{mod}m$

乗法逆元 定義 ある整数$a$は、$a{\cdot }_{m}b=(ab\mathrm{mod}m)=1$であるような整数$b$が存在するとき、$m$を法とする乗法逆元をもつという。${\mathbb{Z}}_m$の単元とは、$m$を法とする逆元を持つ整数$a$のことである。

• 例: $3{\cdot }_{7}5=1$より、3は${\mathbb{Z}}_7$に乗法逆元5をもつ。(逆も一緒)
• $m$を法とする逆元のペアを見つけるテクニック
  • $k\mathrm{mod}m=1$の形をした数$k$を因数分解する
    • 例: $55\mathrm{mod}27=1$ → $55=11\cdot 5$ → 11と5は、${\mathbb{Z}}_{27}$におけるお互いの乗法逆元
  • $ab=1(\mathrm{mod}m)$なら$(-a)(-b)=1(\mathrm{mod}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\mathrm{mod}27=11)=1$
        • 8, 11がお互いに${\mathbb{Z}}_{27}$における乗法逆元とわかる 零因子 定義: $a{\cdot }_{m}b=0$を満たす元$b(0<b<m)$が存在するような元$a(0<a<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(\mathrm{mod}27)$ 同値関係: mを法とする合同は、同値関係である。
• 反射律: $a\equiv a(\mathrm{mod}m)$
• 対称律: $a\equiv b(\mathrm{mod}m)$ならば、$b\equiv a(\mathrm{mod}m)$
• 推移律: $a\equiv b(\mathrm{mod}m)$かつ$b\equiv c(\mathrm{mod}m)$ならば、$a\equiv c(\mathrm{mod}m)$ また、もし$a\equiv b(\mathrm{mod}m)$かつ$a^{\prime }\equiv b^{\prime }(\mathrm{mod}m)$ならば、次が成り立つ
• 加算: $a+a^{\prime }\equiv b+b^{\prime }(\mathrm{mod}m)$
• 乗算: $a{a}^{\prime }\equiv b{b}^{\prime }(\mathrm{mod}m)$ というわけで、方程式とかも解ける(kekeho)