[b][size=150]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/size][/b][br]フェルマーの小定理から、[br]底が既知のときは、法が素数ｐなら、p-1乗が１と合同であることが使えるね。[br][b][size=150]＜大きい指数の剰余を求める＞[br][/size][/b][color=#0000ff]（例）指数が大きめ[/color][br]「　[math]９^{7777}≡x(mod73)[/math]のｘ」は？[br]９は73の倍数ではないから、フェルマーの小定理が使えるね。[br]73-1=72で、　[math]９^{72}≡1(mod73)[/math]　。左辺と同じ表現を作り、１に置き換えることで指数を激減できる。[br]7777=72･108+1だから、[br][math]９^{7777}≡9^{72\cdot108+1}=\left(9^{72}\right)^{108}\cdot9^1\equiv9^1\equiv9(mod73)[/math]　[br]だから、x=9。[br][b][size=150][br]＜指数も底も大きいときの剰余＞[/size][/b][br][color=#0000ff]（例）底が合成数[/color][br]「[math]100^{1001}≡x(mod23)[/math]のｘ」は？[br][color=#0000ff]底が合成数なので分解しよう。[br][/color] [math]100^{1001}=\left(10^2\right)^{1001}=10^{2002}=2^{2002}\cdot5^{2002}\equiv x\left(mod23\right)[/math][br]2002=22･91 だから、[br][math]2^{2002}\cdot5^{2002}=\left(2^{22}\right)^{91}\cdot\left(5^{22}\right)^{91}\equiv1\cdot1=1\equiv x\left(mod23\right)[/math][br]x=1。[br][color=#0000ff]（例）底が素数[/color][br]「　[math]37^{90}≡x(mod23)[/math]のｘ」は？[br] 90=22･4+2、37=23+14。[br]これから、[math]37^{90}\equiv\left(37^{22}\right)^4\cdot37^2\equiv37^2\equiv14^2=196=23\cdot8+12\equiv12\left(mod23\right)[/math][br]x=12。[br][color=#0000ff]（一般論を考えよう）[br][/color]底が合成数でもなく底のサイズも指数も大きいときは、どうするか[br][b][size=150]a[sup]b[/sup](mod23)を求めたいとき、底も指数も剰余を求めよう。[br]b=22c+d[br]a=23e+f [br][/size][/b][color=#0000ff][b][size=200]a[sup]b[/sup](mod23)≡a[sup]d[/sup](mod23)≡(23e+f)[sup]d[/sup](mod23)[br]≡f[sup]d[/sup](mod23)[br][/size][/b][/color]二項定理から、f[sup]d[/sup]以外すべて23の倍数の項だから０。[br][br]dは22未満なので、dは５桁以下の２進数になるね。d=hijkl[sub](2)[br][/sub]lが１ならf[sup]1[/sup](mod23)≡8をたてる。[br]kが１ならf[sup]2[/sup](mod23)≡8[sup]2[/sup]≡18をたてる。[br]jが１ならf[sup]4[/sup](mod23)≡18[sup]2[/sup]≡2をたてる。[br]iが１ならf[sup]8[/sup](mod23)≡2[sup]2[/sup]≡4をたてる。[br]hが１ならf[sup]16[/sup](mod23)≡4[sup]2[/sup]≡13をたてる。[br]だから、f[sup]d[/sup](mod23)≡13[sup]h[/sup]・４[sup]i[/sup]・２[sup]j[/sup]・18[sup]k[/sup]・８[sup]l[/sup](mod 23)[br]hijklのうち0があれば0乗は１だ。だから、最悪でも(13・4・２・18・8 )÷23の計算をするだけ。[br]これで、桁爆発がおきにくくなるでしょう。[br][br][b][size=150]＜大きい法の剰余＞[br][/size][/b][color=#0000ff]（例）法の素数が大きめ[br][/color]「　[math]2^{2000}≡x(mod2003)[/math]のｘ」は？[br]2003は素数だから、フェルマーの小定理から[br][math]2^{2002}\equiv1\left(mod2003\right)[/math][br]2002-2000=2だから、xに２を２乗したもの、４をかけると1と剰余は1と合同になる。[br]4x≡1（2003)を解く。[br]1≡1+2003=2004と４の倍数にすれば４割れるね。[br]x≡2004÷4=501(mod2003)[br]。[br]

フェルマーの小定理を論理式でかこう。[br]F：整数pと[b][color=#0000ff]pの倍数でない整数a[/color][/b]に対して、「ｐが素数」ならば「a[sup]p-1[/sup]≡1(mod p)」[br]ベン図でかくと、「素数pの集合[b]P[/b]」を「a[sup]p-1[/sup]≡1(mod p)となる数ｐの集合[b]F[/b]」が包んでいる図になる。[br][size=200][color=#0000ff][b]FはPより、ゆるい、広い[/b][/color][/size]というイメージで関係をつかもう。[br][br]逆F：整数pとpの倍数でない整数aに対して、「a[sup]p-1[/sup]≡1(mod p)」ならば「ｐが素数」[br]対偶F:整数pとpの倍数でない整数aに対して、[color=#0000ff][b]「a[sup]p-1[/sup]≡1(mod p)でない」ならば「ｐが素数でない」[/b][/color][br]Fが真であることと、対偶Fが真であることは同値だね。[br]だから、フェルマーの小定理は[color=#0000ff][b]対偶の形式[/b][/color]でも使える。Fに入らない数は当然Pに入らない。[br]しかし、[color=#0000ff][b]逆は成り立つとは限らない[/b][/color]。Fに入る数でも、Pでない数がありうる。[br]だから、フェルマーの小定理は[u][b]「素数でない判定」[/b]には使えるけれど、[b]「素数の判定」[/b]には使えない[/u]。[br][br][size=150][b]＜素数でない判定には使える＞[br][/b][size=100]判定するまでもなく、「[color=#0000ff][b]aがpの倍数[/b][/color]」だと、フェルマーの定理はなりたたない。[br]たとえば、p=3で、a=15としよう。15[sup]2[/sup]=225≡0(mod3）となり、３で割った剰余は１にならない。[br]これは、素数かどうかの判定というよりも、前提条件を満たしていないというだけのこと。[br]言い換えると、「pが素数ではない判定」をしたいならば「aは[color=#0000ff][b]ｐの倍数でないなら何でもよい[/b][/color]。」[br]ということだ。a=2のようにべき乗を計算しやすいものがおすすめ。[br][br][color=#0000ff]（例）「213が素数でない判定」は？[br][/color]2[sup]212[/sup]のmod213による剰余が１でないことだ。[br]2は何乗しても法の213の倍数にならない。[br]212を割れないときは１引き、２のべきで割る。[br]212を２のべき乗の和に分解して、2進数の発想で計算してもよいが、[br]2進数にしたときの桁数が多いため、前段階の計算がわりと必要になる。[br]212=53･4。53-1=13･4, 13-1=3･4。[br]だから、4乗か2倍の計算でそのつど、剰余にして桁減らしを繰り返すことにしてみる。[br][/size][/size]2[sup]12[/sup]=(2[sup]3[/sup])[sup]4[/sup]=(64)[sup]2[/sup]≡49(mod213)[br]2[sup]52[/sup]=(2[sup]13[/sup])[sup]4[/sup]＝(2[sup]12[/sup]･２)[sup]4[/sup]≡(49・2)[sup]4[/sup]≡9604[sup]2[/sup]≡19[sup]2[/sup]≡361≡148≡-65(mod213)[br][size=150][size=100]2[sup]212[/sup]=(2[sup]53[/sup][/size][/size])[sup]4[/sup]=[size=150][size=100](2[sup]52[/sup]・2[/size][/size])[sup]4[/sup]≡(-65・2)[sup]4[/sup]≡(-130)[sup]4[/sup]≡(83[sup]2[/sup])[sup]2[/sup]≡(6889)[sup]2[/sup]≡(73)[sup]2[/sup]≡5329≡4(mod213)[br][b][color=#0000ff]2[sup]212[/sup]≡４(mod213）[/color][/b]だから、剰余が１でない。[br]だから、「213は素数でない判定」は成り立つ。[br]実際213=3×71。[br][br][size=150][size=100][color=#0000ff]（例）「223が素数でない判定」は？[br][/color]2[sup]222[/sup]がmod223の剰余が１でないことを求めよう。[br]2は何乗しても法の223の倍数にならない。[br]222を割れないときは１引き、２のべきで割る。[br]222=111･2。111-1=55･2, 55-1=27･2。27-1=13・2, 13-1=3･4。[br]だから、2乗か2倍の計算でそのつど、剰余にして桁減らしを繰り返すことにしてみる。[br][/size][/size]2[sup]12[/sup]=(2[sup]3[/sup])[sup]4[/sup]=(64)[sup]2[/sup]≡82(mod223)[br]2[sup]54[/sup]=((2[sup]13[/sup])[sup]2[/sup]･２)[sup]2[/sup]＝((82[sup][/sup]･２)[sup]2[/sup]･２)[sup]2[/sup]≡(164[sup]2[/sup]・2)[sup]2[/sup]≡((-59)[sup]2[/sup]･2)[sup]2[/sup]≡6962[sup]2[/sup]≡49[sup]2[/sup]≡2401≡171(mod223)[br][size=150][size=100]2[sup]222[/sup]=((2[sup]54[/sup]・2[/size][/size])[sup]2[/sup]・2)[sup]2[/sup][size=150][size=100]=((171・2[/size][/size])[sup]2[/sup]・2)[sup]2[/sup]≡[size=150][size=100](119[sup]2[/sup]・[/size][/size]2)[sup]2[/sup]≡(112・2)[sup]2[/sup]≡224[sup]2[/sup]≡1(mod223)[br][b][color=#0000ff]2[sup]222[/sup]≡1(mod223）[/color][/b]だから、剰余が１。[br]だから、「223は素数でない判定」は成立しない。[br]しかし、素数でない判定が成立しないからといって、素数だとも言い切れない。[br]たまたま、223は素数だけれど、上記の計算結果がそれを正当化しているわけではない。[br]サルは人間に似ているけど、人間でない動物だ。[br]素数の可能性の条件にはあうのに、素数でない数というものがある。[br][br]それを次にみていこう。

人間のようで、人間でない動物がいるように、[br]素数の可能性の条件に合格しても、素数でない数がある。[br]フェルマーの小定理の後件にあうのに、前件にあわない数だ。[br]pの倍数でないaに対して「a[sup]p-1[/sup]≡1(mod p)」なのに「素数でない」数ｐもある。[br][b][size=150]＜擬素数＞[/size][/b][br][color=#0000ff]擬素数[pseudo prime, almost prime][/color][br]aの選び方によってはp-1乗の剰余が１になったり１でなかったりする数もある。[br]たとえば、341は31･11だから、合成数だ。[br]でも、2[sup]340[/sup]≡1(mod 341)[br]しかし、3[sup]340[/sup]≡56(mod341)[br]（計算は省略した。指数を2進化して、そのつど法で割った剰余にし、最後に掛け算して、[br]剰余をもとめればよいね。）[br]底の選び方によって変わってくる。[br]341は擬素数と呼ばれる。[br]#[IN]julia[br]#=========================================[br]#341=33*11[br]#でも、2^340≡1(mod 341)[br]#しかし、3^340≡56(mod341)[br]println("2^340 mod 341 =", powermod(2,340,341))[br]println("3^340 mod 341 =", powermod(3,340,341))[br]#=========================================[br][OUT][br]2^340 mod 341 =1[br]3^340 mod 341 =56[br][b][size=150]＜カーマイケル数＞[/size][/b][br][color=#0000ff][b][size=150]しかし、aの選び方を変えてもｐの倍数以外なら、いつでも１になるという、[br]超まぎらわしい数もある。つまり、オイラーの小定理の対偶によって、素数の可能性がないという判定ができないのに、素数ではない数だ。[br]それが、カーマイケル数。[br]たとえば、561=3･11･17だ。[/size][/b][/color][br][br]３，１１，１７は素数だから、フェルマーの小定理から[br]aが3,11,17の倍数でないなら、[br]a[sup]2[/sup]≡1(mod3),　a[sup]10[/sup]≡1(mod11),　a[sup]16[/sup]≡1(mod17)[br]a[sup]560[/sup]≡(a[sup]2[/sup])[sup]280[/sup]≡1(mod3),　a[sup]560[/sup]≡(a[sup]10[/sup])[sup]56[/sup]≡1(mod11),　a[sup]560[/sup]≡(a[sup]16[/sup])[sup]35[/sup]≡1(mod17)[br]だから、a[sup]560[/sup]≡1(mod561)となる。[br][br]a[sup]561[/sup]≡a(mod561)の形にすれば、aはすべての数で成り立つことになるね。[br][b][size=150][color=#0000ff]561=3･11･17に対して、2,10,16が560の約数になっていたから、カーマイケル数になった。[br]だから、C=p･q･rに対して、p-1,q-1,r-1がC-1の約数になっていればカーマイケル数になれるね。[br][/color][/size][/b][br]10000以下では[br]561=3･11･17で2,10,16が560の約数。[br]1105=5･13･17で4,12,16が1104の約数。[br]1729=7･13･19で6,12,18が1728の約数。[br]2465=5･17･29で4,16,28が2464の約数。[br]2821=7･13･31で6,12,30が2820の約数。[br]6601=7･23･41で6,22,40が6600の約数。[br]8911=7･19･67で6,18,66が8910の約数。[br]の7個ある。[br][br]・カーマイケル数は奇数だ。[br]カーマイケル数なら、a[sup]n[/sup]≡a(mod n)。a=-1のとき、(-1)[sup]n[/sup]≡-1(mod n)[br]これから、nは奇数。[br][br][size=150][u][b][color=#0000ff]質問：1000以下の素数を使ったカーマイケル数を作り、小さい順にならべるにはどうしたらよいでしょうか。[br][/color][/b][/u][/size][size=150][size=100]素数リストから小さい順に３数a,b,cを取り出しその積mickel=a・b・cを[br]a-1,b-1,c-1で割った剰余の和が0ならば、カーマイケル数のリストmickelsにmickelを追加しましょう。[br][/size][/size][color=#0000ff]#[IN]Python[br]#=============================================================[br]from itertools import combinations[br]lim=1000[br]divCount=lambda n:len(list(filter(lambda m:n % m==0, list(range(1,n+1)))))[br]M=list(range(1,lim))[br]P=[x for x in M if divCount(x)==2][br]mickels=[][br]for a,b,c in combinations(P, 3):[br] mickel = a*b*c[br] if (mickel-1) % (a-1) + (mickel-1) % (b-1) + (mickel-1) % (c-1) ==0 :[br] mickels.append(mickel)[br]mickels.sort()[br]print(mickels)[br]#=============================================================[br][/color]#[OUT][br][561, 1105, 1729, 2465, 2821, 6601, 8911, [br]10585, 15841, 29341, 46657, 52633, 115921, [br]162401, 252601, 294409, 314821, 334153, 399001, 410041, 488881, 512461, 530881, [br]1024651, 1152271, 1193221, 1461241, 1615681, 1857241, 1909001, 2508013, 3057601, 3828001, 4335241, 5049001, 5148001, 5444489, 6189121, 6733693, 6868261, 7519441, 9439201, [br]10024561, 10267951, 11972017, 14469841, 14676481, 15829633, 17098369, 17236801, 19384289, 29111881, 31405501, 34657141, 37964809, 50201089, 56052361, 64377991, 68154001, 79624621, 82929001, 92625121, [br]116682721, 118901521, 172947529, 216821881]