初等整数論 [2]
●合同式
数学の世界では、2 つの整数 \(a, b\) を 2 以上の整数 \(n\) で割ったとき、その剰余が等しいことを「合同」といい、以下の式で表します。
\( a \equiv b \pmod n\)
これを「合同式」といい、"a 合同 b モッド n" または "n を法として a と b は合同" と読みます。
合同式の +, -, *, べき乗では、次の規則が成立します。
\(a \equiv b \pmod n, \ c \equiv d \pmod n\) のとき、\(a + c \equiv b + d\)
\(a \equiv b \pmod n, \ c \equiv d \pmod n\) のとき、\(a - c \equiv b - d\)
\(a \equiv b \pmod n, \ c \equiv d \pmod n\) のとき、\(a \times c \equiv b \times d\)
\(a \equiv b \pmod n\) のとき、\(a^k \equiv b^k\) (k は自然数)
ただし、合同式の除算には条件があります。
\(a \times b \equiv a \times c \pmod n\) で \(a\) と \(n\) が互いに素であるとき、\(b \equiv c \pmod n\) が成り立つ
「互いに素」とは、\(a, n\) の共通の約数が 1 しかないこと、つまり最大公約数 \(\gcd(a, n)\) の値が 1 であることと同じです。また、\(f(x\)) を整数係数多項式とすると、\(a \equiv b \pmod n\) のとき、\(f(a) \equiv f(b)\) が成立します。
Python の場合、剰余は演算子 % で求めることができます。簡単な例を示しましょう。
>>> 12345678 % 256
78
>>> 123456789 % 256
21
>>> 1234567890 % 256
210
>>> 12345678900 % 256
52
>>> a = 12345678
>>> b = a % 256
>>> b
78
>>> c = 123456789
>>> d = c % 256
>>> d
21
>>> (a + c) % 256
99
>>> (b + d) % 256
99
>>> (a - c) % 256
57
>>> (b - d) % 256
57
>>> (a * c) % 256
102
>>> (b * d) % 256
102
>>> (a ** 5) % 256
224
>>> (b ** 5) % 256
224
>>> 15240 % 256
136
>>> 34440 % 256
136
>>> 15240 % 3
0
>>> 34440 % 3
0
>>> (15240 // 3) % 256
216
>>> (34440 // 3) % 256
216
>>> 15240 % 4
0
>>> 34440 % 4
0
>>> (15240 // 4) % 256
226
>>> (34440 // 4) % 256
162
もう一つ、有名な定理を紹介します。
\(a\) と \(n\) が互いに素のとき、\(a, \ 2a, \ 3a, \ \cdots, \ (n - 2)a, \ (n - 1)a\) を \(n\) で割ったときの余りはすべて異なる
本当にそうなるか実際に試してみましょう。
>>> a = 10
>>> b = 7
>>> for n in range(1, b):
.... print(a * n % b)
....
3
6
2
5
1
4
証明は「背理法」を使うと簡単です。\(ia\) と \(ja\) (\(i \gt j\)) を \(n\) で割った余りが同じ値 \(x\) だと仮定しましょう。すると、次式が成立するはずです。
\(\begin{array}{llll}
& ia & \equiv & x \pmod n \\
- & ja & \equiv & x \pmod n \\
\hline
& (i-j)a & \equiv & 0 \pmod n
\end{array}\)
\((i-j)a\) を \(n\) で割った余りは \(0\) になるので、\((i-j)a\) は \(n\) の倍数でなければいけません。\(i, j\) の前提条件 \(1 \leq i \lt n, \ 1 \leq j \lt n\) より、\(1 \leq i - j \lt n\) になるので、\(i - j\) は \(n\) で割り切れることはありません。そして、\(a\) と \(n\) は互いに素なので、\(a\) も \(n\) で割り切れることはありません。つまり、\((i-j)a\) は \(n\) の倍数ではないので、最初の仮定「\(ia\) と \(ja\) (\(i \gt j\)) を \(n\) で割った余りが同じ値 \(x\) になる」が矛盾していて、余りはすべて異なる値になることが導かれました。
●フェルマーの小定理
\(n\) が素数で \(a\) と \(n\) が互いに素のとき、\(a^{n - 1}\) を \(n\) で割ると余りが必ず 1 になります。これを「フェルマーの小定理」といい、合同式で書くと次のようになります。
\(a^{n-1} \equiv 1 \pmod n\)
本当にそうなるのか、実際に試してみましょう。
>>>> 10 ** (3 - 1) % 3
1
>>>> 100 ** (3 - 1) % 3
1
>>>> 100 ** (7 - 1) % 7
1
>>>> 1000 ** (7 - 1) % 7
1
>>>> 1000 ** (11 - 1) % 11
1
>>>> 10000 ** (11 - 1) % 11
1
>>>> 10000 ** (97 - 1) % 97
1
確かに余りが 1 になりますね。
フェルマーの小定理の証明 (一例) を示します。
- [定理] \(a\) と \(n\) が互いに素のとき、\(a, 2a, \ldots, (n - 1)a\) を \(n\) で割った余りはすべて異なる
- \(a, 2a, \ldots, (n - 1)a\) を乗算する
\(a \times 2a \times \cdots \times (n - 1)a = (n - 1)! \times a^{n-1}\)
- 左辺式の剰余は各因子の剰余を乗算したものと同じになるので、1 の定理により \((n - 1)!\) になる
\((n - 1)! \equiv (n - 1)! \times a^{n-1} \pmod n\)
- \(n\) と \((n - 1)!\) は互いに素なので、両辺を \((n - 1)!\) で割り算すると、フェルマーの小定理になる
\(a^{n-1} \equiv 1 \pmod n\)
このほかにも、いろいろな証明方法があります。興味のある方は 参考 URL 2, 5 をお読みください。
●オイラーのトーシェント関数
数学の整数論では、整数 \(n\) に対して、\(n\) 以下の自然数で \(n\) と互いに素となる個数を求める関数を、「オイラーのトーシェント関数 (Euler's totient function)」といいます。慣例的に \(\varphi(n)\) と表記されることから、オイラーのファイ関数 (phi function) と呼ばれることもあります。
たとえば、1, 2, 3, 4 の中で 4 と互いに素となる数は 1 と 3 の 2 つあるので、totient(4) は 2 になります。totient(5) は、5 が素数なので、1, 2, 3, 4 と 5 は互いに素となるため、totient(5) は 4 になります。p を素数とすると、totient(p) = p - 1 になります。
幸いなことに、\(\varphi(n)\) を求める公式があるので、それを使うと高速に計算することができます。\(n\) の素因数分解が \({p_i}^a \times {p_j}^b \times \cdots \times {p_k}^c\) とすると、\(\varphi(n)\) は以下の式で求めることができます。
\(
\varphi(n) = n \times (1 - \dfrac{1}{p_i}) \times (1 - \dfrac{1}{p_j}) \times \cdots \times (1 - \dfrac{1}{p_k})
\)
- 証明の概要
- \(n = p^k\) と素因数分解できた場合、\(\varphi(n)\) は \(p\) の倍数を除いた数の個数になるので、以下の式が成り立つ
\(
\varphi(p^k) = p^k - \dfrac{p^k}{p} = p^k \times (1 - \dfrac{1}{p})
\)
- \(m, n\) が互いに素であるとき、\(\varphi(mn) = \varphi(m) \times \varphi(n)\) が成り立つ (トーシェント関数の乗法性)
- \(n = {p_i}^a \times {p_j}^b \times \cdots \times {p_k}^c\) と素因数分解できた場合、\(\varphi({p_i}^a \times {p_j}^b \times \cdots \times {p_k}^c)\) に乗法性を順次適用する
\(\begin{eqnarray}
\varphi(n) &=& \varphi({p_i}^a) \times \varphi({p_j}^b) \times \cdots \times \varphi({p_k}^c) \\
&=& {p_i}^a (1 - \dfrac{1}{p_i}) \times {p_j}^b (1 - \dfrac{1}{p_j}) \times \cdots \times {p_k}^c (1 - \dfrac{1}{p_k}) \\
&=& ({p_i}^a \times {p_j}^b \times \cdots \times {p_k}^c) \times (1 - \dfrac{1}{p_i}) \times (1 - \dfrac{1}{p_j}) \times \cdots \times (1 - \dfrac{1}{p_k}) \\
&=& n \times (1 - \dfrac{1}{p_i}) \times (1 - \dfrac{1}{p_j}) \times \cdots \times (1 - \dfrac{1}{p_k})
\end{eqnarray}\)
この他に以下の式が成り立ちます。
[ファイ関数の和]
\(\displaystyle \sum_{d|n}^{} \varphi(d) = n\)
[オイラーの定理]
\(a^{\varphi(n)} \equiv 1 \pmod n\)
ファイ関数の和は、\(n\) の約数を \(d\) とすると、\(\varphi(d)\) の合計値を求めることです。たとえば、8 の約数は 1, 2, 4, 8 の 4 通りありますが、\(\varphi(1) + \varphi(2) + \varphi(4) + \varphi(8)\) を計算すると、1 + 1 + 2 + 4 = 8 になります。
証明の概略を示します。ファイ関数の和を求める関数を \(F(n)\) とします。
\(n\) が素数の場合
\(
F(n) = \varphi(1) + \varphi(n) = 1 + n - 1 = n
\)
\(n = p^k\) (p は素数) の場合、約数は \(1, p, p^2, \ldots, p^k\) だから
\(
F(p^k) = \displaystyle \sum_{i=0}^k \varphi(p^k) = 1 + (p - 1) + (p^2 - p) + \cdots + (p^{k-1} - p^{k-2}) + (p^k - p^{k-1}) = p^k
\)
\(n = pq\) (\(p, q\) は素数) の場合、約数は \(1, p, q, pq\) だから
\(\begin{eqnarray}
F(pq) &=& \varphi(1) + \varphi(p) + \varphi(q) + \varphi(pq) \\
&=& \varphi(1) + \varphi(p) + \varphi(q) + \varphi(q)\varphi(q) \\
&=& 1 + (p - 1) + (q - 1) + (p - 1)(q - 1) \\
&=& pq \\
F(pq) &=& F(p)F(q) = pq
\end{eqnarray}\)
関数 \(F(n)\) の乗法性を認めることにして、
\(n = {p_i}^a \times {p_j}^b \times \cdots \times {p_k}^c\) と素因数分解できた場合
\(
\begin{eqnarray}
F(n) &=& F({p_i}^a \times {p_j}^b \times \cdots \times {p_k}^c) \\
&=& F({p_i}^a) \times F({p_j}^b) \times \cdots \times F({p_k}^c) \\
&=& {p_i}^a \times {p_j}^b \times \cdots \times {p_k}^c \\
&=& n
\end{eqnarray}
\)
オイラーの定理で n が素数の場合が「フェルマーの小定理」になります。
- 証明
- \(1\) 以上 \(n - 1\) 以下の整数で、\(n\) と互いに素の整数を \(S = \{x_1, x_2, \ldots, x_{\varphi(n)}\}\) とおく
- \(n\) と互いに素な整数 \(a\) を \(S\) の要素に乗算した集合 \(S' = \{ax_1, ax_2, \ldots, ax_{\varphi(n)}\}\) を考える
- \(S'\) の要素を \(n\) で割った余りの集合は \(S\) と一致する
- \(ax_i\) は \(n\) と互いに素になるので、\(ax_i \equiv x_j \pmod n, x_j \in S\) となる \(x_j\) が存在する
- \(S'\) の要素を \(n\) で割った余りはどの 2 つも異なる
- \(ax_i \equiv x \pmod n, ax_j \equiv x \pmod n, x_i \gt x_j\) と仮定する
- 合同式を引き算すると \(a(x_i - x_j) \equiv 0 \pmod n\) となる
- \(a(x_i - x_j)\) は \(n\) の倍数になる
- \(n\) と \(a\) は互いに素なので、\(a\) は \(n\) では割り切れない
- 前提条件 \(x_i \lt n, x_j \lt n, x_i \gt x_j\) より \(0 \lt x_i - x_j \lt n\) になる
- \(x_i - x_j\) は \(n\) で割り切ることはできない
- \(a(x_i - x_j)\) は \(n\) の倍数にはならないので矛盾する
- つまり、\(S'\) の要素を \(n\) で割った余りは \(S\) の要素がひとつずつ現れる
- \(S, S'\) の要素を掛け算すると次式が成り立つ
\(
a^{\varphi(n)} x_1 x_2 \cdots x_{\varphi(n)} \equiv x_1 x_2 \cdots x_{\varphi(n)} \pmod n
\)
\(x_i\) は \(n\) と互いに素なので、両辺を \(x_1 x_2 \cdots x_{\varphi(n)}\) で割ると
\(a^{\varphi(n)} \equiv 1 \pmod n\) を得る
詳しい説明は 参考 URL 3, 7 をお読みください。
●メビウス関数
メビウス関数 (Möbius function) は、正の整数 n を与えると -1, 0, 1 のいずれかの値を返します。
\(\mu(1) = 1\)
n が平方因子を持つとき \(\mu(n) = 0\)
それ以外の場合 \(\mu(n) = (-1)^k\) (k は異なる素因子の個数)
メビウス関数 \(\mu(n)\) は引数 n が 1 の場合は 1 を返します。1 より大きい場合、n を素因数分解した結果で値が決まります。同じ素数で 2 回割り切れる (平方因子を持つ) 場合は 0 を返します。それ以外の場合、n は異なる素数の積で表されるので、その個数 k が奇数ならば -1 を、偶数ならば 1 を返します。
たとえば、24 は \(2^3 \times 3\) と素因数分解できますが、2 で 2 回割り切れるので \(\mu(24)\) は 0 になります。つまり、素因数分解して 2 以上の指数がある場合は 0 を返します。\(\mu(30)\) は \(30 = 2 \times 3 \times 5\) なので、\((-1)^3 = -1\) を返します。n が素数の場合も -1 になります。\(\mu(35)\) は \(35 = 5 \times 7\) なので、\((-1)^2 = 1 \) を返します。
●メビウス関数の性質
\(n\) の約数を \(d\) とすると、\(n \ne 1\) のとき \(\mu(d)\) の合計値は 0 になります。
\(
\displaystyle \sum_{d|n}^{} \mu(d) = 0 \quad (n \neq 1)
\)
- 証明の概要
- \(n = {p_1}^a \times {p_2}^b \times \cdots \times {p_k}^z\) とする
- 指数 a, b, ..., z が 1 より大きい約数 d は \(\mu(d) = 0\) になるので、\(p_1, \ p_2, \ \cdots,\ p_k\) の組み合わせを考えればよい
\(
\displaystyle \sum_{d|n}^{} \mu(d) = (-1)^0 {}_k \mathrm{C}_0 + (-1)^1 {}_k \mathrm{C}_1 + (-1)^2 {}_k \mathrm{C}_2 + \cdots + (-1)^k {}_k \mathrm{C}_k
\)
- ここで二項定理を適用する
\(
(a + b)^n = \displaystyle \sum_{i=0}^{n} {}_n \mathrm{C}_i \times a^{n-i} \times b^i
\)
- a = 1, b = -1 と同じになるので \((1 - 1)^k = 0\)、よって \(\sum_{d|n} \mu(d) = 0\) になる
●メビウス関数の反転公式
自然数 n を引数に受け取り、数を返す関数 \(f(n), g(n)\) を考えます。
\(\begin{array}{ll}
1. & g(n) = \displaystyle \sum_{d|n} f(d) \\
2. & f(n) = \displaystyle \sum_{d|n} \mu(\frac{n}{d}) g(d) = \sum_{d|n} \mu(d) g(\frac{n}{d})
\end{array}\)
式 1 を満たす場合、式 2 が成り立ちます。これを「メビウスの反転公式」といいます。式 2 の場合、d は n の約数なので、n / d も n の約数です。d が決まれば n / d は一意に定まるので、式 2 の \(\mu(n/d) g(d)\) の和と \(\mu(d) g(n/d)\) の和は等しくなります。たとえば、n = 6 とすると、約数は 1, 2, 3, 6 の 4 通りあります。式 2 を計算すると、以下のように総和は等しくなることがわかります。
\(\begin{eqnarray}
\displaystyle \sum_{n|d} \mu(\frac{n}{d}) g(d) = \mu(6)g(1) + \mu(3)g(2) + \mu(2)g(3) + \mu(1)g(6) \\
\displaystyle \sum_{n|d} \mu(d) g(\frac{n}{d}) = \mu(1)g(6) + \mu(2)g(3) + \mu(3)g(2) + \mu(6)g(1)
\end{eqnarray}\)
- 証明の概要
- 式 2 の g(d) を式 1 に書き換えて変形する
\(
\displaystyle \sum_{d|n} \mu(\frac{n}{d}) \times \sum_{e|d} f(e) = \sum_{e|d,d|n} \mu(\frac{n}{d})f(e)
\)
- 最後の \(\Sigma\) は、d が n の約数で、e が d の約数であるすべてのペア (d, e) について取る
- d は e の倍数 (d = ke) かつ n の約数だから、n/d = n/(ke), k(n/d) = n/e となり、n/d は n/e の約数であることがわかる
- e を固定して考えて式を変形する
\(
f(e) \times \displaystyle \sum_{t|(n/e)} \mu(t)
\)
- \(\sum_{t|(n/e)} \mu(t)\) は t = 1 (n/e = 1, e = n) 以外は 0 になるので、f(e) だけが残る
詳しい説明は 参考 URL 4, 8 をお読みくださいませ。
簡単な例として、ファイ関数の和の式にメビウスの反転公式を適用してみましょう。
[ファイ関数の和]
\(
\displaystyle \sum_{d|n} \varphi(d) = n
\)
メビウスの反転公式を適用すると
\(
\varphi(n) = \displaystyle \sum_{d|n} \varphi(\frac{n}{d}) \times d
\)
実際に \(\varphi(n)\) を計算することができるのか、Python3 で試してみましょう。
>>> def phi(n):
... return sum(mobius(n // d) * d for d in divisors(n))
>>> phi(1000)
400
>>> totient(1000)
400
>>> phi(12345)
6576
>>> totient(12345)
6576
phi() と totient() は同じ値を返します。メビウスの反転公式は正しいことがわかります。
●参考 URL
- 合同式(mod)の意味とよく使う６つの性質, (マスオさん)
- フェルマーの小定理の証明と例題, (マスオさん)
- オイラーのファイ関数のイメージ, (マスオさん)
- メビウスの反転公式の証明と応用, (マスオさん)
- フェルマーの小定理 - Wikipedia
- 約数関数 - Wikipedia
- オイラーのφ関数 - Wikipedia
- メビウス関数 - Wikipedia