離散数学及び演習 講義8問題
長さ 60cm，100cm，150cm の鉄板を使って，長さ1330cm の溝を覆うためには，どの鉄板を離散数学及び演習
講義 8 2014. 6.12（木）1限

何枚使えばよいか？

1330cm1 次不定方程式（教科書 pp.117-127）
合同式（教科書 pp.127-131）

60cm

100cm

150cm

教科書･･･野崎昭弘：離散系の数学、近代科学社
2

1 次不定方程式問題の定式化
長さ 60cm，100cm，150cm の鉄板の枚数をそれぞれ
x，y，z とすると，
60x＋100y＋150z＝1330



係数 a1，a2，…，an，b∈Z，変数 x1，x2，…，xn∈Zについての（n 元）1 次不定方程式（indeterminate equation）の非負整数解を求める．

a1 x1＋a2 x2＋…＋an xn ＝b

解１ x＝ 8，y＝1，z＝5
解２ x＝13，y＝4，z＝1
解３ x＝ 8，y＝4，z＝3
解４ x＝ 3，y＝4，z＝5：

1 次不定方程式の解 … 整数解

3

4

定理（1 次不定方程式の解の存在）定理（復習）


任意の m，n∈Z に対して，x，y∈Z が存在して，
mx＋ny＝gcd（m，n）．



例： gcd（10，15）＝5＝10・（－1）＋15・1
gcd（30，77）＝1＝30・18＋77・（－7）


任意の a1，a2，…，an∈Z に対して，
x1，x2，…，xn∈Z が存在して，
a1 x1＋a2 x2＋…＋an xn ＝gcd（ a1，a2，…，an ）．
5

任意の m，n∈Z に対して，x，y∈Z が存在して，
mx＋ny＝k であるとき，かつそのときに限り，gcd（m，n）｜k．
任意の a1，a2，…，an∈Z に対して，
x1，x2，…，xn∈Z が存在して，
a1 x1＋a2 x2＋…＋an xn ＝b であるとき，かつそのときに限り，gcd（ a1，a2，…，an ）｜b．
61

離散数学及び演習 講義8系（1 次不定方程式の解の存在）証明
任意の m，n∈Z に対して，x，y∈Z が存在して，mx＋ny＝kであるとき，かつそのときに限り，gcd（m，n）｜k．


任意の m，n∈Z に対して，gcd（m，n）＝1 ならば，x，y∈Z が存在して，mx＋ny＝k．

a）「 x，y∈Z が存在して，mx＋ny＝k ならば，gcd（m，n）｜k 」を示す．
b）「 gcd（m，n）｜k ならば，x，y∈Z が存在して，mx＋ny＝k 」を示す．

a） x，y∈Z が存在して，mx＋ny＝k と仮定する．
gcd（m，n）｜m かつ gcd（m，n）｜n だから， gcd（m，n）｜mx＋ny．
すなわち， gcd（m，n）｜k．
b） gcd（m，n） ｜k と仮定する．
このとき，q∈Z が存在して，k＝q・ gcd（m，n） ．
一方，定理から，x’，y’∈Z が存在して， mx’＋ny’＝ gcd（m，n） ．
ゆえに，k＝q（ mx’＋ny’）＝ mqx’＋nqy’．
ここで，x＝qx’，y＝qy’ とおくと，x，y ∈Z であり，mx＋ny＝k．

「任意の m，n∈Z に対して，gcd（m，n）｜k ならば，x，y∈Z が存在して，mx＋ny＝k」 から明らか．

78

定理（1 次不定方程式の解の全体）

証明
gcd（m，n）｜k，かつ，mx＋ny＝k の特殊解を x0，y0 とすると，
x，y ∈Z が解であるとき，かつそのときに限り，
x＝x0＋（n／d）q， y＝y0－（m／d）q （q∈Z ）．ただし，d＝gcd（m，n）．

gcd（m，n）｜k ，かつ，1 次不定方程式 mx＋ny＝kの解のひとつ（特殊解）を x0，y0 とすると，
x，y∈Z が解であるとき，かつそのときに限り，nqx ＝ x0 ＋a）「x＝x0＋（n／d）q，y＝y0－（m／d）q ならば， x，y は解である」を示す．
b）「x ，y が解であるならば，x＝x0＋（n／d）q，y＝y0－（m／d）q 」を示す．

dy ＝ y0 －mdqa） x＝x0＋（n／d）q，y＝y0－（m／d）q とすると，
mx＋ny＝m（x0＋（n／d）q）＋n（y0－（m／d）q ）＝mx0＋ ny0＝kだから， x，y は解である．

（q∈Z）．

ただし，d＝gcd（m，n）．


一般解は上記のように表せる．


1 次不定方程式は，解が存在するならば，解は無数に存在する．
9

10

1 次不定方程式の解法

証明
gcd（m，n）｜k，かつ，mx＋ny＝k の特殊解を x0，y0 とすると，
x，y ∈Z が解であるとき，かつそのときに限り，
x＝x0＋（n／d）q， y＝y0－（m／d）q （q∈Z ）．ただし，d＝gcd（m，n）．


入力： m，n，q∈Z （m＞n）
出力： mx＋ny ＝q・gcd（m，n）の整数解 x，y 手順： mx＋ny＝（q1n＋r1）x＋nym＝q1・n＋r1＝ n（q1 x＋y）＋r1 x＝ nx1＋r1xx1＝q1x＋y＝（q2 r1＋r2）x1＋r1 xn＝q2・r1＋r2＝ r1（q2 x1＋x）＋r2 x1＝ r1 x2＋r2x1
x2＝q2x1＋x＝（q3 r2＋r3）x2＋r2 x1
r1＝q3・r2＋ r3＝ r2（q3 x2 ＋x1）＋ r3 x2＝ r2 x3＋r3 x2
x3＝q3 x2＋x1：
b） 「x ，yが解であるならば，x＝x0＋（n／d）q，y＝y0－（m／d）q 」を示す．

b） x，y は解であるとする． このとき， mx＋ny＝k．
x0，y0 は特殊解だから，mx0＋ny0=k．
ゆえに，m（x－x0）＝－n（y－y0）．
ところで，d は m，n の最大公約数 だから，m’，n’∈Z が存在して，
m＝m’d，n＝n’d （ただし，gcd（m’，n’）＝1 ）．
ゆえに，m’d（x－x0）＝－n’ d（y－y0） だから， n’ | m’（x－x0）．
gcd（m’，n’）＝1 だから，n’｜x－x0．
このとき，q∈Z が存在して， x－x0＝q・n’．
ゆえに，x＝ x0＋ n’・q ＝ x0＋（n／d）q．
また，－n’d（y－y0）＝m’d（x－x0）＝ m’dqn’だから，y－y0＝－m’q．
ゆえに, y＝ y0－（m／d）q．
11

12

2

離散数学及び演習 講義8

1 次不定方程式の解法（続き）

1 次不定方程式の解法（続き２）

入力： m，n，q∈Z （m＞n）
出力： mx＋ny ＝q・gcd（m，n）の整数解 x，y
 手順：
mx＋ny
：
＝（qk rk－1＋rk）xk－1＋rk－1 xk－2
rk－2＝qk・rk－1＋rk＝ rk－1（qk xk－1＋xk－2）＋rk xk－1
＝ rk－1 xk＋rk xk－2
xk＝qkxk－1＋xk－2＝（qk＋1rk）xk＋rk xk－1
rk－1＝qk ＋1・ rk ＋0＝ rk（qk ＋1xk＋xk－1）＝ rk xk＋1
xk＋1＝qk ＋1 xk＋xk－1
ゆえに， rk xk＋1 ＝q・gcd（m，n）
Euclid の互除法より，rk＝gcd（m，n）だから，xk＋1＝q．

入力： m，n，q∈Z （m＞n）
 出力： mx＋ny ＝q・gcd（m，n）の整数解 x，y 手順：
xk＋1＝qk ＋1 xk＋xk－1＝q
 特殊解
xk＝0 とおく．
＝qxk－1 ＝ xk＋1－qk＋1 xk＝ －qk qxk－2 ＝ xk － qk xk－1
xk－3 ＝ xk－1－ qk－1 xk－2
＝ q－qk－1（－qk q）：
x1 ＝ x3－ q3 x2x＝ x2－ q2 x1
y＝ x1－ q1 x







13

14

1 次不定方程式の解法（続き３）1 次不定方程式の解法（続き４）
例： 14x－6y ＝ 4 の整数解 x，y

入力： m，n，q∈Z （m＞n）
 出力： mx＋ny ＝q・gcd（m，n）の整数解 x，y 手順：
xk＋1＝qk ＋1 xk＋xk－1＝q 一般解
xk＝u とおく． （u … パラメータ）＝ q －qk＋1u
xk－1 ＝ xk＋1－qk＋1 xk＝ u － qk （q －qk＋1u）
xk－2 ＝ xk － qk xk－1
xk－3 ＝ xk－1－ qk－1 xk－2＝…
：
x1 ＝ x3－ q3 x2x＝ x2－ q2 x1
y＝ x1－ q1 x
14x－6y ＝（（－2）・（－6）＋2）x＋（－6）y14＝（－2）・（－6）＋2＝（－6）（－2x＋y）＋2x＝－6x1＋2xx1＝（－2）x＋y－6＝（－3）・2＋0＝（（－3）・2）x1＋2x＝ 2（－3x1＋x）
x2＝－3x1＋x＝ 2x2
ゆえに， 2x2 ＝4 だから，x2＝2．
 特殊解 x1＝0 とおく．
x
＝ x2－（－3）x1 ＝ 2y＝ x1－（－2）x ＝ 4
 一般解 x1＝u とおく．
x
＝ x2－（－3）x1 ＝ 2＋3uy
＝ x1－（－2）x ＝ u＋2（ 2＋3u ）＝4＋7u
15

16

1 次不定方程式の解法（続き５）
例： 14x－6y ＝ 4 の整数解 x，y1 次不定方程式の解法（続き６）
例： 60x＋100y＋150z＝1330 の整数解 x，y，z

絶対値最小の係数でくくる

14x－6y＝（－6）（－2x＋y）＋2x＝－6x1＋2x← －6 でくくる
x1＝（－2）x＋y

6x＋10y＋15z＝133 の整数解を求める

6x＋10y＋15z ＝ 6（x＋y＋2z）＋4y＋3z ← 6 でくくる
＝ 6u＋4y＋3z
u＝ x＋y＋2z＝ 3（2u＋y＋z）＋y← 3 でくくる＝ 3v＋yv＝ 2u＋y＋z
ゆえに， 3v＋y ＝133 だから，y＝133－3v．
z ＝ v－2u－y ＝ v－2u－（133－3v）＝－2u＋4v－133
x ＝ u－y－2z ＝ u－（133－3v）－2（－2u＋4v－133）＝ 5u－5v＋133
 u＝19，v＝44 のとき，x＝ 8，y＝1，z＝5
 u＝19，v＝43 のとき，x＝13，y＝4，z＝1＝ 2（－3x1＋x）← 2 でくくる
x2＝－3x1＋x＝ 2x2
ゆえに， 2x2 ＝4 だから，x2＝2．
 特殊解 x1＝0 とおく．
x
＝ x2－（－3）x1 ＝ 2y＝ x1－（－2）x ＝ 4
 一般解 x1＝u とおく．
x
＝ x2－（－3）x1 ＝ 2＋3uy
＝ x1－（－2）x ＝ u＋2（ 2＋3u ）＝4＋7u
17

18

3

離散数学及び演習 講義8

整数を法とする合同関係（復習）

整数を法とする合同関係（続き）

m，n，p∈Z に対して，
m と n は p を法（modulo）として合同（congruent）… m ≡p n， m ≡ n （mod p）



m と n は p で割ったときの剰余が等しい
m － n は p の倍数
 p｜m － n










p｜m － nm ≡ 0 （mod p）
例： 365 ≡ 1 （mod 7）m ≡ n （mod p）

p｜mm ≡ n （mod p） iff m ≡ n （mod －p）
p｜m － n iff －p｜m － n

365 － 1＝ 364 ＝ 52・7

－12 ≡ 14 （mod 13）－12－ 14 ＝ －26 ＝ －2・13
19

20

定理（復習）

定理

p∈Z を法とする合同関係は Z 上の同値関係である．

任意の m，n，p∈Z （p≠0） に対して，次の（1）～（3）は同値である．
（1） m ≡ n （mod p）（2） k∈Z が存在して，m＝n＋k・p（3） m を p で割ったときの剰余とn を p で割ったときの剰余は等しい

すなわち，次の（1）～（3）が成り立つ．
（1）任意の m∈Z に対して， m≡m （mod p） ．
（2）任意の m，n∈Z に対して，
m≡n （mod p）ならば， n≡m （mod p）．
（3）任意の m，n，l∈Z に対して，
m≡n （mod p）かつ n≡l （mod p） ならば，m≡l （mod p）．


21

22

証明

証明（続き）

任意の m，n，p∈Z（p≠0）に対して，次の（1）～（3）は同値である．
（1） m ≡ n （mod p）（2） k∈Z が存在して，m＝n＋k・p（3） m を p で割ったときの剰余と n を p で割ったときの剰余は
等しい




任意の m，n，p∈Z（p≠0）に対して，次の（1）～（3）は同値である．
（1） m ≡ n （mod p）（2） k∈Z が存在して，m＝n＋k・p（3） m を p で割ったときの剰余と n を p で割ったときの剰余は等しいa）「（1）ならば（2）」を示す．
b）「（2）ならば（3）」を示す．
c）「（3）ならば（1）」を示す．

b）「（2）ならば（3）」を示す．

b） ある k∈Z に対して，m＝n＋k・p と仮定する．
また， m，n を p で割ったときの剰余をそれぞれ r，r’∈Z とする．
このとき，q，q’∈Z に対して，m＝q・p＋r，n＝q’・p＋r’（0  r，r’＜｜p｜）．
ゆえに， m＝（q’・p＋r’ ）＋k・p ＝q・p＋r だから，
（q－q’－k）p－（r－r’ ）＝0．
p≠0 だから， q－q’＝k，かつ，r＝r’ ．
ゆえに，m を p で割ったときの剰余と n を p で割ったときの剰余は等しい．

a） m ≡ n （mod p）と仮定する．
このとき，p｜m － n．
ゆえに，k∈Z が存在して， m － n ＝ k・p．
すなわち，m＝n＋k・p．
23

24

4

離散数学及び演習 講義8証明（続き２）定理（合同関係における加減乗算）

任意の m，n，p∈Z（p≠0）に対して，次の（1）～（3）は同値である．
（1） m ≡ n （mod p）（2） k∈Z が存在して，m＝n＋k・p（3） m を p で割ったときの剰余と n を p で割ったときの剰余は等しい


任意の a，b，c，d，p∈Z に対して，
a≡b （mod p），c≡d （mod p） ならば，次の（1）～（3）が成り立つ．
（1） a＋c ≡ b＋d （mod p）【参考】任意の a，b，c，d∈Z に対して，
a＝b，c＝d ならば，
（2） a－c ≡ b－d （mod p）
次の（1）～（3）が成り立つ．
（3） ac ≡ bd （mod p）（1） a＋c ＝ b＋dc）「（3）ならば（1）」を示す．

（2） a－c ＝ b－d（3） ac ＝ bd

例：29≡－1 （mod 6），13≡1 （mod 6）c） q，q’，r∈Z に対して，
m＝q・p＋r，n＝q’・p＋r （0  r＜｜p｜） と仮定する．
このとき， m－n＝ （q－ q’）p．
q－q’∈Z だから，p｜m－n．
すなわち，m ≡ n （mod p）．








29＋13≡－1＋1 （mod 6），すなわち，42≡0 （mod 6） ．
29－13≡－1－1 （mod 6），すなわち，16≡－2 （mod 6）．

25≡14 （mod 11），79≡2 （mod 11）25・79≡14・2 （mod 11），すなわち，1975≡28 （mod 11）．

25

26

証明

証明（続き）

任意の a，b，c，d，p∈Z に対して，
a≡b （mod p），c≡d （mod p） ならば，
（1） a＋c ≡ b＋d （mod p）

任意の a，b，c，d，p∈Z に対して，
a≡b （mod p），c≡d （mod p） ならば，
（3） ac ≡ bd （mod p）

a≡b （mod p），c≡d （mod p）だから，q，q’∈Z が存在して，
a－b ＝ q・p， c－d ＝ q’・p．
（1） （a＋c ）－（b＋d ）＝ （a－b ）＋（c－d ）＝ q・p＋q’・p＝ （q＋q’ ）p
q＋q’∈Z だから，a＋c ≡ b＋d （mod p）．

a≡b （mod p），c≡d （mod p）だから，q，q’∈Z が存在して，
a－b ＝ q・p， c－d ＝ q’・p．
（3） ac－bd ＝ （a－b）c＋b （c－d）＝ q・p・c＋b・q’・p＝ （qc＋bq’ ）p
qc＋bq’ ∈Z だから，ac ≡ bd （mod p）．

27

28

系（合同関係における加減乗算）

証明
任意の a，b，c，p∈Z に対して，a≡b （mod p）ならば，任意の a，b，c，p∈Z に対して，a≡b （mod p）ならば，次の（1）～（3）が成り立つ．
（1） a±c ≡ b±c （mod p）（2） ac ≡ bc （mod p）（3） an ≡ bn （mod p） （n∈N∪{0}）（1） a±c ≡ b±c （mod p）（2） ac ≡ bc （mod p）（3） an ≡ bn （mod p） （n∈N∪{0}）（1），（2） c ≡ c （mod p） だから，定理より明らか．
（3） n に関する帰納法により示す．
（基底段階） n＝0 のとき．
a0 ＝ b0 ＝1 ，1≡1 （mod p） だから，明らか．
（帰納段階） an－1 ≡ bn－1 （mod p）と仮定する．
a≡b （mod p）だから，定理より， an－1・a ≡ bn－1・b （mod p）．
ゆえに， an ≡ bn （mod p）．

【参考】 任意の a，b，c ∈Z に対して，a＝b ならば，次の（1）～（3）が成り立つ．
（1） a±c ＝ b±c（2） ac ＝ bc
（3） an ＝ bn （n∈N∪{0}）
29

30

5

離散数学及び演習 講義8

合同関係における乗算（続き）

合同関係の応用

例： 79525 を11で割ったときの剰余任意の a，b∈Z に対して，365a＋b≡a＋b （mod 7）795≡3 （mod 11）
25 ≡325 （mod 11）
 795

a 年後（その間に閏日 b 回）の同じ日の曜日
例： 1979年1月1日（月）に対して，2012年1月1日（日）







2
 3 ＝9≡－2（mod 11）34＝（32）2≡（－2）2＝4 （mod 11）84 22 3 ＝（3 ） ≡4 ＝16≡5 （mod 11）16
8 22 3 ＝（3 ） ≡5 ＝25≡3 （mod 11）

365・33＋8≡33＋1≡5＋1≡6 （mod 7）
7で割ったときの剰余 0→月，1→火， … ，6→日

365－1＝364＝52・7 だから，365≡1 （mod 7）
ゆえに，365a＋b≡a＋b （mod 7）

325＝ 316・ 38・ 31≡3・5・3＝15・3≡4・3≡1 （mod 11）
25 ≡1 （mod 11）
 ゆえに， 795


31

32

合同関係の応用（続き）


合同関係の応用（続き２）

九去法（casting out nines）（9で割ったときの剰余）11で割ったときの剰余

例： 12,345,678≡－1＋2－3＋4－5＋6－7＋8＝4 （mod 11）n ＝（ak ak－1 … a1 a0 ）10＝ ak10k＋ak－110k－1＋…＋a1101＋ a0（ai∈N0，0  ai＜10）に対して，n ≡ （－1）kak＋ （－1）k－1ak－1＋…－a1＋ a0 （mod 11）kk－1a
 11｜n iff 11｜（－1） ak＋ （－1）
k－1＋…－a1＋ a0

例： 12,345,678≡1＋2＋…＋7＋8＝36≡0 （mod 9）
n ＝（ak ak－1 … a1 a0 ）10＝ ak10k＋ak－110k－1＋…＋a1101＋ a0（ai∈N0，0  ai＜10）に対して，
n ≡ ak＋ak－1＋…＋a1＋ a0 （mod 9）
 9｜n iff 9｜ak＋ak－1＋…＋a1＋ a0

10≡－1 （mod 11）
10i≡（－1）i （mod 11）
ゆえに，
n ＝ ak10k＋ak－110k－1＋…＋a1101＋ a0≡ （－1）kak＋ （－1）k－1ak－1＋…－a1＋ a0 （mod 11）

10≡1 （mod 9）10i≡1i＝1 （mod 9）
ai10i≡ai （mod 9）
ゆえに，
n ＝ ak10k＋ak－110k－1＋…＋a1101＋ a0 ≡ ak＋ak－1＋…＋a1＋ a0 （mod 9）102i≡（－1）2i＝1 （mod 11），102i＋1≡（－1）2i＋1 ＝－1 （mod 11）
33

34

合同関係の応用（続き３）定理（合同関係における除算）

7で割ったときの剰余任意の a，b，c，p∈Z に対して，
ac≡bc （mod p） かつ gcd（c，p）＝d （≠0）ならば，

例： 12,345,678≡12－345＋678≡5－2＋6＝9≡2 （mod 7）
n ＝ uk1000k＋uk－11000k－1＋…＋u110001＋ a0（ui∈N0，0  ui＜1000）に対して，
n ≡ （－1）kuk＋ （－1）k－1uk－1＋…－u1＋ u0 （mod 7）kk－1u
 7｜n iff 7｜（－1） uk＋ （－1）
k－1＋…－u1＋ u0a≡b （modp）．

d【参考】 任意の a，b，c ∈Z に対して，
ac ＝ bc かつ c≠0 ならば， a ＝ b．

1001＝7・11・13 だから，1000≡－1 （mod 7）
1000i≡（－1）i （mod 7）
ゆえに，
n ＝ uk1000k＋uk－11000k－1＋…＋u110001＋ u0≡ （－1）kuk＋ （－1）k－1uk－1＋…－u1＋ u0 （mod 7）

整数を法とする合同関係では
 「ac ≡ bc かつ c≡0／ （mod p） ならば， a ≡ b」 は一般に成り立たない．
例： 7×2≡4×2 （mod 6），2≡0／ （mod 6）であるが，7≡4／ （mod 6）
10002i≡（－1）2i＝1 （mod 7），10002i＋1≡（－1）2i＋1 ＝－1 （mod 7）
35

ac ≡ bc （mod p）かつ gcd（c，p）＝1 ならば，a ≡ b （mod p）．
例： 7×5≡1×5 （mod 6），gcd（5，6）＝1 であり，7≡1 （mod 6）．
366離散数学及び演習 講義8

証明

合同関係における零因子

任意の a，b，c，p∈Z に対して，
ac ≡ bc （mod p） かつ gcd（c，p）＝d （≠0）ならば，
pa ≡ b （mod
）．



d

a∈Z は p∈Z を法とする合同関係における零因子（zero divisor）である
 c∈Z が存在して，c≡0（modp） かつ ac≡ca≡0 （mod p）／

例： 2 は 6 を法とする合同関係における零因子 3≡0／ （mod 6） に対して，2・3＝3・2＝6≡0 （mod 6）

d は c，p の最大公約数だから，c’，p’∈Z が存在して，c＝c’・d，p＝p’・d．
このとき，gcd（c’，p’）＝1．
また，ac ≡ bc （mod p）だから，q∈Z が存在して，ac－bc＝q・p．
ゆえに，（a－b）c’d＝qp’d だから， p’｜ （a－b）c’．
gcd（c’，p’）＝1 だから， p’｜ a－b．
pすなわち， a ≡ b （mod p’） だから， a ≡ b （mod）．

通常の等号関係では
ac ＝ 0 ならば a＝0 または c ＝ 0．
 整数を法とする合同関係ではac ≡ 0 （mod p）であっても，a ≡ 0 （mod p） または c ≡ 0 （mod p） とは限らない．


d

37

38

系（合同関係における除算）

証明
任意の a，b，c∈Z と任意の素数 p に対して，
次の（1），（2）が成り立つ．
（1） ac≡bc （mod p） かつ c≡0／ （mod p）ならば， a≡b （mod p）．
（2） ac≡0 （mod p） ならば，a≡0 （mod p）または c≡0 （mod p）．

任意の a，b，c∈Z と任意の素数 p に対して，
次の（1），（2）が成り立つ．
／ （mod p）ならば，（1） ac≡bc （mod p） かつ c≡0a≡b （mod p）．
（2） ac≡0 （mod p） ならば，a≡0 （mod p） または c≡0 （mod p） ．
（1） c≡0／ （mod p） だから，p｜c でない．
ゆえに，gcd（c，p）＝1 となり，定理より明らか．
（2） ac≡0 （mod p）とする．
／ （mod p） かつ c≡0／ （mod p） と仮定する．
ここで， a≡0（1）において b＝0 とおくと， a≡0 （mod p）．
これは矛盾．
ゆえに， a≡0 （mod p）または c≡0 （mod p）．

素数を法とする合同関係については，通常の等号関係と同様に除算を行える．

39

40

まとめ




今回の講義


1 次不定方程式



合同式

次回の講義




（2限）合同式（続き）（教科書 pp.131-137，140-145）

今回の演習


なし

41

7