『ひらがな電卓 Calc-H の数学ノート（第三版）』（PDF）（片山QZの定理）

1
ひらがな電卓 Calc-H の数学ノート（第三版）
片山博文 MZ
2014 年 8 月 24 日
1 準備
定義 1. 数 1, 2, 3, 4, · · · を自然数といい，その全体を N で表す．すなわち，N = {1, 2, 3, 4, · · · } とおく.
定義 2. 自然数に数 0, −1, −2, −3, · · · を合わせたものを整数といい，その全体を Z で表す．すなわち，
Z = {· · · , −3, −2, −1, 0, 1, 2, 3, · · · } とおく.
定義 3. x が集合 X に属することを x ∈ X と表す．
定義 4. 要素を持たない集合，すなわち空集合を ∅ で表す．
定義 5. 任意の命題 P, Q に対して，P ならば Q が成り立つ，ということを
P =⇒ Q
と表す．さらに P ならば Q が成り立ち，かつ，Q ならば P が成り立つとき，すなわち
P =⇒ Q
かつ
Q =⇒ P
であるとき，P と Q は同値であるといい，
P ⇐⇒ Q
と表す．
定義 6. 任意の述語 P(x) と任意の z に対して，
z ∈ {x | P(x)}
⇐⇒
P(z).
(1)
定理 1. 任意の述語 P(x), Q(x) に対して，
{x | P(x)} ∩ {x | Q(x)} = {x | P(x) かつ Q(x)}.
(2)
証明. X = {x | P(x)}，Y = {x | Q(x)}，Z = {x | P(x) かつ Q(x)} とおく．x ∈ X ならば，定義より
P(x) である．また，y ∈ Y ならば，定義より Q(y) である．z ∈ X ∩ Y ，すなわち z ∈ X かつ z ∈ Y ならば，
P(z) かつ Q(z) であるから，z ∈ Z である．逆に z ∈ Z であれば，P(z) かつ Q(z) であり，P(z) かつ Q(z)
ならば，z ∈ X かつ z ∈ Y であり，z ∈ X ∩ Y であると言える．すなわち任意の z について
z ∈X ∩Y
が成り立つ．よって X ∩ Y = Z である．
⇐⇒
z∈Z
(3)
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
定義 7. 任意の整数 x, y のうち最大のものを max(x, y) と表す．また，任意の整数 x, y のうち最小のものを
min(x, y) と表す．すなわち，
{
x
max(x, y) =
y
{
(x = y のとき),
(x < y のとき),
min(x, y) =
y
x
(x = y のとき),
(x < y のとき).
(4)
定理 2. 任意の整数 x, y に対して max(x, y) + min(x, y) = x + y である．
証明. x = y のときと，x < y のときで場合分けして確かめられる．
定理 3. 任意の整数 x, y に対して max(x − min(x, y), y − min(x, y)) = max(x, y) − min(x, y) である．
証明. x = y のときと，x < y のときで場合分けして確かめられる．
定義 8. 任意の集合 X に対して，X の最大値が存在するならば，その最大値を max(X) と表す．
定義 9. 任意の集合 X に対して，X の最小値が存在するならば，その最小値を min(X) と表す．
定義 10. 任意の自然数 x, y に対して，x 6= 0 かつ y 6= 0 のとき，それらの共通の正の倍数のうちで最小のも
のを最小公倍数といい，lcm(x, y) で表す．
定義 11. 任意の自然数 x, y に対して，x 6= 0 または y 6= 0 のとき，それらの共通の約数のうちで最大のもの
を最大公約数といい，gcd(x, y) で表す．
定義 12. 任意の自然数 n と任意の整数 a, b に対して，差 b − a が n の倍数であるとき，a と b は，n を法と
して互いに合同であるといい，a ≡ b (mod n) と表し，このような ≡ を含む式を合同式という．
定理 4. 任意の自然数 m1 , m2 について m1 m2 = lcm(m1 , m2 ) · gcd(m1 , m2 ) である．
証明. M = lcm(m1 , m2 ) かつ N = gcd(m1 , m2 ) とおく．m1 , m2 , M, N を素因数 p1 , p2 , · · · , pr により素
因数分解すると，
m1 =
M=
r
∏
pei i ,
i=1
r
∏
m2 =
max(ei , fi )
pi
,
N=
i=1
r
∏
f
pi i ,
i=1
r
∏
(5)
min(ei , fi )
pi
(6)
i=1
と表せる．すると，max(ei , fi ) + min(ei , fi ) = ei + fi であるから
MN =
r
r
r
r
∏
max(ei , fi ) ∏ min(ei , fi ) ∏ max(ei , fi ) + min(ei , fi ) ∏ ei + fi
pi
pi
=
pi
=
pi
i=1
i=1
となるが，これは
m1 m2 =
i=1
r
r
r
∏
∏
∏
f
e + fi
pei i
pi i =
pi i
i=1
(7)
i=1
i=1
(8)
i=1
と等しい．
定理 5. 任意の自然数 x, y について d = gcd(x, y) とおけば，gcd(x/d, y/d) = 1 である．
証明. x/d と y/d に 1 以外の公約数は存在しない．
2 ／
11
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
定理 6 (除法の定理). 任意の整数 a と任意の自然数 b に対して
a = qb + r
05r<b
かつ
(9)
を満たす整数 q, r の組がただ一つ存在する．
証明. 「a = qb + r かつ 0 5 r < b を満たす整数 q, r の組が存在する」という述語を P(a, b, q, r) で表すこと
にする．0 5 a < b とすると，P(a, b, 0, a) が満たされる．
a = b とする．数学的帰納法のために任意の 0 5 a0 < a なる任意の整数 a0 について，P(a0 , b, h, k) を満た
す整数 h, k が存在すると仮定する．0 5 a − b < a であるから，仮定より，P(a − b, b, q 0 , r 0 ) を満たす整数
q 0 , r0 が存在する．よって a − b = q 0 b + r0 ，これより a = (q 0 + 1)b + r0 となるので，P(a, b, q 0 + 1, r0 ) であ
る．よって，数学的帰納法により，a = b のとき，P(a, b, q, r) を満たす整数 q, r が存在する．
a < 0 とする．P(−a, b, q0 , r0 ) を満たす整数 q0 , r0 が存在する．よって −a = q0 b + r0 かつ 0 5 r0 < b で
ある．ここで，a = (−q0 )b + (−r0 ) = −(q0 + 1)b + (b − r0 ) であり，0 5 b − r0 < b であるから，a < 0 のと
き，P(a, b, −(q0 + 1), b − r0 ) を満たす q = −(q0 + 1)，r = b − r0 が存在する．
次に q, r の組の一意性を証明するために，ある整数 q1 , r1 , q2 , r2 に対して q1 > q2 かつ P(a, b, q1 , r1 ) か
つ P(a, b, q2 , r2 ) と仮定すると，
(q2 − q1 )b = −(r2 − r1 )
(10)
となるが，(q2 − q1 ) は自然数であるから，
(q2 − q1 )b = b
(11)
である．一方，仮定より，0 5 r1 < b かつ 0 5 r2 < b であるから，
|r2 − r1 | < b
(12)
となる．式 (10),(11),(12) は矛盾する．よって q1 = q2 でなければならない．また，これと式 (10) より，
r1 = r2 となる．これで q, r の組の一意性が証明された．
したがって，任意の整数 a と任意の自然数 b に対して，P(a, b, q, r) を満たす q, r の組がただ一つ存在する
ことが証明された．
定理 7 (ディオファントス方程式の解の存在条件). r を任意の自然数とする．任意の r 個の整数 a1 , a2 , · · · ,
ar に対して，a1 , a2 , · · · , ar の最大公約数 d が存在すると仮定する．このとき，ディオファントス方程式：
a1 x1 + a2 x2 + · · · + ar xr = k
(13)
を満たす整数解 x1 , x2 , · · · , xr が存在するための必要十分条件は，整数 k が d で割り切れることである．
証明. 集合 J を
J = {a1 x1 + a2 x2 + · · · + ar xr | x1 , x2 , · · · , xr ∈ Z}
(14)
とおく．証明すべきは，
k∈J
⇐⇒
k は d で割り切れる
(15)
である．J の要素のうち，正のものを集めた集合を K とおくと，K は空ではない可算集合なので最小値
min(K) > 0 が存在する．d0 = min(K) とおく．ここで任意の u, v に対して J において
3 ／
11
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
性質 i) u, v ∈ J ならば u + v ∈ J である，
性質 ii) u ∈ J ならば任意の整数 z に対して zu ∈ J である，
という性質 i), ii) が成り立つ．d0 ∈ K ⊆ J である．0 < u を満たす任意の u ∈ K について，除法の定理より
u = qd0 + r かつ 0 5 r < d0 を満たす整数 q, r が存在する．性質 ii) より，(−q)d0 ∈ J であり，性質 i) より，
r = u − qd0 = u + (−q)d0 ∈ J かつ r < d0 であるが，d0 は K のうち最小であったから，0 < r < d0 ではな
い．よって r = 0 かつ r ∈
/ K である．よって任意の u ∈ K について u が，u = qd0 ，すなわち d0 の倍数であ
ることが示された．
u < 0 と仮定すると，性質 ii) より，すなわち u ∈ J かつ u ∈
/ K について，−u ∈ K であるから，−u は d0
の倍数である．よって任意の u ∈ J について u は d0 の倍数である．
逆に u が d0 の倍数でなければ，u ∈
/ J である．なぜなら，u が d0 の倍数ではなく，かつ u ∈ J ならば，u
は d0 の倍数であるから，u が d0 の倍数ではないことに矛盾する．
a1 , a2 , · · · , ar はすべて J の元であるから，すべて d0 の倍数である．言い換えれば d0 は a1 , a2 , · · · , ar
の公約数である．d0 ∈ J であるから，
d0 = a1 h1 + a2 h2 + · · · + ar hr
(16)
を満たす整数 h1 , h2 , · · · , hr が存在する．e を a1 , a2 , · · · , ar の正の公約数とする．a1 h1 , a2 h2 , · · · , ar hr
がすべて e で割り切れるので，それらの和の d0 も e で割り切れる．よって e 5 d0 である．d0 は考えられ
る e のうち，最大のものである．したがって，d0 は，a1 , a2 , · · · , ar の正の公約数の最大のもの，すなわち
a1 , a2 , · · · , ar の最大公約数 d である．
2 本題
定理 8. 任意の自然数 m, n と任意の整数 a, x について，
x ≡ a (mod mn)
=⇒
x≡a
(mod m)
かつ
x≡a
(mod n).
(17)
証明. x ≡ a (mod mn) ならば，a − x は，mn の倍数である．よって a − x は，m の倍数であり，n の倍数
である．したがって，x ≡ a (mod m) かつ x ≡ a (mod n) である．
定理 9. 任意の自然数 m, n と任意の整数 a, b について，
a≡b
(mod n)
=⇒
ma ≡ mb (mod mn).
(18)
証明. 仮定より b − a は n で割り切れる．よって m · (b − a) は mn で割り切れる．したがって m · (b − a) ≡ 0
(mod mn) であり，ma ≡ mb (mod mn) である．
定義 13. 任意の自然数 m と整数 a に対して，m を法として a と合同な整数の全体を a の剰余類といい，
R(a, m) と表す．すなわち
R(a, m) = {b | a ≡ b (mod m)} = {mx + a | x ∈ Z} = mZ + a.
(19)
定理 10. 任意の自然数 m と任意の整数 r, a に対して，
r ∈ R(a, m)
⇐⇒
r≡a
4 ／
11
(mod m).
(20)
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
証明. 定義より明らか．
定理 11. 任意の自然数 m1 , m2 と任意の整数 y1 , y2 に対して，
{
y1 ≡ y2
(mod lcm(m1 , m2 ))
⇐⇒
y1 ≡ y2
y1 ≡ y2
(mod m1 ),
(mod m2 ).
(21)
証明. 左辺を仮定する．y2 − y1 は lcm(m1 , m2 ) の倍数である．すると最小公倍数の定義より，y2 − y1 は m1
の倍数であり，m2 の倍数である．よって y1 ≡ y2 (mod m1 ) かつ y1 ≡ y2 (mod m2 ) である．したがって左
辺を仮定して右辺を証明できた．
逆に，右辺を仮定する．y1 ≡ y2 (mod m1 ) ならば，y2 − y1 は m1 の倍数である．y1 ≡ y2 (mod m2 ) な
らば，y2 − y1 は m2 の倍数である．y2 − y1 は m1 の倍数であり，m2 の倍数であるから，最小公倍数の定義
より，y2 − y1 は lcm(m1 , m2 ) の倍数である．よって y1 ≡ y2 (mod lcm(m1 , m2 )) であるから，右辺を仮定
して左辺を証明できた．
定理 12. 任意の自然数 m と任意の整数 x, y に対して次の式が成り立つ．
x≡y
⇐⇒
(mod m)
R(x, m) = R(y, m).
(22)
証明. x ≡ y (mod m) ならば
R(x, m) = {z | x ≡ z
(mod m)} = {z | y ≡ z
(mod m)} = R(y, m)
(23)
が得られる．逆に R(x, m) = R(y, m) を仮定すると，任意の z に対して
z ∈ R(x, m)
⇐⇒
z ∈ R(y, m)
(24)
⇐⇒
y≡z
(25)
であるから，
x≡z
(mod m)
(mod m)
であり，矛盾を避けると x ≡ y (mod m) が得られる．
定理 13 (中国剰余定理). r を自然数とし，m1 , m2 , · · · , mr を互いに素な自然数とすると，任意の整数
a1 , a2 , · · · , ar に対して，連立合同式


x ≡ a1


x ≡ a2
..


.



x ≡ ar
(mod m1 ),
(mod m2 ),
(26)
(mod mr )
は，整数解 x を持つ．また，M = m1 m2 · · · mr とすると，解は M を法として一意的に存在する．
証明. まず，整数解が 2 個以上あったと仮定して，それらを x1 , x2 とおく．すると

x1 ≡ a1




x1 ≡ a2
..


.



x1 ≡ ar
(mod m1 ),
(mod m2 ),
かつ
(mod mr )
5 ／

x2 ≡ a1




x2 ≡ a2
..


.



x2 ≡ ar
11
(mod m1 ),
(mod m2 ),
(mod mr )
(27)
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
となるが，x1 ≡ ai ≡ x2 (mod mi ) より，x1 ≡ x2 (mod mi ) でなければならない．ここで定理 11 より
x1 ≡ x2
x1 ≡ x2
..
.
x1 ≡ x2
(mod lcm(m1 , m2 )),
(mod lcm(m2 , m3 )),
(28)
(29)
(mod lcm(mr−1 , mr ))
(30)
であるから，定理 11 と lcm(mi , mj , mk ) = lcm(lcm(mi , mj ), mk ) より
x1 ≡ x2
..
.
(mod lcm(m1 , m2 , m3 )),
(31)
x1 ≡ x2
(mod lcm(mr−2 , mr−1 , mr )).
(32)
このように定理 11 を繰り返し適用することで，
x1 ≡ x2
(mod lcm(m1 , m2 , · · · , mr ))
(33)
が得られる．ここで m1 , m2 , · · · , mr は互いに素であるから，M = lcm(m1 , m2 , · · · , mr ) である．よって，
x1 ≡ x2
(mod M )
(34)
であり，整数解が存在すれば M を法として一意的に存在すると言える．
さて，1 5 i 5 r に対して，ni = M/mi とおく．
gcd(ni , nj ) =
gcd(ni , nj , nk ) =
..
.
..
.
gcd(n1 , n2 , · · · , nr ) =
M
(i 6= j),
mi mj
M
(i, j, k は互いに異なる),
mi mj mk
..
.
M
=1
(1, 2, · · · , r は互いに異なる).
m1 m2 · · · mr
(35)
(36)
(37)
(38)
であるから，n1 , n2 , · · · , nr の最大公約数は 1 である．したがって，定理 7 より，整数 t1 , t2 , · · · , tr が存在
して，
n1 t 1 + n2 t 2 + · · · + nr t r = 1
(39)
を満たす．i 6= j ならば，ni は mj の倍数である．よって，
ni t i ≡ 0
(mod mj )
(i 6= j のとき).
(40)
ni ti ≡ 1 (mod mj )
(i = j のとき)
(41)
これと式 (39) より，
である．まとめると，
{
ni ti ≡
1
0
(mod mj )
(mod mj )
(i = j のとき)
(i 6= j のとき)
(42)
である．ここで
z = a1 n1 t1 + a2 n2 t2 + · · · + ar nr tr
6 ／
11
(43)
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
とおくと，


z ≡ a1


z ≡ a2
..


.



z ≡ ar
(mod m1 ),
(mod m2 ),
(44)
(mod mr )
となるので，z は式 (26) の解となる．
定理 14. 任意の自然数 m1 , m2 と任意の整数 a1 , a2 に対して，N = gcd(m1 , m2 ) とおく．このとき，
z ∈ R(a1 , m1 ) ∩ R(a2 , m2 )
⇐⇒
z ≡ a1 ≡ a2
(mod N ).
(45)
証明. 次の式が成り立つ．
z ∈ R(a1 , m1 ) ∩ R(a2 , m2 ) となる z が存在する
⇐⇒ m1 x1 + a1 = m2 x1 + a2 を満たす整数 x1 , x2 が存在する
⇐⇒ m2 x1 − m1 x1 = a1 − a2 を満たす整数 x1 , x2 が存在する
(46)
(47)
(48)
⇐⇒
⇐⇒
(49)
(50)
a1 − a2 は N の倍数
a1 ≡ a2 (mod N ).
⇐⇒
a1 − a2 ≡ 0 (mod N )
さらに，z = m1 x1 + a1 = m2 x2 + a2 となる整数 x1 , x2 が存在すれば，m1 が N の倍数であり，m2 が N
の倍数であるから，z ≡ a1 (mod N ) かつ z ≡ a2 (mod N ) となる．逆に，z ≡ a1 (mod N ) かつ z ≡ a2
(mod N ) となれば，z = m1 x1 + a1 = m2 x2 + a2 となる整数 x1 , x2 が存在して，z ∈ R(a1 , m1 ) ∩ R(a2 , m2 )
となる．よって正しい．
定理 15. 任意の自然数 m1 , m2 に対して，M = lcm(m1 , m2 )，N = gcd(m1 , m2 ) とおく．すると，
lcm(m1 /N, m2 /N ) = M/N.
(51)
証明. m1 , m2 , M, N を素因数 p1 , p2 , · · · , pr で素因数分解すると，式 (5),(6) のようになる．ここで
m1 /N =
r
∏
e − min(ei , fi )
pi i
,
m2 /N =
i=1
r
∏
f − min(ei , fi )
pi i
(52)
i=1
となり，
r
∏
max(ei − min(ei , fi ), fi − min(ei , fi ))
lcm(m1 /N, m2 /N ) =
pi
=
i=1
r
∏
max(ei , fi ) − min(ei , fi )
pi
i=1
r
∏
=
i=1
r
∏
(53)
(54)
max(ei , fi )
pi
= M/N
(55)
min(ei , fi )
pi
i=1
である．
定理 16. 任意の自然数 a, b に対して整数 x が a の倍数であり，x が b の倍数であれば，x は lcm(a, b) の倍数
である．
7 ／
11
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
証明. 最小公倍数の定義より明らか．
定理 17. 任意の自然数 m1 , m2 に対して，N = gcd(m1 , m2 ) とおく．このとき，m1 は lcm(m1 /N, N ) の倍
数である．
証明. m1 が m1 /N の倍数であり，かつ m1 が N の倍数であるから，定理 16 より正しい．
定理 18 (片山 QZ の定理). 任意の自然数 m1 , m2 と任意の整数 a1 , a2 に対して，M = lcm(m1 , m2 )，
N = gcd(m1 , m2 ) とおく．このとき，
a1 ≡ a2
(mod N )
(56)
(mod m1 )
(mod m2 )
(57)
ならば
{
y ≡ a1
y ≡ a2
を満たす y が M を法として一意的に存在し，y は a1 , m1 , a2 , m2 より計算可能である．
証明. 任意の自然数 m1 , m2 と任意の整数 y, a1 , a2 に対して，式 (57) が満たされることを，述語
Q(y, a1 , m1 , a2 , m2 ) で表すことにする．
整数 y1 , y2 に対して，Q(y1 , a1 , m1 , a2 , m2 ) かつ Q(y2 , a1 , m1 , a2 , m2 ) ならば，y1 ≡ y2 ≡ a1 (mod m1 )
かつ y1 ≡ y2 ≡ a2 (mod m2 ) でなければならない．よって定理 11 より，y1 ≡ y2 (mod M ) となる．した
がって，式 (57) を満たす整数解が存在するならば，M を法としてただ一つである．
m1 , m2 が互いに素ならば，N = 1 であり，a1 ≡ a2 (mod N ) である．このとき，M = m1 m2 となり，中
国剰余定理より，Q(y, a1 , m1 , a2 , m2 ) であり，y は a1 , m1 , a2 , m2 より計算可能である．
m1 , m2 が互いに素ではないと仮定する．このとき，N > 1 である．n1 = m1 /N ，n2 = m2 /N とお
く．n1 と n2 は，自然数であり，互いに素であるから，lcm(n1 , n2 ) = n1 n2 であり，中国剰余定理より，
Q(y 0 , a1 , n1 , a2 , n2 ) を満たす整数解 y 0 が
n1 n2 = (m1 /N )(m2 /N ) = m1 m2 /N 2 = M N/N 2 = M/N
(58)
を法としてただ一つ存在し，y 0 は a1 , m1 , a2 , m2 より計算可能である．よって
{
y 0 ≡ a1
y 0 ≡ a2
(mod n1 )
(mod n2 )
(59)
である．y 0 は，M/N を法として一意的に存在するから，除法の定理を用いると，ある整数 h, k により，
y 0 = (M/N )h + k
(0 5 k < h)
(60)
と書ける．h, k は a1 , m1 , a2 , m2 より計算可能である．M/N が n1 = m1 /N の倍数であり，n2 = m2 /N の
倍数であるから，
{
y 0 ≡ k ≡ a1
y 0 ≡ k ≡ a2
(mod n1 )
(mod n2 )
(61)
である．ここで
y = Mh + k
8 ／
11
(62)
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
とおくと，y は a1 , m1 , a2 , m2 より計算可能であり，M は m1 , m2 の倍数であるから，
{
y ≡ k ≡ a1
y ≡ k ≡ a2
(mod m1 )
(mod m2 )
(63)
となるので，Q(y, a1 , m1 , a2 , m2 ) である．
y が存在するためには，定理 14 より，a1 ≡ a2 (mod N ) でなければならない．よって，一般に a1 ≡ a2
(mod N ) のとき，式 (57) を満たす y が常に存在し，y は a1 , m1 , a2 , m2 より計算可能である．
3 結論
任意の自然数 m1 , m2 と任意の整数 a1 , a2 に対して，M = lcm(m1 , m2 )，N = gcd(m1 , m2 ) とおく．こ
のとき，a1 6≡ a2 (mod N ) ならば，定理 14 より R(a1 , m1 ) ∩ R(a2 , m2 ) = ∅ である．a1 ≡ a2 (mod N ) の
ときは，定理 18 より R(a1 , m1 ) ∩ R(a2 , m2 ) = R(y, M ) を満たす y が存在し，a1 , m1 , a2 , m2 より計算可
能である．まとめると，
{
∅
R(a1 , m1 ) ∩ R(a2 , m2 ) =
R(y, M )
(a1 ≡
6 a2
(a1 ≡ a2
(mod N ) のとき),
(mod N ) のとき),
(64)
である．ここに定理 18 より y は a1 , m1 , a2 , m2 から計算可能である．
このことを確かめるために，実行環境 Intel Core i5, CPU 2.5GHz と日本語版 64 ビット Windows 7 で
図 1, 図 2, 図 3 のような C++ のテストプログラム katatest.cpp を作り，C++ コンパイラ g++ (tdm64-2)
4.8.1 でコンパイルして，2 から 100 までの法についてテストが成功した．実行に要した時間は約 3 分 50 秒．
参考文献
[1]『解析入門 1』松坂和夫（まつざか・かずお），1997 年，株式会社岩波書店
[2]『工科系のための初等整数論入門』楫元（かじ・はじめ），2000 年，株式会社培風館
[3]『プログラムの背景』http://www2.cc.niigata-u.ac.jp/~takeuchi/tbasic/BackGround/
[4]『中国剰余定理』藤田博司，2013 年，
http://tenasaku.com/academia/notes/chinese-remainder.pdf
[5]『Yahoo!知恵袋』http://chiebukuro.yahoo.co.jp
[6]『ウィキペディア (Wikipedia)』http://ja.wikipedia.org
[7]『２ちゃんねる』http://2ch.net
図1
1
2
3
4
5
C++ のテストプログラム katatest.cpp（次のページへ続く）
// katatest . cpp --- 片山 Q Z の定理をテストする．
// Copyright ( C ) 2014 Katayama Hirofumi MZ < katayama . hirofumi . mz@gmail . com >.
# include < cstdio >
# include < cassert >
using namespace std ;
6
7
// 法の最大値．
9 ／
11
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
図2
8
C++ のテストプログラム katatest.cpp（続き，次のページに続く）
# define MAX 100
9
10
11
12
13
14
15
// エラー処理．
void error ( int num , int a1 , int m1 , int a2 , int m2 , int M , int N )
{
printf ( " ERROR #% d at ( a1 :% d , m1 :% d , a2 :% d , m2 :% d , M :% d , N :% d )\ n " ,
num , a1 , m1 , a2 , m2 , M , N );
}
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// ユークリッド互除法で最大公約数を求める．
int mygcd ( int x , int y )
{
assert ( x != 0 || y != 0);
if ( x < 0) x = -x ;
if ( y < 0) y = -y ;
if ( y == 0) return x ;
for (;;)
{
int z = x % y ;
if ( z == 0) break ;
x = y;
y = z;
}
return y ;
}
33
34
35
36
37
38
39
// 最小公倍数を求める．
int mylcm ( int x , int y )
{
assert ( x != 0 || y != 0);
return x * y / mygcd (x , y );
}
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
// 拡張ユークリッド互除法．
// a >0 , b >0 に対して， ax + by = d となる x , y と d = gcd (a , b ) を求める．
// d は戻り値．
int gcdx ( int & x , int & y , int a , int b )
{
assert ( a > 0 || b > 0);
int r0 = a , r1 = b , x0 = 1 , x1 = 0 , y0 = 0 , y1 = 1;
while ( r1 > 0)
{
int q1 = r0 / r1 ;
int r2 = r0 % r1 ;
int x2 = x0 - q1 * x1 ;
int y2 = y0 - q1 * y1 ;
r0 = r1 ; r1 = r2 ; x0 = x1 ; x1 = x2 ; y0 = y1 ; y1 = y2 ;
}
x = x0 ; y = y0 ;
return r0 ;
}
59
60
61
62
63
64
65
66
67
68
// 中国剰余定理の解を求める．
int chrem ( int a1 , int m1 , int a2 , int m2 )
{
assert ( m1 > 0 && m2 > 0);
int x , y ;
int d = gcdx (x , y , m1 , m2 );
assert ( d == 1);
return a1 + ( a2 - a1 ) * x * m1 ;
}
69
70
71
72
73
74
75
76
// 片山 Q Z の定理の y と，最小公倍数 M と，最大公約数 N を求める．
// y が存在すれば 1 を，存在しなければ 0 を返す．
int katayama ( int & y , int & M , int & N , int a1 , int m1 , int a2 , int m2 )
{
N = mygcd ( m1 , m2 ); M = m1 * m2 / N ;
// printf (" a1 :% d , m1 :% d , a2 :% d , m2 :% d , M :% d , N :% d \ n " ,
//
a1 , m1 , a2 , m2 , M , N );
77
78
79
80
81
if (( a2 - a1 ) % N != 0) return 0;
if ( N != 1)
{
m1 /= N ; m2 /= N ;
10 ／
11
片山博文 MZ
ひらがな電卓 Calc-H の数学ノート（第三版）
図3
}
y = chrem ( a1 , m1 , a2 , m2 );
while ( y < 0) y += M ;
y %= M ;
return 1;
82
83
84
85
86
87
C++ のテストプログラム katatest.cpp（続き）
}
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
// 主処理．
int main ( void )
{
for ( int m1 = 1; m1 <= MAX ; ++ m1 )
{
for ( int m2 = 1; m2 <= MAX ; ++ m2 )
{
for ( int a1 = 0; a1 < m1 ; ++ a1 )
{
for ( int a2 = 0; a2 < m2 ; ++ a2 )
{
int y , M , N ;
int f = katayama (y , M , N , a1 , m1 , a2 , m2 );
if (! f && ( a2 - a1 ) % N == 0)
{
error (1 , a1 , m1 , a2 , m2 , M , N );
return 1;
}
if (! f )
continue ;
f = 0;
for ( int k = 0; k < M ; ++ k )
{
if ( a1 % m1 == k % m1 && a2 % m2 == k % m2 )
{
if ( k == y % M )
{
if ( f )
{
error (2 , a1 , m1 , a2 , m2 , M , N );
return 2;
}
f = 1;
}
}
}
if (! f )
{
printf ( " y :% d \ n " , y );
error (3 , a1 , m1 , a2 , m2 , M , N );
return 3;
}
}
}
}
}
printf ( " success \ n " );
return 0;
}
11 ／
11

Download Report