≡はmagic
1.≡という魔法
このワークシートはMath by Codeの一部です。
整数が偶数と奇数のどちらかのクラスに分けられるというのは便利な考え方です。
偶数もたんさんあるし、奇数もたくさんある。
でも、偶数は0、奇数は1で代表すると、とても楽になります。
それが合同の発想です。
<合同式>
偶数、奇数は2で割った余りによる分類でした。
4で割った余りは0,1,2,3の4種類のどれかなので、
それでクラス分けしましょう。
aを4で割った余りとbで割った余りが等しいとき、合同式「a≡b(mod 4)」と書きます。
aとbのクラスは同じとも言えますね。
(pを法pとか、モジュラスpとか、pで割ったときとか、mod pとか読みます。bは剰余。)
この≡記号は=よりも線が1本増えただけで、ほぼ等式の性質が使えます。
くわしく見ていきましょう。
(一般化しよう)
a-b≡0(mod p)とかくと、a-bはpの倍数だ。pはa-bを割り切る(divide)
p|a-bともかけるし、(a-b)=pkともかけるでしょう。
実は、これがもともとの合同式の定義でした。
整数x,y,zに対してz|(x-y)が成り立つとき、x≡y(mod z)とかき、
zを法として、xとyは合同だという。この式を合同式と呼ぶ。
合同式には3つの性質があり、合同は、同値関係だとわかるね。
性質1(反射)x≡x(mod n)
性質2(対称)x≡y(mod n)⇒y≡x(mod n)
性質3(推移)x≡y(mod n) ∧ y≡z(mod n) ⇒ x≡z(mod n)
法則(加減乗)2つの合同式の左辺どうし、右辺どうしの和差積は合同だ。
互除法
ABG法
ウィルソンの確認
2.≡と=を比べる
≡は=と同じように、等式の性質が使えることが多い。
質問:≡と=の同じところ、ちがうとこを調べてみよう。
移項したり、両辺に同じ数をたしたり、ひいたりできるだけでなく、
両辺同じ数をかけたり、
左辺どうしの積と右辺同士の積を結ぶことができる。
また、平方根も整数の範囲で求めることができる。
また、負の値はmod のpを加えて正の値にすることができます。これはmod の意味から明らか。
(例)
x≡1(mod7)ならば、2x≡2(mod7)
x≡2(mod 7)ならば、7x≡14≡0(mod 7)
x-1≡0(mod 7) ならば、x≡1(mod 7)
x+6≡1(mod 7) ならば、x≡-5≡-5+7≡ 2(mod 7)
x2≡4 (mod 7) ならば、x≡±2≡2, -2+7≡ 2,5(mod 7)
・13≡4, 132≡16≡7≡-2, 133≡-2・4=-8≡1(mod 9)だから、
1310000≡(133)3333・13≡1・4=4(mod 9)
<法と剰余の関係>
ただし、等式とちがう部分もある。とくに、割り算だ。
x≡1(mod8)なら、x={1,9,17,25,.....} だから、剰余と法が互いに素ならx≡1(mod2, mod4)となる。
x≡4(mod 8)なら、x={4,12,20,28,....} だから、1以外の剰余と法の最大公約数d=4で約すと、
x/4={1,3,5,7,....}だから、x/4≡4/4(mod 8/4)≡1(mod 2)
x≡6(mod 8)なら、x={6,14,22,30,....} だから、1以外の剰余と法の公約数d=2で約すと、
x/2={3,7,11,15,....}だから、x/2≡6/2(mod 8/2)≡3(mod 4)
<合同方程式を解いてみよう>
・1次方程式ax≡b(mod p)
ax - b = np となるnがある。
ax + np =b という、積和の形に直せるね。
ma≡mb(mod n) mがnの倍数でないとき、 両辺をmで割って約せる。しかし、法については注意!
法nもmの倍数、n=mcなら、法もmで約せる。a≡b( mod n/m)
そうでないとき(nとmが互いに素なら)法はそのままだ。a≡b (mod n)
一般に、G(m,n)=dとすると、a≡b( mod n/d)
(例1)「4x≡3(mod 19)」の解は? x ≡15
両辺を5倍する。20x≡(19+1)x≡ x ≡15(mod 19)
(別解) 3-19=-16。
右辺-19で、4x≡-16(mod 19) 両辺を4で約す。x≡-4≡-4+19≡15。
(例2)「4x≡16(mod 28)」の解は? x ≡ 4 (mod 7)
係数の最大公約数d=4だから、
4x/4≡16/4(mod 28/4) x≡4(mod 7)
x≡4, 4+7, 4 +7+7, 4 + 7+7+7 ( mod 28)
x ≡ 4 , 11, 18, 25(mod 28)
(例3)「18x≡8(mod 14)」の解は? x≡2 ,9 (mod 7)
剰余と法の最大公約数d=2だから、
18x/2≡8/2(mod 14/2) 9x≡4(mod 7)
4≡4+7+7=18(mod 7)から、9x≡18(mod 7) x≡2(mod 7)
x≡2, 2+7 (mod 7)から、x≡2,9(mod 14)。
(別解)ax≡b(mod p)を言い換える。
ax-py=bの解はax-py=G(a,p)のb/G(a,p)倍。
この倍数が整数のときは解がある。
18・4ー14・5=G(18,14)=2だから、8/2=4倍する。
x=4・4=16, y=5・4=20。
18・16=14・20 + 8となる。
だから、18・16≡8(mod 14) x=16≡2(mod 14)。
他の解は14/2=7を加えて、x=2+7=9(mod 14)
(例4)「35x≡105(mod 225)」の解は? x≡3(mod 45)
両辺は35の倍数になっている。
35 と225 の最大公約数は5だから、
35x/35≡105/35(mod 225/5)
x≡3(mod 45)
x ≡ 3 , 48, 93, 138, 183 (mod 225)
(例5)「893x≡266(mod 2432)」の解は? x≡1106,1234, 1362,........, (mod 2432)
G(266,2432)=38
G(893,2432)=19
893x-2432y=266の解は893x-2432y=G(893,2432)=19の266/19=14倍。
「ユークリッドの互除法の逆算」(ABG計算)によって、x,yの特殊解は求められるね。
(ABG計算の説明は省略。)
893・79ー2432・29=19だから、14倍する。
x=79・14=1106 y=29・14=406。
893・1106 = 2432・406+266となる。
だから、893・1106≡266(mod 2432)
x≡1106(mod 2432)。
2432/19=128を1106に加えていく。
pythonの対話モードで調べよう。
>>> y=1106
>>> for i in range(19):
... print(y)
... y=y+128
... y=y%2432
を実行する。
異なる解はx=1106+128k(mod 2432)=
1106
1234
1362
1490
1618
1746
1874
2002
2130
2258
2386
82
210
338
466
594
722
850
978
(例6)6x≡15(mod 514)の解は?なし
6x-15は必ず奇数。法の514は偶数。
偶数が割り切る奇数はないので、6x-15≡0(mod 514)の解はない。
・2次方程式
(例7)x2+2x≡0(mod 7)の解は? x ≡ 0, 5 (mod 7)
左辺の因数分解で、x2+2x≡x(x+2)≡0(mod 7)から、x≡0, -2≡0,5(mod 7)
(例8)x2+2x-1≡0(mod 7)の解は?x≡ 2, 3 (mod 7)
左辺-7して因数分解すると、x2+2x-8=(x-2)(x+4)≡0(mod 7)から、x≡2, -4≡2,3(mod 7)
(例9)x2≡3(mod 10)の解は?なし
x(mod 10)={0,1,2,3,4,5,6,7,8,9}に対して、x2(mod 10)={0,1,4,9,6,5,6,9,4,1}から、剰余が3と合同に
ならない。だから、解なし。
このように、1次合同方程式でも解の数は1つとは限らない。
また、1次でも2次でも合同方程式は解なしもありうるね。
3.「ウィルソンの定理」で≡記号に親しもう
質問:pが素数のときに
(p-1)! + 1 ≡ 0 (mod p)
というウィルソンの定理というものがあります。
≡式の考えを使ってなぜそうなるかを考えてみよう。
(例)
p=2,3,5,7,11のとき、
(2-1)!+1= 1!+1 =2≡0(mod 2)
(3-1)!+1= 2!+1 =3≡0(mod 3)
(5-1)!+1= 4!+1 =25≡0(mod 5)
(7-1)!+1= 6!+1 =721≡0(mod 7)
(11-1)!+1= 10!+1 =3628801=329891*11≡0(mod 11)
(mod7で実験しよう)
(7-1)!=(7-1)*5*4*3*2*1=(7-1)*(5*3)*(4*2)*1
≡(7-1)*1*1*1=7-1(mod 7)
だから、(7-1)!+1≡7-1+1=7≡0(mod 7)です。
7-1以下の1以上の整数は、単位元が1です。
剰余どうしの積が1になるペアは逆元といいますが、
同じ数が別のペアと逆元になることはありません。
1つの数には1つだけ逆元があります。
5*3=15≡1(mod 7)
4*2=8≡1(mod 7)
ただし、特殊なケースが2つあります。
1と6です。
1*1≡1(mod 7)
6*6=(7-1)*(7-1)≡(-1)*(-1)≡1(mod 7)です。
だから、7-1=6個の要素のうち、1と6だけは自分が逆元なので、そのままのこる。
のこりの6-2=4要素は4/2=2組の1ができるので、かけ算で1となり消える。
だから、ウィルソンの定理は( )!がはずれる定理と覚えられます。
(一般化してみよう)
7を一般の素数pにしたときも同じ論法です。
(p-1)!=(p-1)*(p-2)*..........*2*1 ( p-1個の偶数個の積)
=(p-1)*1* 1*1*......*1 ( 両端以外の(p-1-2)/2個の逆元ペアが1と合同。)
≡p-1 (mod p)
だから、(p-1)!+1≡p-1+1=p≡0 (mod p)
ただし、p=3のときは、(3-1)!=(3-1)*1なので、両端だけで( )!が外れます。
また、p=2のときは、(2-1)!=1=2-1だから、先頭の2-1だけそのまま( )!が外れます。