【第4章】
(4)1次合同方程式
A≠0とする。
Ax+B≡0 (mod n)
を、「1次合同方程式」という。
(例)x+10≡0 (mod 4)
x≡-10≡-10+4×3≡2 (mod 4)
3x≡8 (mod 13)
3x≡8+13≡21 (mod 13)
x≡7 (mod 13)
一般的な解法を考えてみよう。
Ax≡C (mod n)
Ax-C=ntより、Ax-nt=C
A,nの最大公約数をgとする。
Cがgの倍数でないときは、解なし。
A=ga, n=gm, C=gc (a,mは互いに素)とする。
gax≡gc (mod gm)
ax≡c (mod m)
a,mは互いに素だから、
ax-mt=1は特殊解(p,q)を持つ。
ap-mq=1より、ap=mq+1
apx≡cp (mod m)
(mq+1)x≡cp (mod m)
mqx+x≡cp (mod m)
x≡cp (mod m)
(例)6x≡4 (mod 16) …各辺を2で割る
3x≡2 (mod 8) …①
3x-8t=1の特殊解(3,1) …①の両辺を3倍
3×3x≡3×2 (mod 8)
9x≡6 (mod 8)
x≡6 (mod 8)
合同式の性質を解いてみよう。
慣れるとこちらの方が楽。
(別解)
6x≡4 (mod 16)…各辺を2で割る
3x≡2 (mod 8)
3x≡2+8×2=18 (mod 8)…右辺が3の倍数になるように
3x≡18 (mod 8)…両辺を3で割る
x≡6 (mod 8)
(例)6x≡4 (mod 9)
6x-4=9tとなる整数tが存在する。
6x-9t=4
3(2x-3t)=4
2x-3tは整数でないから、xは整数でない。
よって、解なし。
