4章合同式を使った方程式

4 章合同式を使った方程式
2015 年 5 月 7 日 (木)
(１).2 を法とした方程式について考えよう。
∼準備∼
1．初めに次の 2 を法とした表を埋めてみよう
＋
0
1
0
0
1
1
1
0
×
0
1
0
0
0
1
0
1
2. 補数と逆数の表を埋めよう
補数
逆数
0
1
0
1
0
1
/
1
1,2 より、2 を法とした足し算・掛け算に関しては
1 の表を見ることで計算可能になり、
2 の表より引き算は補数を足す事で計算可能になる
割り算は逆数を掛ける事で計算可能になる
よって全ての計算が可能になる。
1
∼練習∼
x+1 ≡ 0(mod2)
x+1+1 ≡ 0+1(mod2)
(両辺から 1 を引く、つまり 1 の補数を足す）
x ≡ 1(mod2)
(２).3 を法とした方程式について考えよう。
∼準備∼
＋
0
1
2
0
0
1
2
1
1
2
0
2
2
0
1
×
0
1
2
0
0
0
0
1
0
1
2
2
0
2
1
補数
逆数
0
1
2
0
2
1
0
1
2
/
1
2
∼練習 1∼
. 次の 1 次方程式を解いてみよう
2x+1 ≡ 0(mod3)
2x+1+2 ≡ 0+2(mod3)
2x ≡ 2(mod3)
2・2x ≡ 2・2(mod3)
x ≡ 1(mod3)
∴x ≡ 1(mod3)
2
∼練習 2∼
. 次の連立方程式を解いてみよう

2x + y ≡ 1(mod3) ... (1)
x + y ≡ 2(mod3) ... (2)
(1)
(1) の両辺から 2x を引く
x+2x+y ≡ x+1
(左辺に 2x の補数ｘを加える）
左辺：2x+x+y ≡ (2+1)x+y ≡ 0+y ≡ y
∴y ≡ 1+x
...(1)‘
(1)‘を (2) に代入 x+(1+x) ≡ 2
2x+1 ≡ 2 (両辺から 1 を引くつまり 1 の補数である 2 を足す)
2x ≡ 2+2
2x ≡ 1 (両辺を 2 で割るつまり 2 の逆数をかける)
x≡2
よって求めた x を (1) に代入すると
y≡0
∴x ≡ 2,y ≡ 0

x + 2y ≡ 2(mod3)
2x + y ≡ 1(mod3)
...
(1)
...
(2)
(1) より x について解く
x+2y+y ≡ 2+y
x ≡ 2+y
...(1)‘
求めた x を (2) に代入
2(2+y)+y ≡ 1
1+2y+y ≡ 1
1≡1
結果左辺も右辺も 1 になるので
この式は y と無関係に成り立ちます。
よって (1)‘を満たすような x,y の組はすべて解になります。
3
(2)
(1)‘は y を勝手に決めれば x が自動的に決まります。
よって方程式の解は

x ≡ 2 ... (1)
y ≡ 0 ... (2)
(3)

x ≡ 0 ... (1)
y ≡ 1 ... (2)
(4)

x ≡ 1 ... (1)
y ≡ 2 ... (2)
(5)
POINT!
普通、連立方程式では解が決まらないときその数は無限に存在するが
3 を法とした場合考えている数自体が有限個だから解の数も
有限個になります。

x + 2y ≡ 2(mod3)
2x + y ≡ 2(mod3)
...
(1)
...
(2)
(2) の両辺を 2 倍すると、
2(2x+y) ≡ 2・2
2・2x+2y ≡ 1
x+2y ≡ 1
...(2)‘
(2)‘と (1) を比べてみると、左辺が同じなのに対して
右辺が異なるので (2)‘と (1) が両立しないことが分かります。
よって、上の連立方程式には解が存在しない。
4
(6)
(3).4 を法とした方程式で遊ぼう。
∼準備∼
＋
0
1
2
3
0
0
1
2
3
1
1
2
3
0
2
2
3
0
1
3
3
0
1
2
×
0
1
2
3
0
0
0
0
0
1
0
1
2
3
2
0
2
0
2
3
0
3
2
1
補数
逆数
0
1
2
3
0
3
2
1
0
1
2
3
/
1
/
3
∼練習 3∼
. 次の 1 次方程式を解いて比べてみよう
(1)2x+1 ≡ 0(mod4)
2x+1+3 ≡ 3
2x ≡ 3
(2)2x+2 ≡ 0(mod4)
2x+2+2 ≡ 2
2x+≡ 2
x ≡ 1,3
結果：逆数が存在しない数に対しては、割り算の答えは一定しない。
5
∼練習 4∼
. 次の連立方程式を解いてみよう

2x + y ≡ 1(mod4) ... (1)
x + y ≡ 2(mod4) ... (2)
(7)
2x+2x+y ≡ 1+2x
y ≡ 1+2x ...(1)‘
(2) に (1)‘を代入
x+(1+2x) ≡ 2
3x+1 ≡ 2
3x ≡ 1
x≡3
x ≡ 3 を (1)‘に代入
y ≡１＋ 2・3
y≡3
∴x ≡ 3(mod4),y ≡ 3(mod4)
∼練習 5∼
. 次の 4 を法とした連立方程式を解き、3 を法とした時の解と比べよう。
（3 を法としたとき答えが 1 つに決まらなかったもの）

x + 2y ≡ 2(mod4)
2x + y ≡ 1(mod4)
x+2y+2y ≡ 2+2y
x ≡ 2+2y ...(1)‘
(2) に (1)‘を代入
2(2+2y)+y ≡ 1
y≡1
6
...
(1)
...
(2)
(8)
y ≡ 1 を (1)‘に代入
x ≡ 2+2・1
x ≡ 2+2
x≡0
∴x ≡ 0(mod4),y ≡ 1(mod4)
（3 を法としたのでは解がなかったもの）

x + 2y ≡ 2(mod4)
2x + y ≡ 2(mod4)
...
(1)
...
(2)
(9)
x+2y+2y ≡ 2+2y
x ≡ 2+2y ...(1)‘
(2) に (1)‘を代入
2(2+2y)+y ≡ 2
y≡2
y ≡ 2 を (1)‘に代入
x ≡ 2+0
x≡2
∴x ≡ 2(mod4),y ≡ 2(mod4)
(4).5 を法とした 3 元連立方程式に挑戦しよう！
！
＋
0
1
2
3
4
0
0
1
2
3
4
1
1
2
3
4
0
2
2
3
4
0
1
3
3
4
0
1
2
4
4
0
1
2
3
×
0
1
2
3
4
0
0
0
0
0
0
1
0
1
2
3
4
2
0
2
4
1
3
3
0
3
1
4
2
4
0
4
3
2
1
7
補数
逆数
0
1
2
3
4
0
4
3
2
1
0
1
2
3
4
/
1
3
2
4



3x + y + 2z ≡ 2(mod5) ... (1)


2x + 3y + 4z ≡ 3(mod5) ... (2)



4x + 2y + 2z ≡ 1(mod5) ... (3)
(ヒント：解 5 つ）
3x+2x+y+2z ≡ 2+2x
y+2z ≡ 2+2x
y+2z+3z ≡ 2+2x+3z
x ≡ 2+2y+3z ...(1)‘
(2) に (1)‘を代入
2x+3(2+2y+3z)+4z ≡ 3
3x+3z+1 ≡ 3
3x+3z ≡ 2 ...(2)‘
3z ≡ 2+2x
z ≡ 4+4x
z ≡ 4+4x を (1)‘に代入
y ≡ 2+2x+3(4+4x)
y ≡ 4+4x
以上より x により y,z は決まる。また y ≡ z
よって
x ≡ 0(mod5),y ≡ 4(mod5),z ≡ 4(mod5)
x ≡ 1(mod5),y ≡ 3(mod5),z ≡ 3(mod5)
x ≡ 2(mod5),y ≡ 2(mod5),z ≡ 2(mod5)
x ≡ 3(mod5),y ≡ 1(mod5),z ≡ 1(mod5)
x ≡ 4(mod5),y ≡ 0(mod5),z ≡ 0(mod5)
8
(10)

Download Report