数学に「法の世界」と言うものがある(主に暗号分野で)。
簡単に言えば我々が日常的に使っている時間の概念がそれで、例えば、今が午後の1時だったとして、13時間後は何時ですか? と言うと午前の2時だ。
つまり12時間を基調として、表現したり指し示したりする数字が順繰りになる世界が「数学における法の世界」となる。
この場合、「12を法とする世界」と言う。
これは我々の生活の時間がそうなのであって、数学の考え方的には、12であってもなくてもいい。自然数だったらなんでもいい。
例えば、7を法とする世界だったら{0,1,2,3,4,5,6}の7つの数字の集合になる。
「7を法とする世界」であるこの場合、3+1=4だが、3+4や5+6などは順繰りになるので、7を超えることがない。ちなみに時計の世界と同じく、「7を法とする世界」では7を基調にして繰り越すので、3+4=0,5+6=4だ(数えてみよう)。
上記は足し算だったが、掛け算、乗算でも同じである。
3×2=6、3×4=5、3^2=2、3^4=4である。
要は得られた結果に対し、その法の基調となっている数字で割り算をして、その余りを求めればいい。
さて問題はこの世界にも「割り算」があることだ。
割り算は割り算でかなり事情がややこしい。
例えば上記の
3×2=6(3に2をかけたら何になるか=6)
は
6÷2=3(6を2で割ったら何になるか=3)
に変形できるが、これと同様に
3×4=5(3に4をかけたら何になるか=本来は12だが、7を法とする世界なので、7で割って余りが5)
は
5÷4=3(5を4で割ったら何になるか=3)
となるのだが、推測するのは単純計算では困難だ。
要は、この数字が余りとして存在しましたよ(5)、さて、これはとある掛け算の結果で出た数字ですが、その掛け算の片方で割ったら(4)、元の数字が出ますよね(3)。この元の数字はなんでしょう? と言った具合だ。
しかし数学的にはこれを一般解として導出しなければいけない。
ここでちょっとややこしいが一つのツールを使う。
フェルマーの小定理である。
詳しい説明はWikipediaを見て欲しいが、aとpが互いに素の時、
Pを法とする世界では
a^(p−1)≡1
なのである。
具体的に言えば、例えば7を法とする世界において
a=2,3,4,5,6のいずれも
a^(p−1)の結果は1である。
例)
a=2
2^(7−1)=2^6=64→1
a=3
3^(7−1)=3^6=729→1
a=4
4^(7−1)=4^6=4096→1
a=5
5^(7−1)=5^6=15625→1
a=6
6^(7−1)=6^6=46656→1
これは便利だ。
これを×1としてa^(p−1)を使用する(後ほど変形)。
例えば、7を法とする世界において、1/2はなんであるかというと、
1/2=1×(2)^(−1)となるが
1=a^(p−1)
を変形し、両辺にaを割ると、
a^(−1)=a^(p−2)
になる。
上記の場合、7を法とする世界なので、
1/2=1×(2)^(−1)=1×2^(7−2)=32=4
となる。
更に戻って
5÷4の例に戻ると(手動で数えると答えは3)
5/4=5×(4)^(−1)=5×4^(7−2)=5120=3
で正しい答えが出た。
応用例題)
1)31を法とする世界(F31)で3/24を求めよ。
3/24=3・((24)^-1)=3・(24^(31-2))=3・(24^(29))
=3・10620036506406716776157242913621199028224
=31860109519220150328471728740863597084672
=4
2)31を法とする世界(F31)で17^-3を求めよ。
フェルマーの小定理を変形する。
1=a^(p-1)
a^-1=a^(p-2)
a^-2=a^(p-3)
a^-3=a^(p-4)
(一般解はa^-n=a^(p-(n+1)))
17^-3=17^(31-4)=17^27=1667711322168688287513535727415473
=29
3)31を法とする世界(F31)で4^-4・11を求めよ。
上記一般解より
11・4^-4=11・4^(31-5)=11・4^26=11・4503599627370496=49539595901075456
=13
※追記
「xを法とする世界」のxは素数を使用することが多い。
素数の方が便利だからである。
と言うのも、フェルマーの小定理a^(p−1)≡1では、aとpは互いに素でなければならない。
つまり、約数において共通で保持しているものがあってはならない、と言う条件があるので、6と55などの組み合わせが可能だ。
だが、これだといちいち「公約数はあったっけ」と検査するのが面倒である。
よって、そういう検査がそもそも必要ない素数を使用するのが便利だということである。
簡単に言えば我々が日常的に使っている時間の概念がそれで、例えば、今が午後の1時だったとして、13時間後は何時ですか? と言うと午前の2時だ。
つまり12時間を基調として、表現したり指し示したりする数字が順繰りになる世界が「数学における法の世界」となる。
この場合、「12を法とする世界」と言う。
これは我々の生活の時間がそうなのであって、数学の考え方的には、12であってもなくてもいい。自然数だったらなんでもいい。
例えば、7を法とする世界だったら{0,1,2,3,4,5,6}の7つの数字の集合になる。
「7を法とする世界」であるこの場合、3+1=4だが、3+4や5+6などは順繰りになるので、7を超えることがない。ちなみに時計の世界と同じく、「7を法とする世界」では7を基調にして繰り越すので、3+4=0,5+6=4だ(数えてみよう)。
上記は足し算だったが、掛け算、乗算でも同じである。
3×2=6、3×4=5、3^2=2、3^4=4である。
要は得られた結果に対し、その法の基調となっている数字で割り算をして、その余りを求めればいい。
さて問題はこの世界にも「割り算」があることだ。
割り算は割り算でかなり事情がややこしい。
例えば上記の
3×2=6(3に2をかけたら何になるか=6)
は
6÷2=3(6を2で割ったら何になるか=3)
に変形できるが、これと同様に
3×4=5(3に4をかけたら何になるか=本来は12だが、7を法とする世界なので、7で割って余りが5)
は
5÷4=3(5を4で割ったら何になるか=3)
となるのだが、推測するのは単純計算では困難だ。
要は、この数字が余りとして存在しましたよ(5)、さて、これはとある掛け算の結果で出た数字ですが、その掛け算の片方で割ったら(4)、元の数字が出ますよね(3)。この元の数字はなんでしょう? と言った具合だ。
しかし数学的にはこれを一般解として導出しなければいけない。
ここでちょっとややこしいが一つのツールを使う。
フェルマーの小定理である。
詳しい説明はWikipediaを見て欲しいが、aとpが互いに素の時、
Pを法とする世界では
a^(p−1)≡1
なのである。
具体的に言えば、例えば7を法とする世界において
a=2,3,4,5,6のいずれも
a^(p−1)の結果は1である。
例)
a=2
2^(7−1)=2^6=64→1
a=3
3^(7−1)=3^6=729→1
a=4
4^(7−1)=4^6=4096→1
a=5
5^(7−1)=5^6=15625→1
a=6
6^(7−1)=6^6=46656→1
これは便利だ。
これを×1としてa^(p−1)を使用する(後ほど変形)。
例えば、7を法とする世界において、1/2はなんであるかというと、
1/2=1×(2)^(−1)となるが
1=a^(p−1)
を変形し、両辺にaを割ると、
a^(−1)=a^(p−2)
になる。
上記の場合、7を法とする世界なので、
1/2=1×(2)^(−1)=1×2^(7−2)=32=4
となる。
更に戻って
5÷4の例に戻ると(手動で数えると答えは3)
5/4=5×(4)^(−1)=5×4^(7−2)=5120=3
で正しい答えが出た。
応用例題)
1)31を法とする世界(F31)で3/24を求めよ。
3/24=3・((24)^-1)=3・(24^(31-2))=3・(24^(29))
=3・10620036506406716776157242913621199028224
=31860109519220150328471728740863597084672
=4
2)31を法とする世界(F31)で17^-3を求めよ。
フェルマーの小定理を変形する。
1=a^(p-1)
a^-1=a^(p-2)
a^-2=a^(p-3)
a^-3=a^(p-4)
(一般解はa^-n=a^(p-(n+1)))
17^-3=17^(31-4)=17^27=1667711322168688287513535727415473
=29
3)31を法とする世界(F31)で4^-4・11を求めよ。
上記一般解より
11・4^-4=11・4^(31-5)=11・4^26=11・4503599627370496=49539595901075456
=13
※追記
「xを法とする世界」のxは素数を使用することが多い。
素数の方が便利だからである。
と言うのも、フェルマーの小定理a^(p−1)≡1では、aとpは互いに素でなければならない。
つまり、約数において共通で保持しているものがあってはならない、と言う条件があるので、6と55などの組み合わせが可能だ。
だが、これだといちいち「公約数はあったっけ」と検査するのが面倒である。
よって、そういう検査がそもそも必要ない素数を使用するのが便利だということである。