1次合同方程式を、合同式のまま解く。
【合同式の割り算の性質】
=============================
ka≡kb (mod n)
kとnの最大公約数をgとすると、
a≡b (mod n/g)
特に、kとnが互いに素のときは、
g=1だから、
ka≡kb (mod n)⇒a≡b (mod n)
=============================
【modの定義】
a≡b (mod n)
⇔
a-b=nkとなる整数kが存在する。
【証明】
k=gs, n=gt sとtは互いに素とする。
ka≡kb (mod n)より、
ka-kb=nmとなる整数mが存在する。
k(a-b)=nm
gs(a-b)=gtm
s(a-b)=tm
sとtは互いに素だから、a-bがtの倍数
よって、a-b≡0 (mod t)
a≡b (mod t)
ここで、n=gtより、t=n/g
したがって、
a≡b (mod n/g)
【証明終】
【例】
①2x≡6 (mod 7)→x≡3 (mod 7)
②4x≡12 (mod 18)→x≡3 (mod 9)
❲4と18の最大公約数g=2→mod 18/2❳
→x≡3,12 (mod 18)
mod 18では、g=2個解を持つ
③2x≡5 (mod 7)
2x≡5+7≡12→x≡6 (mod 7)
④7x≡2 (mod 17)
7x≡2+17×4≡2+68≡70
7と17は互いに素だから、
x≡10
2+17×4の4はなぜ？
どうやって見つける？
modの数が小さいときは見つけ易いが大きくなるとなかなか見つけにくい。
=============================
aとnは互いに素とする。
ax≡b (mod n)の解法
b≡s (mod a)
n≡t (mod a)
ty≡-s (mod a)を解く→y≡k→tk≡-s
b+nk≡s+tk≡s+(-s)≡0 (mod a)で、
b+nkはaの倍数
ax≡b+nk (mod n)
→x≡(b+nk)/a (mod n)
=============================
【例】
7x≡2 (mod 17)
2≡2 (mod 7)
17≡3 (mod 7)
3y≡-2 (mod 7)→3y≡-9→y≡-3≡4
7x≡2+17×4=2+68≡70 (mod 17)
x≡10 (mod 17)
【例】
11x≡5 (mod 41)
5≡5 (mod 11)
41≡-3 (mod 11)
-3y≡-5 (mod 11)→-3y≡6→y≡-2≡9
11x≡5+41×9≡5+369≡374
→y≡34 (mod 41)
【例】
29x≡5 (mod 51)
5≡5 (mod 29)
51≡22≡-7 (mod 29)
-7y≡-5 (mod 29)→7y≡5 (mod 29)
5≡5 (mod 7)
29≡1 (mod 7)
→z≡-5≡2 (mod 7)
7y≡5+29×2≡63→y≡9 (mod 29)
29x≡5+51×9≡5+459≡464→x≡16
よって、x≡16 (mod 51)
割り算を含めた合同式の性質を利用して解くこともできる。
【解】
29x≡5 (mod 51)
29x-51x≡5-51→-22x≡-46→11x≡23
→11x-51x≡23+51→-40x≡74
→20x≡-37≡-88→5x≡-22
→5x≡-22-51×3→5x≡-175
→x≡-35≡16 (mod 51)
【解】
29x≡5 (mod 51)
-22x≡-46→11x≡23
23≡1 (mod 11)
51≡7 (mod 11)
7y≡-1≡21 (mod 11)→y≡3
11x≡23+51×3≡23+153≡176
x≡16 (mod 51)
1次合同方程式は、1次不定方程式を利用して解くこともできる。
【解】
29x+51y=5とする。
a=29, b=51とする。
51=29+22→22=b-a
29=22+7→7=a-(b-a)=2a-b
22=7×3+1→1=(b-a)-3(2a-b)=-7a+4b
5=-35a+20b
よって、
29×(-35)+51×20=5
x=-35+51k
x≡-35 (mod 51)→x≡16 (mod 51)
【例】65x≡3 (mod 79)
65x-79x≡3-79→-14x≡-76→7x≡38
38≡3 (mod 7)
79≡2 (mod 7)
2y≡-3 (mod 7)→y≡2
7x≡38+79×2≡38+158≡196
x≡28 (mod 79)
【例】127x≡4 (mod 2021)
4≡4 (mod 127)
2021≡-11 (mod 127)
-11y≡-4 (mod 127)→11y≡4 (mod 127)
4≡4 (mod 11)
127≡6 (mod 11)
6z≡-4 (mod 11)→3z≡-2≡9→z≡3
11y≡4+127×3≡385→y≡35
127x≡4+2021×35≡70739
x≡557 (mod 2021)
【例】23x≡7 (mod 41)
7≡7 (mod 23)
41≡18≡-5 (mod 23)
-5y≡-7 (mod 23)→5y≡7≡30→y≡6
23x≡7+41×6≡7+246≡253
x≡11 (mod 41)
合同式の性質をフル活用して解いている。
(2022/10/17)
