初等整数論/合成数を法とする合同式

初等整数論/フェルマーの小定理で、フェルマーの小定理を用いて、素数を法とする剰余類の構造を調べたので、次に、一般の自然数を法とする合同式について考えたい。まず、素数の冪を法とする場合について考え、次に一般の法について考える。

$p^{e}$ を法とする合同式について

$p^{e}$ を法とする剰余類は $0,1,\ldots ,p^{e}-1$ の $p^{e}$ 個ある。

$\gcd(a,p)=1$ ならば $\gcd(a,p^{e})=1$ である。よってこのとき任意の $b{\pmod {p^{e}}}$ に対し $ax\equiv b{\pmod {p^{e}}}$ となる $x{\pmod {p^{e}}}$ が一意的に定まる。このような剰余類 $a{\pmod {p^{e}}}$ は $bp+r,0\leq b\leq p^{e-1}-1,1\leq r\leq p-1$ の形に一意的に書けるから、ちょうど $p^{e-1}(p-1)$ 個存在する。

一方、 $a$ が $p$ の倍数の場合、 $ax\equiv b{\pmod {p^{e}}}$ となる $x{\pmod {p^{e}}}$ が存在するかも定かでない。例えば $2x\equiv 3{\pmod {4}},9x\equiv 3{\pmod {27}}$ などは解を持たない。 $a=sp^{f},b=tp^{g},\gcd(s,p)=\gcd(t,p)=1$ とおくと $ax\equiv b{\pmod {p^{e}}}\iff sp^{f}x\equiv tp^{g}{\pmod {p^{e}}}$ である。ここで、つぎの3つの場合に分かれる。

1. $g\geq e$ のとき $b\equiv 0{\pmod {p^{e}}}$ よりこの合同式はすべての剰余類を解に持つ。

2. $e,f>g$ のとき $sp^{f-g}x\equiv t{\pmod {p^{e-g}}}$ つまり $sp^{f-g}x-t\equiv 0{\pmod {p^{e}}}$ であるが $f>g,\gcd(t,p)=1$ より、この合同式は解を持たない。

3. $f\leq g<e$ のとき $sx\equiv tp^{g-f}{\pmod {p^{e-f}}}$ は $\gcd(s,p)=1$ よりただ1つの剰余類 $x=x_{0}{\pmod {p^{e-f}}}$ を解に持つ。しかし $ax\equiv b{\pmod {p^{e}}}$ は $p^{e}$ を法とする合同式である。よって、これはちょうど $p^{f}$ 個の剰余類 $x_{0}+kp^{e-f}{\pmod {p^{e}}}(k=0,1,\ldots ,p^{g}-1)$ を解に持つ。

次に、合同方程式 $f(x)\equiv 0{\pmod {p^{e}}}$ が解を持つのはどのような場合か考える。そもそも $f(x)\equiv 0{\pmod {p}}$ が解を持たなければならないことは言うまでもない。まず、正の整数 $k,m$ に対して

(x+p^{m})^{k}=x^{k}+kx^{k-1}p^{m}+{\binom {k}{2}}x^{k-2}p^{2m}+\cdots \equiv x^{k}+kx^{k-1}p^{m}{\pmod {p^{m+1}}}

より

f(x+p^{m})\equiv \sum _{k=0}^{n}a_{k}(x^{k}+kx^{k-1}p^{m})=f(x)+p^{m}f'(x){\pmod {p^{m+1}}}

が成り立つことから、次のことがわかる。

定理 2.4.1

$x=a$ を合同方程式 $f(x)\equiv 0{\pmod {p^{m}}}$ の解とする。このとき $f'(a)\not \equiv 0{\pmod {p}}$ ならば

f(a+bp^{m})\equiv 0{\pmod {p^{m+1}}}\cdots (*)

となる $a{\pmod {p}}$ がちょうど1つ定まる。 $f'(a)\equiv 0{\pmod {p}}$ ならばそのような $b{\pmod {p}}$ は存在しないか、すべての $b{\pmod {p}}$ に対して (*) が成り立つ。

数学的帰納法より、次の定理がすぐに導かれる。

定理 2.4.2

$x=a$ を合同方程式 $f(x)\equiv 0{\pmod {p}}$ の解とする。 $e\geq 2$ を整数とする。このとき $f'(a)\not \equiv 0{\pmod {p}}$ ならば

f(a+bp)\equiv 0{\pmod {p^{e}}}

となる $b{\pmod {p^{e-1}}}$ はちょうど1つ定まる。

例任意の素数 $p$ と正の整数 $e$ に対し、合同方程式 $x^{p-1}\equiv 1{\pmod {p^{e}}}$ の解の個数は $p-1$ 個である。より詳しく、各 $a=1,2,\ldots ,p-1$ に対し、 $x^{p-1}\equiv 1{\pmod {p^{e}}},x\equiv a{\pmod {p}}$ となる $x{\pmod {p^{e}}}$ が1個ずつある。

中国の剰余定理

一般の合成数を法とする場合は素数冪を法とする場合に帰着される。具体的に、次のような問題を考えてみる。

問 7 で割って 6 余り、13 で割って 12 余り、19 で割って 18 余る数はいくつか?

答えは、7×13×19 - 1 である。さて、このような問題に関して、次の定理がある。

定理 (w:中国の剰余定理)

$m_{1},m_{2},\cdots ,m_{k}$ のどの2つをとっても互いに素であるとき、任意の整数 $a_{1},a_{2},\cdots ,a_{k}$ について、

{\begin{cases}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\\cdots \\x\equiv a_{k}{\pmod {m_{k}}}\end{cases}}

を満たす $x$ は $m_{1}m_{2}m_{3}\cdots m_{k}$ を法としてただひとつ存在する。（ここでの「ただひとつ」というのは、互いに合同なものは同じとみなすという意味である。）

証明 1

まず、 $k=2$ のときを証明する。

${\begin{cases}x\equiv a_{1}{\pmod {m_{1}}}\ \cdots (1)\\x\equiv a_{2}{\pmod {m_{2}}}\ \cdots (2)\\\end{cases}}$

$(m_{1},m_{2})=1$ より、一次不定方程式に関する定理 1.9 より $m_{1}u+m_{2}v=1$ と表せる。このとき、

${\begin{cases}m_{2}v\equiv 1{\pmod {m_{1}}}\ \cdots (3)\\m_{1}u\equiv 1{\pmod {m_{2}}}\ \cdots (4)\\\end{cases}}$

となる。

$x\equiv a_{1}m_{2}v+a_{2}m_{1}u{\pmod {m_{1}m_{2}}}$ とおくと、

$x-a_{1}=a_{1}(m_{2}v-1)+a_{2}m_{1}u$ となる。(4) より、 $m_{2}v-1=m_{1}M$ とおけば、

$x-a_{1}=a_{1}m_{1}M+a_{2}m_{1}v$ は $m_{1}$ で割り切れる。したがって、合同の定義より方程式の (1) を満たす。また、同様に (3) を用いることで、(2) をも満たすことは容易に証明される。

よって、解が存在することが証明された。

さて、その唯一性であるが、 $y$ を任意の解とすれば、 $x,y\equiv a_{1}\Rightarrow x\equiv y\Rightarrow x-y\equiv 0{\pmod {m_{1}}}$ となる。また同様にして $x-y\equiv 0{\pmod {m_{2}}}$ となる。したがって合同の定義より、 $x-y$ は $m_{1},m_{2}$ の公倍数。 $(m_{1},m_{2})=1$ より、 $x-y$ は $m_{1}m_{2}$ の倍数である。したがって $x-y\equiv 0\Rightarrow x\equiv y{\pmod {m_{1}m_{2}}}$

となり、唯一性が保証された。

次に、定理を k に関する数学的帰納法で証明する。

(i) k = 1 のとき $x\equiv a_{1}{\pmod {m_{1}}}$ は $x=a_{1}$ が唯一の解である（除法の原理より唯一性は保証される）。

(ii) k = n のとき成り立つと仮定する

${\begin{cases}x\equiv a_{1}{\pmod {m_{1}}}\\x\equiv a_{2}{\pmod {m_{2}}}\\\cdots \\x\equiv a_{n}{\pmod {m_{n}}}\\x\equiv a_{n+1}{\pmod {m_{n+1}}}\end{cases}}$

最初の n の式は、帰納法の仮定によって $x\equiv b{\pmod {m_{1}m_{2}\cdots m_{n}}}$ なる $b$ がただひとつ存在する。

ゆえに、

${\begin{cases}x\equiv b{\pmod {m_{1}m_{2}\cdots m_{n}}}\\x\equiv a_{n+1}{\pmod {m_{n+1}}}\end{cases}}$

を解けば良い。仮定より、 $(m_{1}m_{2}\cdots m_{n},m_{n+1})=1$ であるから、k = 2 の場合に当てはめて、この方程式を満たす $x$ が、 $m_{1}m_{2}\cdots m_{n}m_{n+1}$ を法としてただひとつ存在する。

したがって、k = n のとき成り立つならば k = n+1 のときも成り立つことが証明された。

(i)(ii) より数学的帰納法から定理が証明される。

証明 2 この証明はガウスによる。

$M=m_{1}m_{2}\cdots m_{n}$ とおき、

$M=m_{1}M_{1}=m_{2}M_{2}=\cdots =m_{n}M_{n}$

とおく。仮定より、 $(M_{k},m_{k})=1\ \ (k=1,2,\cdots ,n)$ なので定理 1.8 から

$M_{k}t_{k}\equiv 1{\pmod {m_{k}}}$ なる $t_{k}$ が存在する。

すると、連立合同方程式の解は、 $x\equiv a_{1}M_{1}t_{1}+a_{2}M_{2}t_{2}+\cdots +a_{n}M_{n}t_{n}{\pmod {M}}$ となる。なぜなら任意の $1\leqq k\leqq n$ について、

$M_{k}t_{k}\equiv 1\Rightarrow a_{k}M_{k}t_{k}\equiv a_{k}{\pmod {m_{k}}}$ となり、他の全ての項は $M_{1},M_{2},\cdots ,M_{k-1},M_{k+1},\cdots ,M_{n}$ の積なので $m_{k}$ で割り切れる。

したがって、 $x\equiv a_{k}{\pmod {x_{k}}}$ となる。よって $x$ が解である。

もちろん、各剰余類 $x{\pmod {m_{1}m_{2}\cdots m_{k}}}$ に対し、 $x\equiv x_{i}{\pmod {m_{i}}}$ となる剰余類 $x_{i}{\pmod {m_{i}}}$ はただ一つ存在する。このことから $x{\pmod {m_{1}m_{2}\cdots m_{k}}}$ と $(x_{1}{\pmod {m_{1}}},x_{2}{\pmod {m_{2}}},\ldots ,x_{k}{\pmod {m_{k}}})$ は 1対1 に対応していることがわかる。特に $a\equiv 1{\pmod {m_{1}m_{2}\cdots m_{k}}}$ は各 $i$ に対して $a\equiv 1{\pmod {m_{i}}}$ となることと同値である。

さて、 1より大きい整数 $n$ を $n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$ と素因数分解すると、 $p_{i}^{e_{i}}$ はどの2つをとっても互いに素である。ここで、次のことがわかる。

定理 2.4.3

$n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}$ と素因数分解すると、任意の整数 $a_{1},a_{2},\cdots ,a_{k}$ について、

{\begin{cases}a\equiv a_{1}{\pmod {p_{1}^{e_{1}}}}\\a\equiv a_{2}{\pmod {p_{2}^{e_{2}}}}\\\cdots \\a\equiv a_{k}{\pmod {p_{k}^{e_{k}}}}\end{cases}}

を満たす $a$ は $n$ を法としてただひとつ存在する。さらに、ここで $\gcd(a,n)=1\iff \gcd(a_{i},p_{i}^{e_{i}})=1(i=1,2,\ldots ,k)$ が成り立つ。

証明
前段は中国の剰余定理を $m_{i}=p_{i}^{e_{i}}$ に適用したものである。 $\gcd(a_{i},p_{i}^{e_{i}})>1$ ならば $p_{i}$ は $a_{i}$ の素因数であり、そうなると $p_{i}$ は $a$ の素因数になってしまい、 $p|\gcd(a,n)$ となってしまう。