初等整数論 [3]
●不定方程式と拡張ユークリッドの互除法
変数の個数が式の本数よりも多い方程式を「不定方程式」といいます。一次不定方程式 \(ax + by = c \ (c \ne 0)\) は、\(a, b, c\) が整数で、\(c\) が \(a\) と \(b\) の最大公約数の倍数であるとき、整数解を持つことが証明されています。これを「ベズーの等式」といいます。ベズーの等式は「拡張ユークリッドの互除法」を使って簡単に解くことができます。
拡張といっても原理はユークリッドの互除法とまったく同じです。\(\gcd(a, b)\) を求めるときに一組の解 \((x, y)\) もいっしょに見つける、というものです。ポイントは数を \(x = xa \times a + xb \times b\) の形で表すところです。次の図を見てください。
\(x = xa \times a + xb \times b, \ y = ya \times a + yb \times b\) とおき、
\(x, y\) に対してユークリッドの互除法を適用する (初期値は \(xa = 1, \ xb = 0, \ ya = 0, \ yb = 1 \))
\(x\) と \(y\) の商を \(q\), 余りを \(z\) とすると
\(\begin{eqnarray}
z &=& x - q \times y = xa \times a + xb \times b - q \times (ya \times a + yb \times b) \\
&=& (xa - q \times ya) \times a + (xb - q \times yb) \times b \\
&=& za \times a + zb \times b
\end{eqnarray}\)
となる
次は \(y\) と \(z\) で同様の処理を繰り返す
具体的には変数の値を
\(\begin{array}{l}
x, xa, xb = y, ya, yb \\
y, ya, yb = z, za, za
\end{array}\)
のように更新して処理を繰り返す
\(y\) が \(0\) になったとき、\(x\) が \(a\) と \(b\) の最大公約数で \((xa, xb)\) が一つの解となる
具体的な例を示しましょう。\(4321 \times x + 1234 \times y = \gcd(4321, 1234)\) を解いてみます。
(x, xa, xb) (y, ya, yb) q (z, za, zb)
------------------------------------------------------
(4321, 1, 0) (1234, 0, 1) 3 (619, 1, -3)
(1234, 0, 1) (619, 1, -3) 1 (615, -1, 4)
(619, 1, -3) (615, -1, 4) 1 (4, 2, -7)
(615, -1, 4) (4, 2, -7) 153 (3, -307, 1075)
(4, 2, -7) (3, -307, 1075) 1 (1, 309, -1082)
(3, -307, 1075) (1, 309, -1082) 3 (0, -1234, 4321)
(1, 309, -1082) (0, -1234, 4321)
4321 * 309 + 1234 * (-1082) = 1 になる
一般解は次のように求めることができます。
\(\begin{array}{clclcl}
& 4321 \times x & + & 1234 \times y & = & 1 \\
- & 4321 \times 309 & + & 1234 \times (-1082) & = & 1 \\
\hline
& 4321 \times (x - 309) & +& 1234 \times (y - (-1082)) &= & 0
\end{array}\)
となるから \(4321 \times (x - 309) = -1234 \times (y + 1082)\) が成り立つ
\(-1234\) は \(x - 309\) の約数で \(4321\) は \(y + 1082\) の約数だから、\(t\) を整数とすると、
\(\begin{array}{ll}
x - 309 = -1234 \times t & \therefore \ x = 309 - 1234 \times t \\
y + 1082 = 4321 \times t & \therefore \ y = -1082 + 4321 \times t
\end{array}\)
それでは、実際に値を代入して (x, y) の組を求めてみましょう。
t x y z = 4321 * x + 1234 * y
-----------------------------------------
-4 5245 -18366 1
-3 4011 -14045 1
-2 2777 -9724 1
-1 1543 -5403 1
0 309 -1082 1
1 -925 3239 1
2 -2159 7560 1
3 -3393 11881 1
4 -4627 16202 1
ところで、Python のライブラリ SymPy には最大公約数を求める関数 gcd(a, b) や、拡張ユークリッドの互除法を行う関数 gcdex(a, b) が用意されいます。簡単な使用例を示します。
>>> import sympy as sy
>>> sy.gcd(4321,1234)
1
>>> sy.gcdex(4321,1234)
(309, -1082, 1)
●中国の剰余定理
中国の剰余定理 (Chinese remainder theorem) は整数の剰余に関する定理です。具体的には、連立合同式に解があることを示す定理です。
- 証明 (解の存在)
- 2 つの整数 \(m, \ n\) が互いに素であれば、以下の式 (ベズーの等式) が成立する
\(m \times X + n \times Y = 1\)
- 上式を満たす整数 \(X, \ Y\) が必ず存在する
- 上式に \(\mathrm{mod} \ n, \ \mathrm{mod} \ m\) を適用すると、以下の式が成り立つ
\(\begin{array}{l}
m \times X \equiv 1 \pmod n \\
n \times Y \equiv 1 \pmod m
\end{array}\)
- ここで \(x = a \times n \times Y + b \times m \times X\) として、\(\mathrm{mod} \ n, \mathrm{mod} \ m\) を適用する
\(\begin{array}{l}
x \equiv a \pmod m \\
x \equiv b \pmod n
\end{array}\)
- \(x\) は与えられた連立合同式の解となる
SymPy には中国人の剰余定理を計算する関数 crt([m, n, ...], [a, b, ...]) が用意されています。関数 crt() は m で割った余りが a で、n で割った余りが b となる整数を求めます。
簡単な使用例を示します。3 で割ると 2 余り、5 で割ると 4 余る数を求めます。
>>> sy.ntheory.modular.crt([3,5],[2,4])
(14, 15)
>>> 14 % 3
2
>>> 14 % 5
4
解は 14 になります。確かに 14 % 3 は 2 に、14 % 5 は 4 になります。解を合同式で表すと \(x \equiv 14 \pmod {15}\) になります。
●中国剰余定理の一般化
中国の剰余定理は合同式の本数を増やしても成立します。
- 証明 (数学的帰納法)
- \(k = 1\) のときは明らかに成立する
- \(k = t\) のとき、中国剰余定理が成立すると仮定する
\(
x \equiv a_i \pmod {n_i} \quad (i = 1, \ 2, \ \cdots, \ t)
\)
- 上式を満たす整数 \(x\) の値を \(a_0\) とすると、次の合同式で表すことができる
\(
x \equiv a_0 \pmod {n_1 \times n_2 \times \cdots \times n_t}
\)
- t + 1 本の連立合同式は以下に示す 2 本の連立合同式と同じ
\(\begin{array}{l}
x \equiv a_0 \pmod {n_1 \times n_2 \times \cdots \times n_t} \\
x \equiv a_{t+1} \pmod {n_{t+1}}
\end{array}\)
- \(n_1 \times n_2 \times \cdots \times n_t\) と \(n_{t+1}\) は互いに素である
- 二元の結果より t + 1 本の連立合同式の解 \(x\) は \(0\) 以上 \(n_1 \times n_2 \times \cdots \times n_{t+1}\) 未満の範囲にただ一つ存在する
Sympy の関数 crt() は一般化に対応しています。実際に試してみましょう。
- \(x \equiv 2 \pmod 3, \ x \equiv 3 \pmod 5, \ x \equiv 2 \pmod 7\)
>>> sy.ntheory.modular.crt([3,5,7],[2,3,2])
(23, 105)
>>> 23 % 3
2
>>> 23 % 5
3
>>> 23 % 7
2
\(x \equiv 2 \pmod 3, \ x \equiv 3 \pmod 5, \ x \equiv 2 \pmod 7, \ x \equiv 4 \pmod {11}\)
>>> sy.ntheory.modular.crt([3,5,7,11],[2,3,2,4])
(653, 1155)
>>> 653 % 3
2
>>> 653 % 5
3
>>> 653 % 7
2
>>> 653 % 11
4
●互いに素でない場合
次は、中国剰余定理を整数 \(n_i \ (i = 1, 2, \ldots, k)\) が互いに素でない場合に拡張します。
- 中国剰余定理 (二元で互いに素でない場合)
\(\begin{eqnarray}
\left\{
\begin{array}{l}
x \equiv a \pmod m \\
x \equiv b \pmod n
\end{array}
\right.
\iff a \equiv b \pmod {\gcd(m, n)}
\end{eqnarray}\)
- \(x\) は \(0\) 以上 \(\mathrm{lcm}(m, n)\) 未満の範囲内にただ一つ存在する
- 必要十分条件は \(a \equiv b \pmod {\gcd(m, n)}\)
\(\mathrm{lcm}(m, n)\) は \(m\) と \(n\) の最小公倍数を表します。\(m\) と \(n\) が互いに素であれば \(\gcd(m, n) = 1\) になるので、必要十分条件を満たします。
- 証明1
- \(d = \gcd(m, n)\) とすると以下の式 (ベズーの等式) が成立する
\(m \times X + n \times Y = d\)
- \(a \equiv b \pmod {\gcd(m, n)}\) より \(b - a\) は \(d\) で割り切れる
- \(s = (b - a) / d\) とおくと次式になる
\(
s \times m \times X + s \times n \times Y = b - a
\)
- \(x = s \times m \times X + a \ (= b - s \times n \times Y)\) として \(\mathrm{mod} \ n, \mathrm{mod} \ m\) を適用する
\(\begin{array}{l}
x \equiv a \pmod m \\
x \equiv b \pmod n
\end{array}\)
- x は与えられた連立合同式を満たす
- \(x \ \% \ \mathrm{lcm}(m, n)\) とすれば、\(0\) 以上 \(\mathrm{lcm}(m, n)\) 未満の解となる
- 証明2
- 連立合同式に解 \(x\) が存在するとき、\(m\) は \(\gcd(m, n)\) の倍数だから \(x \equiv a \pmod m\) より式 (1) が成立
\(x \equiv a \pmod {\gcd(m, n)} \quad (1) \)
- 同様に、\(n\) は \(\gcd(m, n)\) の倍数だから \(x \equiv b \pmod n\) より式 (2) が成立
\(x \equiv b \pmod {\gcd(m, n)} \quad (2)\)
- 式 (1), (2) より \(a \equiv b \pmod {\gcd(m, n)}\) が成立する
もちろん、合同式の本数を増やしても成立します。
- 中国剰余定理 (互いに素でない場合)
\(
x \equiv a_i \pmod {n_i} \iff a_i \equiv a_j \pmod {\gcd(n_i, n_j)}, \quad (i, j = 1, 2, \cdots, k)
\)
- \(x\) は \(0\) 以上 \(\mathrm{lcm}(n_1, n_2, \cdots, n_k)\) 未満の範囲にだた一つ存在する
- 必要十分条件は任意の i, j に対して \(a_i \equiv a_j \pmod {\gcd(n_i, n_j)}\)
証明は互いに素の場合と同様 (数学的帰納法) にできるので省略します。
それでは実際に試してみましょう。
>>> sy.ntheory.modular.crt([3,5],[2,4])
(14, 15)
>>> sy.ntheory.modular.crt([30,50],[20,40])
(140, 150)
>>> 140 % 30
20
>>> 140 % 20
0
>>> 140 % 50
40
>>> sy.ntheory.modular.crt([3,5,7],[2,3,2])
(23, 105)
>>> sy.ntheory.modular.crt([30,50,70],[20,30,20])
(230, 1050)
>>> 230 % 30
20
>>> 230 % 50
30
>>> 230 % 70
20
>>> sy.ntheory.modular.crt([3,5,7,11],[2,3,2,4])
(653, 1155)
>>> sy.ntheory.modular.crt([30,50,70,110],[20,30,20,40])
(6530, 11550)
>>> 6530 % 30
20
>>> 6530 % 50
30
>>> 6530 % 70
20
>>> 6530 % 110
40
●位数と原始根
互いに素となる整数 \(a\) と \(n\) に対して、合同式 \(a^k \equiv 1 \pmod n\) を満たす最小の正整数 \(k\) を、\(n\) を法とする \(a\) の位数 (order of a modulo n) といい、\(ord_n(a)\) や \(O_n(a)\) と記述します。オイラーの定理 \(a^{\varphi(n)} \equiv 1 \pmod n\) より、位数 \(k\) は \(\varphi(n)\) 以下になります。そして、\(\varphi(n)\) と位数が等しいとき、\(a\) を \(n\) の原始根 (primitive root of n) と呼びます。
簡単な例を示しましょう。\(2^k \mod {11}, \ 3^k \mod {11}, \ (k = 1, 2, \ldots, 10)\) を計算します。
>>> for k in range(1, 11): print(2 ** k % 11, end=" ")
...
2 4 8 5 10 9 7 3 6 1
>>> for k in range(1, 11): print(3 ** k % 11, end=" ")
...
3 9 5 4 1 3 9 5 4 1
mod 11 の世界では、2 の位数は 10 で、3 の位数は 5 になりました。n が素数のとき \(\varphi(n) = n - 1\) になるので、\(\varphi(11)\) は 10 になります。したがって、2 は 11 の原始根ですが、3 は 11 の原始根ではありません。それから、2 ** k % 11 (k = 1, ..., 10) の計算結果を見ると、1 から 10 までの値がひとつずつ現れていますね。これは原始根で一般的に成立する性質 (定理) です。
- 定理１
- \(a\) が \(n\) の原始根であるとき、\(a, a^2, \ldots, a^{n-1}\) を \(n\) で割った余りはすべて異なり、\(1\) から \(n - 1\) までの値がひとつずつ現れる
- 証明 (背理法)
- \(a^i \equiv a^j \pmod n\) となる自然数 \(i, j \ (n - 1 \geqq i \gt j)\) が存在すると仮定する
- 式を変形する
\(\begin{array}{l}
a^i \equiv a^j \\
a^i - a^j \equiv 0 \\
a^j \times (a^{i-j} - 1) \equiv 0
\end{array}\)
- \(a\) と \(n\) は互いに素なので、\(a^j\) で除算することができる
\(\begin{array}{l}
a^{i-j} - 1 \equiv 0 \pmod n \\
a^{i-j} \equiv 1 \pmod n
\end{array}\)
- \(n - 1\) よりも小さな整数 \(i - j\) が位数となるため、原始根の定義に反する
- \(a^i \equiv a^j \pmod n\) となる自然数 \(i, j\) は存在しない (\(n\) で割った余りはすべて異なる)
\(n\) が素数のとき、\(n\) の原始根 \(a\) が必ず存在することが知られています。これを「原始根の存在定理」とか「原始根定理」といいます。\(n\) の原始根が存在するとき、その個数は \(\varphi(n - 1)\) になります。
それから、位数には次の性質 (定理) があります。
- 定理２
- \(\mathrm{mod} \ n\) における \(a\) の位数を \(s\) とする
- \(a^k \equiv 1 \pmod n\) を満たすならば、\(k\) は \(s\) の倍数になる
たとえば、mod 11 における 3 の位数は 5 ですが、3k % 11 (k = 1, 2, ..., 10) を計算すると、k = 5 * 2 = 10 のときも 1 になります。
- 証明
- \(k = p \times s + q\) とおく
\(\begin{array}{l}
a^k \equiv 1 \\
a^{p \times s + q} \equiv 1 \\
(a^s)^p \times a^q \equiv 1
\end{array}\)
- \(s\) は位数なので、\(a^s \equiv 1 \pmod n\) より \(a^q \equiv 1 \pmod n\) となる
- \(q\) は余りなので \(0 \leqq q \lt s\) だが、\(q \ne 0\) とすると位数の定義に反する
- よって \(q = 0\) となり、\(k\) は \(s\) の倍数 (\(k = p \times s\)) であることが示された
●ウィルソンの定理
位数と原始根を使うと、ウィルソンの定理 (Wilson's theorem) を簡単に証明することができます。
- ウィルソンの定理
- \(n\) が素数ならば、\((n - 1)! \equiv -1 \pmod n\) が成立する
- 逆に、整数 \(n \gt 1\) に対し、\((n - 1)! \equiv -1 \pmod n\) ならば、\(n\) は素数である
実際に試してみましょう。
>>> for x in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
... print(x, fact(x - 1) % x)
...
2 1
3 2
5 4
7 6
11 10
13 12
17 16
19 18
23 22
29 28
31 30
37 36
41 40
43 42
47 46
確かに (n - 1)! % n は n - 1 (-1 % n = n - 1) になります。n = 2 の場合、定理が成り立つのは自明なので、奇素数の場合について証明します。
- 証明
- 素数 n の原始根を a とすると以下の式が成り立つ
\(\begin{array}{l}
a \times a^2 \times \cdots \times a^{n-1} \equiv 1 \times 2 \times \cdots \times (n - 1) \pmod n \\
a^m \equiv (n - 1)! \pmod n, \quad \left(m = 1 + 2 + \cdots + (n - 1) = \dfrac{n(n - 1)}{2}\right)
\end{array}\)
- \(a^{2m}\) にフェルマーの小定理 \(a^{n-1} \equiv 1 \pmod n\) を適用する
\(\begin{array}{l}
a^{2m} = a^{n(n-1)} = (a^{n-1})^n \\
a^{2m} \equiv 1^n \pmod n \\
(a^m + 1) \times (a^m - 1) \equiv 0 \pmod n
\end{array}\)
- \(a^m \equiv 1\) と仮定すると、m は n - 1 の倍数になる (m は n - 1 で割り切れる)
\(
\dfrac{m}{p - 1} = \dfrac{n(n - 1)}{2(n - 1)} = \dfrac{n}{2}
\)
- n は奇素数だから n / 2 は整数にならない、よって \(a^m \equiv -1 \pmod n\)
- \(a^m \equiv (n - 1)!\) より \((n - 1)! \equiv -1 \pmod n\) が成り立つ
- 逆に、\(n\) を合成数とする
- \(n\) を割り切る素数 \(q\) (\(2 \leqq q \lt n)\) が存在するので \((n - 1)! \equiv 0 \pmod q\) になる
- \((n - 1)! \equiv -1 \pmod n\) であれば \((n - 1)! \equiv -1 \pmod q\) になるので矛盾する (\(n\) は素数である)
●原始根を求める
位数や原始根を求める場合、次の定理を使うと簡単です。
- 定理３
- a が n の原始根で n - 1 の素因数分解が \({p_1}^a \times {p_2}^b \times \cdots \times {p_m}^k\) と表されるとき、以下の式が成り立つ
\(
a^{\frac{n-1}{p_i}} \not\equiv 1 \pmod n, \quad (i = 1, 2, \cdots, m)
\)
- 証明
- n - 1 は \(p^i\) で割り切れるので、\(1 \leqq \frac{n - 1}{p_i} \lt n - 1\) が成立する
- a は n の原始根なので、\(a^k \equiv 1 \pmod n\) を満たす最小の \(k\) は \(n - 1\)
- \(\frac{n - 1}{p_i}\) は \(n - 1\) よりも小さいので、\(a^{\frac{n - 1}{p_i}} \equiv 1 \pmod n\) にはならない
- 証明
- a が n の原始根でなければ、位数 s は n - 1 未満で、n - 1 の約数になる (n - 1 は s の倍数)
- 位数 s は n - 1 と同様に \(p_1, \ p_2, \ \cdots, \ p_m\) で素因数分解できる
- ただし、指数は a, b, ..., k よりも小さいものが少なくとも一つある
\(
s = {p_1}^{a'} \times {p_2}^{b'} \times \cdots \times {p_m}^{k'}, \quad (a' \leqq a, \ b' \leqq b, \cdots, \ k' \leqq k)
\)
- それを \({p_i}^{e'}, \ (e' \lt e)\) とすると、次式が成り立つ
\(\begin{eqnarray}
\dfrac{n-1}{p_i} &=& \left(\dfrac{1}{p_i}\right) \times {p_1}^a \times {p_2}^b \times \cdots \times {p_i}^e \times \cdots \times {p_m}^k \\
&=& \left(\dfrac{1}{p_i}\right) \times {p_1}^{a-a'} \times {p_2}^{b-b'} \times \cdots \times {p_i}^{e-e'} \times \cdots \times {p_m}^{k-k'} \times s \\
&=& {p_i}^{e-e'-1} \times s
\end{eqnarray}\)
\(e - e' - 1 \geqq 0\) より \(\dfrac{n - 1}{p_i} = (num) * s\)
\(\begin{eqnarray}
a^{\frac{n-1}{p_i}} &=& a^{(num) \times s} \\
&=& (a^s)^{(num)}
\end{eqnarray}\)
- \(a^s \equiv 1 \pmod n\) より \(a^{\frac{n-1}{p_i}} \equiv 1 \pmod n\) が成り立つ
SymPy には位数を求める関数 n_order() や原始根を判定する is_primitive_root() が用意されています。簡単な使用例を示します。
>>> sy.n_order(2, 11)
10
>>> sy.n_order(3, 11)
5
>>> sy.n_order(2, 13)
12
>>> sy.n_order(3, 13)
3
>>> sy.n_order(4, 13)
6
>>> sy.n_order(5, 13)
4
>>> sy.n_order(6, 13)
12
>>> sy.n_order(7, 13)
12
>>> sy.is_primitive_root(2, 11)
True
>>> sy.is_primitive_root(3, 11)
False
>>> sy.is_primitive_root(2, 13)
True
>>> sy.is_primitive_root(3, 13)
False
>>> sy.is_primitive_root(4, 13)
False
>>> sy.is_primitive_root(5, 13)
False
>>> sy.is_primitive_root(6, 13)
True
>>> sy.is_primitive_root(7, 13)
True
SymPy の関数 primitive_root(p) は、存在するときに限り p の最小の原始根を一つ返します。簡単な使用例を示します。
>>> for x in [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]:
... print(x, sy.primitive_root(x))
...
3 2
5 2
7 3
11 2
13 2
17 3
19 2
23 5
29 2
31 3
37 2
41 6
43 3
47 5