[b][size=150][b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br]＜法だけ乗してみる＞[br][/size][/b]７で割った余りで数を同一視する整数の世界、[br]つまり、mod７でのべき乗計算をしてみる。[br]1[sup]7[/sup]≡1 (mod 7), [br]2[sup]7[/sup]≡2 (mod 7), [br]3[sup]7[/sup]≡3 (mod 7), [br]4[sup]7[/sup]≡4 (mod 7), [br]5[sup]7[/sup]≡5 (mod 7), [br]6[sup]7[/sup]≡6 (mod 7)[br][color=#0000ff][b][color=#0000ff][b][size=150]a[sup]7[/sup]≡a (mod7)[/size][/b][/color]ということだ。[br]aが1から６のどれでも、法と同じ7回かけるaに等しい。合同になる。[br]7乗が1乗と同じと考えることもできるね。[br]つまり、７−１＝6乗分はキャンセルできるということだね。[br][/b][/color]かけ算で何もしない数は１だから、[br]1[sup]6[/sup]≡1 (mod 7), [br]2[sup]6[/sup]≡1 (mod 7), [br]3[sup]6[/sup]≡1 (mod 7), [br]4[sup]6[/sup]≡1 (mod 7), [br]5[sup]6[/sup]≡1 (mod 7), [br]6[sup]6[/sup]≡1 (mod 7)[br][color=#0000ff][b][size=150]a[sup]6[/sup]≡1 (mod7)[/size][/b][/color]ということだ。[br]言い換えると、[br][size=150][b]a[/b][sup]6[/sup][b]ー1は必ず７の倍数になるということだね。[br][color=#0000ff]#[IN]Python[br]#============================================[br]nums =[[/color][/b][color=#0000ff]1, 2, 3, 4, 5, 6][br][b]ferm=[x**6-1 for x in nums ] #[/b]=[/color][/size][color=#0000ff][0, 63, 728, 4095, 15624, 4665][br][b]g = [x % 7 for x in ferm] [br]print(g)[br][/b][b]#============================================[br][/b][OUT][br][/color] [0,0,0,0,0,0][br]どれも７の倍数になっているね。[br][br][color=#0000ff][b][size=200]素数pを法として[br]a[sup]p-1[/sup]≡1 (mod p)[br][/size][/b][/color][br][color=#0000ff][b][size=150][size=200]これが、フェルマーの小定理[br]（Fermat's little theorem)[br][br][/size][/size][/b][/color]これのおかげで、6[sup]22[/sup]を計算しなくても、23で割った余りが１になる。[br]つまり、[b][size=150]6[sup]22[/sup]≡1 (mod23)[br][b][color=#0000ff]#[IN]Python[br]#============================================[/color][/b][br]pow(6,22,23)[br][color=#0000ff][b]#============================================[br][/b][OUT][br][/color][/size][/b]1[br]
ちなみに[br]pythonで、6**22-1≡0(mod 23)をたしかめることもできる。[br][b][size=150][b][color=#0000ff]#============================================[/color][/b][/size][/b][br]res=6**22-1[br]print(res)[br][b][size=150][color=#0000ff][b]#============================================[br][/b][OUT][br][/color][/size][/b]131621703842267135[br][b][size=150][b][color=#0000ff]#============================================[/color][/b][/size][/b][br]res % 23[br][b][size=150][color=#0000ff][b]#============================================[br][/b][OUT][br][/color][/size][/b]0[br][br][color=#0000ff][b][size=150][u]質問：この事例からフェルマーの小定理の便利さを２つ上げください。[br][/u][/size][/b][/color][b][size=150][br]フェルマーの小定理の便利さは、指数を(法-1)だけへらせるとか、[br]何かの(法-1)乗−1をするだけで、法の倍数が作れてしまうとかですね。[br][br]＜たよらないとき＞[/size][/b][br]前回扱った、くりかえし2乗法を使うと、けた溢れしにくい計算で[br]大量のべき乗計算の剰余を、くりかえし2乗した剰余の積に分解して計算できます。[br][color=#0000ff]指数を2進数にする[/color]ことで、かけ算、わり算のけた数を減らそう。[br]22[sub](10)[/sub]=16+4+2=10110[sub](2)[/sub][br]なので、6[sup]16[/sup]まで、指数を[color=#0000ff]倍々した剰余、つまり、剰余の2乗の剰余[/color]を求めよう。[br]6[sup]1[/sup]≡6 (mod 23), [br]6[sup]2[/sup]≡36-23=13 (mod 23), [br]6[sup]4[/sup]≡169-161=8 (mod 23), [br]6[sup]8[/sup]≡64-46=18 (mod 23), [br]6[sup]16[/sup]≡324-23*14=2 (mod 23), [br]6[sup]22[/sup]=6[sup]16+4+2[/sup]=6[sup]16[/sup]･6[sup]4[/sup]･6[sup]2[br][/sup]≡2･8･13 ≡16･13 ≡208-23･9[br]＝1(mod 23)[br][br][b][size=150]＜たよるとき＞[/size][/b][br][b][color=#0000ff]x[sup]103[/sup]≡4(mod 11)のｘは？[br][/color][/b][br]xが未知数のときは、倍々した剰余を求めておく作戦は使えない。[br]そこで、指数を減らすためにフェルマーの小定理にたよってみよう。[br]ｘ[sup]10[/sup]≡1(mod11)と103＝3(mod10)から、x[sup]103[/sup]≡x[sup]3[/sup]≡4(mod11)を解けばよいね。[br]x =[1, 2, 3, 4, [u]5[/u], 6, 7, 8, 9, 10]に対して[br]x[sup]3[/sup](mod11)=[1, 8, 5, 9, [u]4[/u], 7, 2, 6, 3, 10][br]だから、x≡5(mod11)が解だ。[br][color=#0000ff][b]#[IN]julia[br]#============================================[br]# x^k≡b(mod p)[br]k=103[br]p=11[br]b=4[br]# 指数をフェルーの定理で削減してから計算する。[br]# x をすべての剰余にした結果のリストを作る。[br]xms=[powermod(x,k % (p-1),11) for x in 1:p-1][br]# 結果がｂになるものを検索することで、ｘを求める。[br]x=findfirst(isequal(b),xms)[br]print("x^",k,"≡",b,"(mod ",p,")の解x=",x)[br]#============================================[br]#[OUT][br]x^103≡4(mod 11)の解x=5[/b][/color]
ちなみに[br]pythonで、6**22-1≡0(mod 23)をたしかめることもできる。[br][b][size=150][b][color=#0000ff]#============================================[/color][/b][/size][/b][br]res=6**22-1[br]print(res)[br][b][size=150][color=#0000ff][b]#============================================[br][/b][OUT][br][/color][/size][/b]131621703842267135[br][b][size=150][b][color=#0000ff]#============================================[/color][/b][/size][/b][br]res % 23[br][b][size=150][color=#0000ff][b]#============================================[br][/b][OUT][br][/color][/size][/b]0[br][br][color=#0000ff][b][size=150][u]質問：この事例からフェルマーの小定理の便利さを２つ上げください。[br][/u][/size][/b][/color][b][size=150][br]フェルマーの小定理の便利さは、指数を(法-1)だけへらせるとか、[br]何かの(法-1)乗−1をするだけで、法の倍数が作れてしまうとかですね。[br][br]＜たよらないとき＞[/size][/b][br]前回扱った、くりかえし2乗法を使うと、けた溢れしにくい計算で[br]大量のべき乗計算の剰余を、くりかえし2乗した剰余の積に分解して計算できます。[br][color=#0000ff]指数を2進数にする[/color]ことで、かけ算、わり算のけた数を減らそう。[br]22[sub](10)[/sub]=16+4+2=10110[sub](2)[/sub][br]なので、6[sup]16[/sup]まで、指数を[color=#0000ff]倍々した剰余、つまり、剰余の2乗の剰余[/color]を求めよう。[br]6[sup]1[/sup]≡6 (mod 23), [br]6[sup]2[/sup]≡36-23=13 (mod 23), [br]6[sup]4[/sup]≡169-161=8 (mod 23), [br]6[sup]8[/sup]≡64-46=18 (mod 23), [br]6[sup]16[/sup]≡324-23*14=2 (mod 23), [br]6[sup]22[/sup]=6[sup]16+4+2[/sup]=6[sup]16[/sup]･6[sup]4[/sup]･6[sup]2[br][/sup]≡2･8･13 ≡16･13 ≡208-23･9[br]＝1(mod 23)[br][br][b][size=150]＜たよるとき＞[/size][/b][br][b][color=#0000ff]x[sup]103[/sup]≡4(mod 11)のｘは？[br][/color][/b][br]xが未知数のときは、倍々した剰余を求めておく作戦は使えない。[br]そこで、指数を減らすためにフェルマーの小定理にたよってみよう。[br]ｘ[sup]10[/sup]≡1(mod11)と103＝3(mod10)から、x[sup]103[/sup]≡x[sup]3[/sup]≡4(mod11)を解けばよいね。[br]x =[1, 2, 3, 4, [u]5[/u], 6, 7, 8, 9, 10]に対して[br]x[sup]3[/sup](mod11)=[1, 8, 5, 9, [u]4[/u], 7, 2, 6, 3, 10][br]だから、x≡5(mod11)が解だ。[br][color=#0000ff][b]#[IN]julia[br]#============================================[br]# x^k≡b(mod p)[br]k=103[br]p=11[br]b=4[br]# 指数をフェルーの定理で削減してから計算する。[br]# x をすべての剰余にした結果のリストを作る。[br]xms=[powermod(x,k % (p-1),11) for x in 1:p-1][br]# 結果がｂになるものを検索することで、ｘを求める。[br]x=findfirst(isequal(b),xms)[br]print("x^",k,"≡",b,"(mod ",p,")の解x=",x)[br]#============================================[br]#[OUT][br]x^103≡4(mod 11)の解x=5[/b][/color]