0

(高校生むけ)合同式の基本

337
0

合同式の基本

(※今回の記事は生徒に解説するために作ったので,100%高校範囲です.)

断りがなければ,a,b,cを整数,k,n,mを0以上の整数とします.

1.合同式とは

合同式とは,整数の剰余(あまりのことね.)に着目した式のことです.
例えば,abmで割った剰余が等しいことを

ab (mod n)

と書きます.
これをa,bnを法として合同(a and b are congruent modulo n)と言います.
(modulo【前】:〜を法として)
例えば,
577 (mod 5), 572 (mod 5), 573 (mod 5)
です.
これは適切な整数Kを用いて57を,

57=5K+7, 57=5K+2, 57=5K3

と表せることに対応していますね.

2.合同式の性質1

合同式の性質1

(i)aa (mod n)(反射律)
(ii)ab (mod n)ba (mod n)(対称律)
(iii)ab (mod n)bc (mod n)ac (mod n)(推移律)

合同式の性質2-1

任意の整数a,b,c,dに対し,ab (mod n),cd (mod n),

(I)a+cb+d (mod n)(加法)
(II)acbd (mod n)(減法)
(III)acbd (mod n)(乗法)

合同式の性質2-2

(I)
条件より,
a+cb+c (mod n),b+cb+d (mod n)
推移律(iii)より,
a+cb+cb+d (mod n).

(II)
条件より,c,dは任意なのでcc,ddと置き換えて,(I)より,
acbd (mod n).

(III)
条件と(I)より,
acbc (mod n),bcbd (mod n)
推移律(iii)より,
acbcbd (mod n).

これで合同式においても等式と同様に加減乗が保障されました.
難しかったら最悪a=b+nk,c=d+nlと置けば証明できます.

合同式の性質2-2

(IV)任意の整数a,bに対し,acbc (mod n)cnが互いに素のとき,ab (mod n)(除法)

合同式の性質2-2

(IV)

acbc (mod n)即ち(ab)c0 (mod n)より,(ab)cnの倍数.
cnが互いに素ゆえ,(ab)nの倍数となるから
ab (mod n).

条件付きで加減乗(除)が保障されました.

べき乗

(V)ab (mod n)ambm (mod n)

べき乗

(V)
数学的帰納法を用いる.
(i)m=1のときは自明.
(ii)m=kのときakbk (mod n)と仮定すると,m=k+1のときak+1bk+1 (mod n)を示す.
仮定と条件より,
akabka (mod n), abkbbk (mod n)だから,
ak+1abkbk+1 (mod n) m=k+1でも成立.
以上により,題意は示された.

(III)を使ってもよいならもっと簡単に示せますね.

フェルマーの小定理

(VI)pを素数とすると,
apa (mod p)
(VII)pが素数,a,pが互いに素のとき,
ap11 (mod p)

フェルマーの小定理

(VI)
k=1,...,p1のとき,
kpCk=pp1Ck1 , p,kは互いに素より,
pCkpの倍数だから,二項定理より,

ap=[(a1)+1]p=(a1)p+pC1(a1)p1+...+pCp1(a1)+1(a1)p+1 (mod p)

よって,これを繰り返すと,

ap(a1)p+1(a2)p+2...1p+a1a (mod p)

を得る.

(VII)
条件より(IV)が使えるので,(VI)の両辺をaで割ると,
ap11 (mod p).

3.使用例1:ユークリッドの互除法

合同式を使うと,次のようになります.

ユークリッドの互除法

0<rk<...<r1<b
ar1 (mod b), br2 (mod r1),...,rk10 (mod rk)gcd(a,b)=rk

1003312877を約分せよ.(数検1級 2010/4)

互除法で最大公約数を求める.

128772844 (mod 10033)
100331501 (mod 1244)
28441343 (mod 1501)
1501158 (mod 1343)
134379 (mod 158)
1580 (mod 79)

より,gcd(10033,12877)=79だから,
1003312877=10033/7912877/79=127163.

4.使用例2:一次不定方程式

次の方程式の整数解をすべて求めよ.
72x+32y=3

小さい方の係数を法として計算

71x+32y71x7x3 (mod 32)...(1)
335 (mod 32)((1)より,右辺が7の倍数になるようにする)より,
7x35 (mod 32)
732は互いに素だから,
x5 (mod 32)
よって,x=32k+5(kZ)と表せるから,
32y=71x+3=71(32k+5)+3=7132k352
故に,
x=32k+5,y=71k11(kZ).

特殊解を求めなくても一次不定方程式を解くことができました.

4.演習問題

(1)250を7で割った余りを求めよ.(易)
(2)1750を9で割った余りを求めよ.(易)
(3)23100を19で割った余りを求めよ.(易)
(4)n5n30の倍数になることを示せ.(普)
(5)nが自然数のとき,26n5+32n11の倍数となることを示せ.(普)
(6)nが自然数のとき,52n1+72n1+232n135の倍数となることを示せ.(普)
(7)k=1nk!が平方数となるようなnを全て求めよ.(難)
(ヒント:0から9までの平方の1の位に注目せよ.)
(8)整式x20231を整式x4+x3+x2+x+1で割ったときの余りを求めよ.(難)
(ヒント:x4+x3+x2+x+10 (mod x4+x3+x2+x+1)より,x510 (mod x4+x3+x2+x+1))
(9)自然数nに対し,n2+2,n4+2,n6+2の最大公約数を求めよ.(難)
(ヒント:n4+2,n6+2n2+2でそれぞれ互除法.)

投稿日:202382
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

東北大学工学研究科出身 できるだけ受け売りはせず,自分で思いついた解法や妄想を備忘録がてら書き綴っていこうと思います.

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 合同式の基本
  2. 1.合同式とは
  3. 2.合同式の性質1
  4. 3.使用例1:ユークリッドの互除法
  5. 4.使用例2:一次不定方程式
  6. 4.演習問題