[b]このワークシートは[url=https://www.geogebra.org/m/twxxx3yq]Math by Code[/url]の一部です。[br][/b][br][br]整数が偶数と奇数のどちらかのクラスに分けられるというのは便利な考え方です。[br]偶数もたんさんあるし、奇数もたくさんある。[br]でも、偶数は０、奇数は１で代表すると、とても楽になります。[br]それが合同の発想です。[br][br][b][size=150]＜合同式＞[/size][/b][br]偶数、奇数は２で割った余りによる分類でした。[br]４で割った余りは０，１，２，３の４種類のどれかなので、[br]それでクラス分けしましょう。[br]aを４で割った余りとｂで割った余りが等しいとき、合同式「[color=#0000ff][b][size=150]a≡b(mod 4)」と書きます。[br]aとｂのクラスは同じとも言えますね。[br][/size][/b][/color][b][color=#0000ff]（pを[color=#0000ff][b]法ｐ[/b][/color]とか、モジュラスｐとか、ｐで割ったときとか、mod pとか読みます。[color=#0000ff][b]bは剰余。[/b][/color]）[br]この≡記号は＝よりも線が１本増えただけで、ほぼ等式の性質が使えます。[br][/color][/b]くわしく見ていきましょう。[br][br][br][b][size=150]（一般化しよう）[br][/size][/b][color=#0000ff][b][size=150]a-b≡０(mod p）[/size][/b][/color]とかくと、a-bはｐの倍数だ。ｐはa-bを割り切る(divide)[br][b]p｜a-b[/b]ともかけるし、[b](a-b)=pk[/b]ともかけるでしょう。[br][color=#9900ff]実は、これがもともとの合同式の定義でした。[br][/color]整数ｘ，ｙ，ｚに対してｚ|(x-y）が成り立つとき、ｘ≡ｙ(mod z)とかき、[br]ｚを法として、ｘとｙは[b]合同[/b]だという。この式を[b]合同式[/b]と呼ぶ。[br]合同式には３つの性質があり、合同は、同値関係だとわかるね。[br]性質１（反射）ｘ≡ｘ（mod ｎ）[br]性質２（対称）ｘ≡ｙ（mod ｎ）⇒ｙ≡ｘ（mod ｎ)[br]性質３（推移）x≡ｙ（mod ｎ)　∧　y≡ｚ（mod ｎ)　⇒　ｘ≡ｚ（mod ｎ)[br][br]法則（加減乗）２つの合同式の左辺どうし、右辺どうしの和差積は合同だ。[br]　　　[br][br]

[b]≡は＝と同じように、等式の性質が使えることが多い。[br][br][size=150][color=#0000ff][u]質問：≡と＝の同じところ、ちがうとこを調べてみよう。[br][/u][/color][br][/size][/b]移項したり、両辺に同じ数をたしたり、ひいたりできるだけでなく、[br]両辺同じ数をかけたり、[br]左辺どうしの積と右辺同士の積を結ぶことができる。[br]また、平方根も整数の範囲で求めることができる。[br]また、負の値はmod のｐを加えて正の値にすることができます。これはmod の意味から明らか。[br]（例）[br]x≡1(mod7)ならば、2x≡2(mod7)[br]x≡2(mod 7)ならば、7x≡14≡０(mod 7)[br]ｘ-1≡０（mod 7) ならば、x≡1(mod 7)[br]ｘ+6≡1（mod 7) ならば、x≡-5≡-5+7≡ 2(mod 7)[br]ｘ[sup]2[/sup]≡4 (mod 7) ならば、x≡±2≡2, -2+7≡ 2,5(mod 7)[br]・13≡4, 13[sup]2[/sup]≡16≡７≡-2, 13[sup]3[/sup]≡-2･4=-8≡1(mod 9)だから、[br]　13[sup]10000[/sup]≡(13[sup]3[/sup])[sup]3333[/sup]・13≡1･4＝４（mod 9)[br][br][br][b][size=150]＜法と剰余の関係＞[br][/size][/b]ただし、[color=#0000ff][b]等式とちがう部分もある。とくに、割り算だ[/b][/color]。[br][b]ｘ≡1(mod8)[/b]なら、x={1,9,17,25,.....} だから、剰余と法が互いに素なら[color=#0000ff][b]ｘ≡1(mod2, mod4)[/b][/color]となる。[br][b]ｘ≡4(mod 8)[/b]なら、x={4,12,20,28,....} だから、１以外の剰余と法の最大公約数ｄ=4で約すと、[br] x/4={1,3,5,7,....}だから、[b][color=#0000ff]x/4≡4/4(mod 8/4)≡1(mod 2)[br][/color][/b][br][b]ｘ≡6(mod 8)[/b]なら、x={6,14,22,30,....} だから、１以外の剰余と法の公約数d＝2で約すと、[br] x/2={3,7,11,15,....}だから、[color=#0000ff][b]x/2≡6/2(mod 8/2)≡3(mod 4)[/b][/color][br][br][b][size=150]＜合同方程式を解いてみよう＞[br][/size][/b]・1次方程式[b][color=#0000ff][size=150]ax≡b(mod p)　[br][/size][/color][/b]ax - b = np となるｎがある。[br][b]ax + np =b[/b] という、積和の形に直せるね。 [br][br][b][color=#0000ff][size=150]ma≡mb(mod n)　[/size][/color]ｍがｎの倍数でないとき、 両辺をｍで割って約せる。しかし、法については注意！[br][/b] 法ｎもｍの倍数、n=mｃなら、法もｍで約せる。a≡b( mod n/m) [br] そうでないとき（nとｍが互いに素なら）法はそのままだ。a≡b (mod n)[br] [color=#0000ff][b][size=150]一般に、G(m,n)＝ｄとすると、a≡b( mod n/d)[br][/size][/b][/color][br][color=#0000ff][b](例１）「4x≡3(mod 19)」の解は？ x ≡15[br][/b][/color]両辺を5倍する。20x≡(19+1)ｘ≡ x ≡15(mod 19) [br](別解)　3-19=-16。[br]右辺-19で、4x≡-16(mod 19)　両辺を4で約す。ｘ≡-4≡-4+19≡15。[br][color=#0000ff][b](例２）「4x≡16(mod 28)」の解は？ x ≡ 4 (mod 7)[br][/b][/color]係数の最大公約数d=4だから、[br]4x/4≡16/4(mod 28/4)　x≡4(mod 7)[br]x≡4, 4+7, 4 +7+7, 4 + 7+7+7 ( mod 28)[br]x ≡ 4 , 11, 18, 25(mod 28)[br][b][color=#0000ff](例３）「18x≡8(mod 14)」の解は？ x≡2 ,9 (mod 7)[br][/color][/b]剰余と法の最大公約数d=2だから、[br]18x/2≡8/2(mod 14/2)　9x≡4(mod 7)　[br]４≡4+7+7=18(mod 7)から、9x≡18(mod 7) x≡2(mod 7)[br]x≡2, 2+7 (mod 7)から、x≡2,9(mod 14)。 [br]（別解）[color=#0000ff][b][size=150]ax≡b(mod p)を言い換える。[br]ax-py=bの解はax-py=G(a,p)のb/G(a,p)倍。[br]この倍数が整数のときは解がある。[br] [/size][/b][/color]18・４ー14・5=G(18,14)=2だから、8/2＝４倍する。[br]x=4・4=16, y=5・4=20。[br][b]18[/b]・16=[b]14[/b]・20 + [b]8[/b]となる。[br]だから、18・16≡8(mod 14) x=16≡2(mod 14)。[br]他の解は14/2=7を加えて、ｘ＝2+7=9(mod 14)[br][b][color=#0000ff](例４）「35x≡105(mod 225)」の解は？ x≡3(mod 45)[br][/color][/b]両辺は35の倍数になっている。[br]35 と225 の最大公約数は5だから、[br]35x/35≡105/35(mod 225/5)　[br]x≡3(mod 45)[br]x ≡ 3 , 48, 93, 138, 183 (mod 225)[br][color=#0000ff][b](例５）「893x≡266(mod 2432)」の解は？ x≡1106,1234, 1362,........, (mod 2432)[br]G(266,2432)=38[br]G(893,2432)=19[br]893x-2432y=266の解は893x-2432y=G(893,2432)=19の266/19=14倍。[br]「ユークリッドの互除法の逆算」（ABG計算）によって、ｘ，ｙの特殊解は求められるね。[br]（ABG計算の説明は省略。）[br][/b][/color]893・79ー2432・29=19だから、14倍する。[br]x=79・14=1106 y=29・14=406。[br][b]893[/b]・1106 = [b]2432[/b]・406+[b]266[/b]となる。[br]だから、893・1106≡266(mod 2432) [br] x≡1106(mod 2432)。[br][b]2432/19=128を1106に加えていく。[br][/b]pythonの対話モードで調べよう。[br]>>> y=1106[br]>>> for i in range(19):[br]... print(y)[br]... y=y+128[br]... y=y%2432[br]を実行する。[br]異なる解はｘ＝1106+128k(mod 2432)=[br]1106[br]1234[br]1362[br]1490[br]1618[br]1746[br]1874[br]2002[br]2130[br]2258[br]2386[br]82[br]210[br]338[br]466[br]594[br]722[br]850[br]978[br][br][b][color=#0000ff]（例６）6ｘ≡15（mod 514）[b]の解は？なし[/b][br][/color][/b]6x-15は必ず奇数。法の514は偶数。[br]偶数が割り切る奇数はないので、6x-15≡0(mod 514)の解はない。[br][br]・２次方程式[br][color=#0000ff][b](例７）x[sup]2[/sup]+2x≡０(mod 7)[b]の解は？ x ≡ 0, 5 (mod 7)[/b][br][/b][/color]左辺の因数分解で、x[sup]2[/sup]+2x≡x(x+2)≡0(mod 7)から、x≡0, -2≡0,5(mod 7)[br][color=#0000ff][b](例８）x[sup]2[/sup]+2x-1≡０(mod 7)[b]の解は？x≡ 2, 3 (mod 7)[/b][br][/b][/color]左辺-7して因数分解すると、x[sup]2[/sup]+2x-8=(x-2)(x+4)≡0(mod 7)から、x≡2, -4≡2,3(mod 7)[br][b][color=#0000ff](例９）x[sup]2[/sup]≡3(mod 10)[b]の解は？なし[/b][/color][/b][br]x(mod 10)={0,1,2,3,4,5,6,7,8,9}に対して、x[sup]2[/sup](mod 10)={0,1,4,9,6,5,6,9,4,1}から、剰余が３と合同に[br]ならない。だから、解なし。[br][br][color=#0000ff][b]このように、1次合同方程式でも解の数は１つとは限らない。[br]また、１次でも２次でも合同方程式は解なしもありうるね。[br][/b][/color][br][br]

[color=#0000ff][b][size=150]質問：ｐが素数のときに[br][br][size=200](p-1)! + 1 ≡ 0 (mod p)[br][/size][br]という[u]ウィルソンの定理[/u]というものがあります。[br]≡式の考えを使ってなぜそうなるかを考えてみよう。[br][/size][/b][/color][b][size=150]（例）[/size][/b][br]p=2,3,5,7,11のとき、[br](2-1)!+1= 1!+1 =2≡0(mod 2)[br](3-1)!+1= 2!+1 =3≡0(mod 3)[br](5-1)!+1= 4!+1 =25≡0(mod 5)[br](7-1)!+1= 6!+1 =721≡0(mod 7)[br](11-1)!+1= 10!+1 =3628801=329891*11≡0(mod 11)[br][br][b][size=150]（mod7で実験しよう）[/size][/b][br](7-1)!=(7-1)*5*4*3*2*1=(7-1)*(5*3)*(4*2)*1[br]≡(7-1)*1*1*1=7-1(mod 7)[br]だから、(7-1)!+1≡7-1+1=7≡0(mod 7)です。[br]7-1以下の１以上の整数は、単位元が１です。[br]剰余どうしの積が１になるペアは逆元といいますが、[br]同じ数が別のペアと逆元になることはありません。[br]１つの数には１つだけ逆元があります。[br]5*3=15≡１(mod 7)[br]4*2=8≡１(mod 7)[br]ただし、特殊なケースが２つあります。[br]１と６です。[br]1*1≡１(mod 7)[br]6*6=(7-1)*(7-1)≡(-1)*(-1)≡1(mod 7)です。[br]だから、7-1=6個の要素のうち、１と６だけは自分が逆元なので、そのままのこる。[br]のこりの6-2=4要素は4/2=2組の１ができるので、かけ算で１となり消える。[br]だから、[color=#0000ff][b]ウィルソンの定理は(　)!がはずれる定理[/b][/color]と覚えられます。[br][br][b][size=150](一般化してみよう）[/size][/b][br]7を一般の素数pにしたときも同じ論法です。 [br][b][size=150][color=#0000ff](p-1)!=[/color][/size][/b](p-1)*(p-2)*..........*2*1 ( p-1個の偶数個の積）[br]=(p-1)*1* 1*1*......*1 ( 両端以外の（p-1-2）/2個の逆元ペアが１と合同。)[br][b][size=150][color=#0000ff]≡p-1 (mod p)[/color][/size][/b][br]だから、(p-1)!+1≡p-1+1=p≡0 (mod p)　[br]ただし、p=3のときは、(3-1)!=(3-1)*1なので、両端だけで( )!が外れます。[br]また、p=2のときは、(2-1)!=1=2-1だから、先頭の2-1だけそのまま( )!が外れます。