情報数学1 第1-3章

情報数学１第2-2章
合同式の逆元と応用
香川大学工学部富永浩之
[email protected]
第01節 [1] 合同式における逆元の定義
法nにおいて、a×b≡1 となるとき、
bはaの逆元といい、a~ と書く。
aとbが互いに逆元であることは a⇔b と書く。
任意の法nにおいて 1×1≡1 より 1~≡1
逆元は必ずしも存在するとは限らない
任意の法nにおいて 0×□≡0 なので、0に逆元は存在しない
法
法
法
法
法
3
4
4
5
5
で
で
で
で
で
2×2≡1 より 2~≡2
2×2≡0, 2×3≡2 より、2 の逆元は存在しない
3×3≡1 より 3~≡3
2×3≡1 より 2~≡3 また 3~≡2
4×4≡1 より 4~≡4
第01節 [2] 逆元の存在条件と零因子
● 逆元の存在条件
a⊥n のとき
法nにおけるaの逆元が存在する
このようなaを可逆元という
a⊥n でないとき
法nにおけるaの逆元は存在しない
a×b≡0 となる、0でないbが存在
このようなaを零因子という
● 逆元と零因子
法nが素数のとき、1～n-1 の全てが、可逆元
法nが合成数のとき、a⊥n のとき、可逆元
a⊥n でないとき、零因子
1  1  2  6  3  4  5  9  7  8  10  10  1
第01節 [3] 逆元の一覧
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
2
3
4
5
2
3
4
3
2
5
3
5
6
7
7
7
4
9
5
8
3
10
5
3
5
2
9
5
8
3
4
11
7
8
9
10
11
12
13
14
15
例えば、法11の行を横に見ると、
1×1≡2×6≡3×4≡5×9≡7×8≡10×10≡1
4
2
6
13
6
2
11
7
4
3
8
7
2
13
7
8
7
5
9
5
3
11
2
9
10
4
11
6
9
11
3
12
13
7
5
14
15
第02節 [1] 逆元を求める素朴な方法
法 nにおいて、aの逆元を求めるとき、まず[0]を確認し、
逆元が存在するなら、[1]または[2]の方法を用いる。
[0] 法n とaが互いに素でなければ、逆元は存在しない。
[1] aの倍数列を列挙し、nによる剰余が1になるものを探す。
実際には、aの倍数列は、法nで考えればよい。
[2] nの倍数列を列挙し、それに1を加えて
aで割り切れるものを探す。
法19で8の逆元
8×2≡16, 8×3≡5, 8×4≡13, 8×5≡2, 8×6≡10, 8×7≡18, 8×8≡7,
8×9≡15, 8×10≡4, 8×11≡12, 8×13≡1 より 8~≡13
19の倍数+1 で考えると、1, 20, 39, 58, 77, 96 で
96%8＝0, 96@8＝12
で 8~≡13
第09節 [1] 大きな逆元の求め方
第10節 [1] 合同式の応用

Download Report