離散数学及び演習 講義6

離散数学及び演習
講義 6 2014. 5.29（木）整数論（number theory）

約数・倍数（教科書 pp.101-106, 113-116）
教科書･･･野崎昭弘：離散系の数学、近代科学社

２８＝１＋２＋４＋７＋１４

整数の基本的性質

除法定理（division theorem）

Z： すべての整数からなる集合
N： すべての自然数からなる集合
N0＝N∪{0}： すべての非負整数からなる集合（1） 任意の m∈N0，n∈N に対して，順序対（q，r）∈N02 が唯一存在して，m＝q・n＋r （0  r ＜ n ）（2） 任意の m，n∈Z （n≠0） に対して，順序対（q，r）∈Z2 が唯一存在して，m＝q・n＋r （0  r ＜｜n｜）任意の m，n ∈ Z に対して，
 m＋n ∈ Z
 m－n ∈ Z

0－n ＝ －n ∈ Z例：××m・n ∈ Z 一般に，m／nZ

Z は加法，減法，乗法について閉じている．
Z は除法について閉じていない．
 剰余のある除法
3

r＝66｜51｜
r＝－36＜0－117＝3・（－51）＋36
× －117＝4・（－51）＋87
× －117＝2・（－51）＋（－15）

r＝87 ｜－51｜
r＝－15＜0

4

証明（続き２）（1） 任意の m∈N0， n∈N に対して，順序対（q，r）∈N02 が唯一存在して，m＝q・n＋r （0  r ＜ n ）

r＝mod（m，n）

117＝2・51＋15
117＝1・51＋66
117＝3・51＋（－36）

証明

q … 商（quotient）
r … 剰余（remainder）（1） 任意の m∈N0，n∈N に対して，順序対（q，r）∈ N0 2 が唯一存在して，m＝q・n＋r （0  r ＜ n ）a） 「（q，r）∈N0 2 が存在する」を示す．
b） 「（q，r）∈N0 2 は唯一である」を示す．

b） 「（q，r）∈N0 2 は唯一である」を示す．

b）任意の m∈N0 ，n∈N に対して，（q1，r1），（q2，r2） ∈ N0 2 （ q1≠q2 ）が存在して，m＝q1・n＋r1 （0  r1＜ n ）， m＝q2・n＋r2 （0  r2＜ n ） と仮定する．
b-1） q1＞q2 のとき．
このとき，0＝（ q1－q2 ）・n＋（ r1－r2 ）．すなわち， r2－r1＝（ q1－q2 ）・n．
q1－q2 ＞0 で， q1－q2∈Z だから， q1－q2  1．
n＞0 だから， （ q1－q2 ）・n  n．
一方， r2 ＜n， r1 0 だから， r2－r1 ＜n．
r2－r1 ＝（ q1－q2 ）・n ＜n となるから，これは矛盾．
b-2） q2＞q1 のとき． 同様に矛盾．
ゆえに， q1＝q2．
このとき， r2－r1＝（ q1－q2 ）・n＝0 だから， r1＝r2．
6a-1） m＜n のとき．このとき，0  m＜n．
q＝0，r＝m とおくと，m＝0・n＋m だから， m＝q・n＋r （0  r ＜ n ）a-2） m  n のとき．m に関する帰納法により示す．
任意の k＜m （k∈N0 ） に対して，（q’，r’）∈N0 2 が存在して，k＝q’・n＋r’ （0  r’ ＜ n ）と仮定する（帰納法の仮定）．
ここで，m’＝m－n （  0）とおくと， m’－m＝－n＜0 だから， m’＜m．
帰納法の仮定から，m’ と n に対して，（q’，r’）∈N0 2 が存在して，m’＝q’・n＋r’ （0  r’ ＜ n ）．
m’ ＝m－n＝q’・n＋r’ だから，m＝（q’＋1）・n＋r’．
q＝q’＋1，r＝r’ とおくと，（q，r）∈N0 2 で，m＝q・n＋r （0  r ＜ n ）．
51

離散数学及び演習 講義6証明（続き３）証明（続き４）（2） 任意の m，n∈Z （n≠0） に対して，順序対（q，r）∈Z2 が唯一存在して，m＝q・n＋r （0  r ＜｜n｜）（1） 任意の m∈N0，n∈N に対して，順序対（q，r）∈N0 2 が唯一存在して，m＝q・n＋r （0  r ＜ n ）（2） 任意の m，n∈Z （n≠0） に対して，順序対（q，r）∈Z2 が唯一存在して，m＝q・n＋r （0  r ＜｜n｜ ）a） 「（q，r）∈Z2 が存在する」を示す．

a-1） n＞0 のとき．このとき，｜n｜＝n．
a-1-1） m  0 のとき．（1）から明らか．
a-1-2） m＜0 のとき．
m’＝－（m＋1）とおくと，m＜0 だから，m’ ＞－1．
m’∈Z だから， m’  0．
（1）から，m’，n に対して，（ q’，r’ ）∈Z2 が存在して，m’＝q’・n＋r’（0  r’ ＜ n ）このとき，m＝－m’－1＝－（q’・n＋r’ ）－1＝（－q’－1）・n＋（n－1－r’）．
ここで，q＝－q’－1 ，r＝ n－1－r’ とおくと，（q，r）∈Z2 で，m＝q・n＋r．
また， r’∈Z だから， 0  r’ n－1．
ゆえに， 0  n－1－r’  n－1．
したがって，0  r  n－1 だから，0  r ＜n＝｜n｜．

a） 「（q，r）∈Z2 が存在する」を示す．
b） 「（q，r）∈Z2 は唯一である」を示す．
a-1） n＞0 のとき．
 a-1-1） m 0 のとき． … （１）から明らか．
 a-1-2） m＜0 のとき．
a-2） n＜0 のとき．
 a-2-1） m 0 のとき．
（１）に帰着させる．
 a-2-2） m＜0 のとき．
b） （1）と同様に証明できる．

78

証明（続き５）証明（続き６）（2） 任意の m，n∈Z （n≠0） に対して，順序対（q，r）∈Z2 が唯一存在して，m＝q・n＋r （0  r ＜｜n｜）（2） 任意の m，n∈Z （n≠0） に対して，順序対（q，r）∈Z2 が唯一存在して，m＝q・n＋r （0 r ＜｜n｜）a） 「（q，r）∈Z2 が存在する」を示す．

a） 「（q，r）∈Z2 が存在する」を示す．

a-2） n＜0 のとき．このとき，｜n｜＝－n＞0．
a-2-1） m  0 のとき．
n’＝－n とおくと，n’＞0．
（1）から，m，n’ に対して組（ q’，r’ ）∈Z2 が存在して，m＝q’・n’＋r’（0  r’ ＜ n’ ）このとき，m＝q’・（－n）＋r’ ＝（－q’）・n＋r’．
ここで，q＝－q’ ，r＝r’ とおくと，（q，r）∈Z2 で，m＝q・n＋r．
さらに， n’＝－n＝｜n｜だから， 0  r ＜｜n｜ ．

a-2） n＜0 のとき．このとき，｜n｜＝－n＞0．
a-2-2） m＜ 0 のとき．
m’＝－（m＋1），n’＝－n とおくと，m’ 0，n’＞ 0．
（1）から，m’，n’ に対して組（ q’，r’ ）∈Z2 が存在して，m’＝q’・n’＋r’（0  r’ ＜ n’ ）このとき，m ＝－m’－1 ＝－（q’・（－n）＋r’ ）－1＝（q’＋1）・n＋（－（n＋r’＋1）） ．
ここで，q＝ q’＋1 ，r＝－（n＋r’＋1）とおくと，（q，r）∈Z2 で，m＝q・n＋r．
さらに，0  r’＜ n’ だから，1 r’＋1＜n’＋1＝－n＋1．
ゆえに， 0＜r’＋1 －n だから， 0 －（n＋r’＋1）＜－n＝｜n｜．
すなわち， 0  r ＜｜n｜．

910約数・倍数約数・倍数（続き）n，k∈Z に対して，
k は n の約数（divisor）である， n は k の倍数（multiple）である
k は n を割り切る（divide） （ n は k で割り切れる（divisible）） … k｜nn，k∈Z に対して，
 k は n の約数（divisor）である
n は k の倍数（multiple）である
k は n を割り切る（divide） （ n は k で割り切れる（divisible））… k｜n



（19は38の約数，38は19の倍数）
－19｜38 （－19は38の約数，38は－19の倍数）

38＝（－2）・（－19）
11（±n∈Z）±1は任意の n∈Z の約数である，任意の n∈Z は±1の倍数である±1は任意の n∈Z を割り切る （ ±1 ｜n ）任意の k∈Z に対して，0＝0 ・k

38＝2・19ある q ∈Z が存在して，n ＝ q・k

任意の n∈Z に対して，n＝n ・1， n＝（－n）・（－1）
ある q ∈Z が存在して，n ＝ q・k

例：
 19｜38（0∈Z ）

任意の k∈Z は 0 の約数である， 0 は任意の k∈Z の倍数である
任意の k∈Z は 0 を割り切る （ k｜0 ）特に，0 は 0 の約数である， 0 は 0 の倍数である
0 は 0 を割り切る （ 0｜0 ）任意の n∈Z （ n≠ 0 ）に対して， n＝q・0 となる q∈Z は存在しない n≠ 0 に対して，0｜n とはならない．
122

離散数学及び演習 講義6

整除関係（divisibility relation）
Z 上の整除関係 ｜ （｜⊆ Z2 ）｜は反射的かつ推移的である｜は反対称的でない
1｜－1かつ－1｜1であるが，1≠－10｜は半順序±8±12±30±4±6±10

特に， m，n∈N0 のとき，（2’） m｜n かつ n｜m ならば，m＝n．

1 は N0 上の整除関係｜の最小元

任意の m，n，k∈Z に対して，次の（1）～（4）が成り立つ．
（1） m｜m．
（2） m｜n かつ n｜m ならば，｜m｜＝｜n｜．
（3） m｜n かつ n｜k ならば，m｜k．
（4） k｜m かつ k｜n ならば，任意の a，b∈Z に対して，k｜am＋bn．

k｜n iff ある q ∈Z が存在して，n ＝ q・k

N0 上の整除関係 ｜ （｜⊆ N02 ）

定理

任意の n ∈N0 に対して， 1 ｜n ．

±150 は N0 上の整除関係｜の最大元

任意の k ∈N0 に対して， k｜0 ．

±2±3±5±1±7

整除関係｜は N0 上の半順序である．

1314

証明

証明（続き）（1） m｜m．
（2） m｜n かつ n｜m ならば，｜m｜＝｜n｜．

（3） m｜n かつ n｜k ならば，m｜k．
 「ある q∈Z が存在して，k ＝ q・m 」 を示す．

（1） 1∈Z に対して，m＝1・m だから，明らか．
（2） m｜n だから，q1∈Z が存在して，n＝q1・m．
n｜m だから，q2∈Z が存在して，m＝q2・n．
ゆえに，n＝q1q2 n．
a） n≠0 のとき． q1q2 ＝1．
q1，q2∈Z だから，q1＝q2＝1 または q1＝q2＝－1．
すなわち，m＝n または m＝－n だから，｜m｜＝｜n｜．
b） n＝0 のとき． m＝q2・0＝0．
ゆえに，m＝n＝0 だから，｜m｜＝｜n｜．

m｜n だから，q1∈Z が存在して，n＝q1・m．
n｜k だから，q2 ∈Z が存在して，k＝q2・n．
ゆえに，k＝q2・ q1・ m．
q2・ q1 ∈Z だから，m｜k．

1516

証明（続き２）定理（4） k｜m かつ k｜n ならば，任意の a，b∈Z に対して，k｜am＋bn．
 「ある q ∈Z が存在して， am＋bn ＝ q・k 」 を示す．

n，m∈Z に対して，m≠0 かつ n｜m ならば，｜n｜｜m｜．
特に，n，m∈N に対して，n｜m ならば，n  m．

k｜m だから，q1∈Z が存在して，m＝q1・k．
k｜n だから，q2∈Z が存在して，n＝q2・k．
ゆえに， am＋bn ＝ aq1k ＋bq2k ＝ （aq1 ＋bq2）k ．
aq1 ＋bq2 ∈Z だから， k｜am＋bn．

17183離散数学及び演習 講義6

証明

公倍数n，m∈Z に対して，m≠0 かつ n｜m ならば，｜n｜ ｜m｜．

n，k∈Z に対して，
 m∈Z は n，k の公倍数（common multiple）である
n｜m だから，q∈Z が存在して，m＝q・n．
m≠0 だから，q≠0 かつ n≠0．
ゆえに，1 ｜q｜．
｜n｜ 0 だから，｜n｜ ｜q｜・｜n｜＝｜q・n｜＝｜m｜．

n｜m かつ k｜m．

m∈N0 は n，k の最小公倍数（least common multiple）である… m＝lcm（n，k）＝［n，k］
m は n，k の公倍数で，かつ， n，k の任意の公倍数 m’に対して，m｜m’（m’は m の倍数）．
m は n，k のすべての非負公倍数からなる集合上での整除関係に関する最小元0

例： 4 の倍数 ：…，－12，－8，－4，0，4，8，12，…
6 の倍数 ：…，－18，－12，－6，0，6，12，18，…
 4 と 6 の公倍数 ：…，－24，－12，0，12，24，…
±24
 4 と 6 の最小公倍数 ： 12 （ ∈N0 ）12｜0，12｜12，12｜2419

定理

k1，…，kn∈Z に対して，
 m∈Z は k1，…，kn の公倍数である

任意の n，k ∈Z に対して，lcm（n，k）＝ lcm（k，n）．
 任意の n∈Z に対して，lcm（n，0）＝0．
0 は n，0 の唯一の公倍数で，かつ， 0｜0．

n，k ∈N の最小公倍数は n，k の公倍数の中で（大小関係に関して）最小である．
k1｜m ，…， kn｜m．

m∈N0 は k1，…，kn の最小公倍数である… m＝lcm（ k1，…，kn ）＝［ k1，…，kn ］
m を n，k の任意の公倍数とすると，lcm（n，k）｜m ，かつ， m＞0， lcm（n，k）＞0 だから，定理より，lcm（n，k）  m．

m は k1，…，knの公倍数で，かつ， k1，…，kn の任意の公倍数 m’に対して，m｜m’．

2122

公約数

定理

n，k∈Z に対して，
 d∈Z は n，k の公約数（common divisor）である

d｜n かつ d｜k．

d∈N0 は n，k の最大公約数（greatest common divisor）である… d＝gcd（n，k）＝（n，k）


－8，－4，－2，－1，1，2，4，8－12，－6，－4，－3，－2，－1，1，2，3，4，6，12
8 と12の公約数 ： －4，－2，－1，1，2，4
8 と12の最大公約数 ： 4 （ ∈N0 ）

1｜4，2｜4，4｜4

任意の n，k ∈Z に対して，gcd（n，k）＝ gcd（k，n）．
任意の n∈Z に対して，gcd（n，0）＝｜n｜．
特に，gcd（0，0）＝0．
d は n，k の公約数で，かつ， n，k の任意の公約数 d’に対して，d’｜d （ d’ は d の約数） ．
d は n，k のすべての非負公約数からなる集合上での整除関係に関する最大元

例： 8 の約数 ：12の約数 ：20

公倍数（続き）±12±4n，k ∈N の最大公約数は n，k の公約数の中で（大小関係に関して）最大である．
±2±1

任意の整数は 0 の約数である．
ゆえに，n，0 の公約数は n の約数である．
｜n｜は n，0 の公約数で，かつ， n，0 の任意の公約数 d’に対して，d’｜｜n｜．

d を n，k の任意の公約数とすると，d｜gcd（n，k）かつ gcd（n，k）＞0， d＞0 だから，定理より，d gcd（n，k）．

23244離散数学及び演習 講義6公約数（続き）

互いに素k1，…，kn∈Z に対して，
 d∈Z は k1，…，kn の公約数である


d｜k1 ，…， d｜kn ．

d∈N0 は k1，…，kn の最大公約数である… d＝gcd（ k1，…，kn ）＝（ k1，…，kn ）n，k ∈Z は互いに素である（relatively prime, coprime）
gcd（n，k）＝1

d は k1，…，knの公約数で，かつ， k1，…，kn の任意の公約数 d’に対して，d’｜d．

25

26

定理

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

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

mu＋nv （u，v∈Z）という形の最小の自然数を d＝ mx＋ny とする．
このとき， x，y ∈Z．
 d＝ gcd（m，n）を示す．
 1）「d｜m かつ d｜n 」を示す．
 2）「m と n の任意の公約数 d’ に対して，d’｜d 」を示す．
1） d｜m でないと仮定する．
このとき，除法定理から，q，r∈Z が存在して，m＝q・d＋r （0＜r＜d）．
ゆえに，r＝m－q・d＝m－q・（mx＋ny ）＝ m（1－q・x ）＋n（－q・y ）．
1－q・x ，－q・y ∈Z だから，r は mu＋nv という形の自然数である．
ところが， r＜d だから，d の選び方に矛盾する．
ゆえに， d｜m ．
同様に， d｜n ．
28

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

27

証明（続き）

系

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

任意の m，n，k∈Z に対して，gcd（m，n）＝1 かつ m｜nk ならば，m｜k．

mu＋nv （u，v∈Z）という形の最小の自然数を d＝ mx＋ny とする．
 d ＝ gcd（m，n）を示す．
 2）「m と n の任意の公約数 d’ に対して，d’｜d 」を示す．
2） d’ は m と n の公約数だから，m’，n’∈Z が存在して，m＝m’d’ かつ n＝n’d’．
ゆえに，d＝ mx＋ny ＝ m’d’x＋ n’d’y ＝（m’x＋ n’y ）d’ ．
m’ x＋ n’y ∈Z だから， d’｜d ．
以上から， d ＝ gcd（m，n）．
2930

5離散数学及び演習 講義6

証明

定理

任意の m，n，k∈Z に対して，gcd（m，n）＝1 かつ m｜nk ならば，m｜k．

任意の n，k ∈Z に対して，gcd（n，k）・lcm（n，k）＝n・k．

定理から，m，n ∈Z に対して，x，y∈Z が存在して，mx＋ny＝gcd（m，n）＝1．
このとき，k（mx＋ny）＝k．
一方，k（mx＋ny）＝ mkx＋nky．
m｜nk だから， m｜nky．
また，明らかに，m｜mkx．
ゆえに，定理より m｜ mkx ＋ nky だから， m｜k（mx＋ny）．
mx＋ny＝1 だから，m｜k．
3132

証明

証明（続き）
任意の n，k ∈Z に対して，gcd（n，k）・lcm（n，k）＝n・k．

任意の n，k ∈Z に対して，gcd（n，k）・lcm（n，k）＝n・k．
a） n＝0 または k ＝0 のとき．
b） n， k ≠0 のとき．

b） n， k ≠0 のとき．
gcd（n，k）＝d とおく．すなわち， d・lcm（n，k）＝n・k を示す．
このとき，q，q’∈Z が存在して，n＝q・ d かつ k＝q’・d．
（ gcd（q ，q’ ）＝1 ）ゆえに，n・k ＝ q・d・q’・d ＝ d・qq’d．
qq’d ＝ m とおく．すなわち，n・k＝d・m．
 m＝ lcm（n，k）を示す．
 b-1） 「 n｜m かつ k｜m 」を示す．
 b-2） 「 n，k の任意の公倍数 m’ に対して，m｜m’」を示す．

a） n＝0 または k ＝0 のとき．
lcm（n，k）＝0，n・k＝0 だから， gcd（n，k）・lcm（n，k）＝n・k．

b-1） m ＝ q’・qd ＝ q’・n だから， n｜m ．
また，m ＝ q・q’d ＝q・k だから， k｜m ．
33

34

定理（Euclid の互除法の原理）

証明（続き２）b） n， k ≠0 のとき．
gcd（n，k）＝d とおく．すなわち， d・lcm（n，k）＝n・k を示せばよい．
このとき，q，q’∈Z が存在して，n＝q・ d かつ k＝q’・d．
ゆえに，n・k ＝ q・d・q’・d ＝ d・qq’d．
qq’d ＝ m とおく．すなわち，n・k＝d・m．
 b-2） 「 n，k の任意の公倍数 m’ に対して，m｜m’」を示す．

任意の m，n，q，r∈Z に対して，m＝qn＋r ならば，gcd（m，n）＝gcd（n，r）．
例： gcd（117，51）＝gcd（51，15）＝gcd（15， 6）＝gcd（ 6， 3）＝gcd（ 3， 0）＝3b-2） n，k の任意の公倍数を m’ とする．
このとき，q1∈Z が存在して， m’＝ q1・n＝ q1・ q・ d ．
一方， q2∈Z が存在して， m’＝ q2・k＝ q2・ q’・d ．
ゆえに， q1・ q・ d ＝ q2・ q’・d ．
d ≠0 だから， q1・ q＝ q2・ q’ であり，q’｜ q1・ q ．
ところが，gcd（q ，q’ ）＝1 だから， q’｜ q1．
ゆえに， q’ ・n ｜q1 ・n だから，q’ ・q・ d ｜q1 ・n ．
すなわち，m｜ m’．

… 117＝2・51＋15… 51＝3・15＋ 6… 15＝2・ 6＋ 3…
6＝2・ 3＋ 0… 定理

Euclid（ギリシャ，330?-275? B.C.）
35

366離散数学及び演習 講義6

Euclid の互除法（Euclidean Algorithm）

証明

入力： m，n ∈Z
出力： gcd（ m，n ） 手順：
gcd（m，n）＝ gcd（n，r1）
r1＝mod（m，n） （0  r1＜｜n｜）＝ gcd（r1，r2）
r2＝mod（n，r1） （0  r2＜｜r1｜＝ r1）＝ gcd（r2，r3）
r3＝mod（r1，r2） （0  r3＜｜r2｜＝ r2）：＝ gcd（rk－1，rk）
rk＝mod（rk－2，rk－1）（0 rk＜｜rk－1｜＝ rk－1 ）＝ gcd（rk，0）0＝mod（rk－1，rk）＝ rk

任意の m，n，q，r∈Z に対して，m＝qn＋r ならば，gcd（m，n）＝gcd（n，r）．







「m と n のすべての非負公約数からなる集合と， n と r のすべての非負公約数からなる集合は等しい（Dm,n ＝ Dn,r ）」を示す．
等しい集合上の整除関係に関する最大元は等しい．

m と n のすべての非負公約数からなる集合を Dm,n とし，n と r のすべての非負公約数からなる集合を Dn,r とする．
任意の d∈Dm,n に対して，d｜m かつ d｜n だから，d｜m－qn ．
ゆえに，d｜r だから，d は n と r の非負公約数でもあり， d∈Dn,r．
したがって， Dm,n ⊆ Dn,r．
一方，任意の d’∈Dn,r に対して，d’｜n かつ d’｜r だから，d’｜qn＋r ．
ゆえに，d’｜m だから，d’ は m と n の非負公約数でもあり， d’∈Dm,n．
したがって， Dn,r ⊆Dm,n．
以上から，Dm,n ＝ Dn,r だから，gcd（m，n）＝gcd（n，r）．

37

38

Euclid の互除法の実現


入力： m，n ∈Z
出力： gcd（ m，n ）手順：
procedure gcd（m，n）；
begin
if n＝0 then return（｜m｜）；s ：＝ m ；s’：＝ n ；while s’≠ 0 do
begin
t ：＝s ；
s ：＝s’ ；s’ ：＝mod（t，s’）；end ；return（s） ；end

Euclid の互除法の実現（続き）
入力： m，n ∈Z 出力： gcd（ m，n ）

手順：
procedure gcd（m，n）；
begin
if n＝0then return（｜m｜）
else return（gcd（n，mod（m，n））
end

39

40

定理（停止性と正当性，計算量）




まとめ

Euclid の互除法は，有限回の計算ステップで停止し，任意のm，n∈Z に対して，gcd（m，n）を正しく計算する．







今回の講義


m，n∈Z （m  n）に対して，Euclid の互除法は最大┌┐logφ（n） 回以下の除法で計算を停止する．
ただし，φ＝再帰呼び出し

1+ 5

次回の講義
2

┌ u ┐は u の小数点以下を切り上げた整数．
u∈R に対して，41素数（教科書 pp.106-113）

今回の演習
m，n∈Z （m  n）に対して，n が10進 s 桁ならば，Euclid の互除法は最大 5s 回以下の除法で計算を停止する．

約数・倍数なし

427