初等整数論/合同の応用

一次合同方程式の定理

一次合同方程式 $ax\equiv b{\pmod {m}}$ が解を持つ必要十分条件は、$b$ が $g=(a,m)$ で割り切れるときに限り、解の個数は $g$ である。

証明
(i) $(a,m)=1$ のとき

$ax\equiv b{\pmod {m}}$ より、 $ax+my=b$ とおける。定理 1.9 より、解が存在する。解のうちの一つを $(x,y)=(x_{0},y_{0})$ とおけば、全ての解は $(x_{0}-mk,y_{0}+ak)$ とおける。そのとき、解の全て（$x$のこと）は $m$ を法として同じ類に属す。すなわち解は $1=(a,m)$ 個である。

(ii) $(a,m)=g$ のとき

$ax-b=my$ とおくと、$b=ax-my$ より $b$ は $g=(a,m)$ で割り切れる。

そこで $a=ga',b=gb',m=gm'$ とおく。

$ax-b\,|\,m\iff a'x-b'\,|\,m'\iff a'x\equiv b'{\pmod {m'}}\cdots (1)$ となる。

もちろん $(a',m')=1$ より、(1) を満たす $x$ は $m'$ を法とする類である。その一つを $x_{0}$ とおくと、(1) の解は $x=x_{0}+m't$ と書ける。$t$ に2つの値 $t_{1},t_{2}$ を与えたとき $m't_{1}\equiv m't_{2}{\pmod {m}}$ となるには、$m'(t_{1}-t_{2})$ が $m$ で割り切れる、すなわち $t_{1}-t_{2}$ が $g$ で割り切れるときに限る。

つまり $t_{1}\equiv t_{2}{\pmod {g}}$ であり、$t$ に $0,1,\cdots ,g-1$ の $g$ 個の値を与えるときに合同式の全ての解を得られる。つまり、解の個数は $g$ 個である。

有理数の小数展開

有理数を小数展開すると最終的に循環する小数となることはよく知られている。ここでは、その小数展開について考察したい。実はその小数展開にフェルマーの小定理と原始根が関わっているのである。 まず、整数部分を消去することで ${\frac {n}{d}}(0<n<d,\gcd(d,n)=1)$ の形の分数（真分数）についてのみ考えればよくなる。

まず $d>1$ が2と5のみを素因数に持つ場合、 $d=2^{e}5^{f}$ とおくと

${\frac {n}{d}}={\frac {n}{2^{e}5^{f}}}={\frac {2^{f}5^{e}n}{10^{e+f}}}={\begin{cases}{\frac {2^{f-e}n}{10^{f}}},&f\geq e\\{\frac {5^{e-f}n}{10^{e}}},&e\geq f\end{cases}}$

となり、有限小数であることがわかる。

次に $d>1$ が10と互いに素な場合を考える。ここで $10{\pmod {n}}$ の位数を $l$ とし、 $10^{l}-1=dM$ とおくと

${\frac {n}{d}}={\frac {nM}{10^{e}-1}}=nM\sum _{k=1}^{\infty }{\frac {1}{10^{kl}}}=nM\times 0.\underbrace {{\dot {0}}0\ldots 0} _{l-1{\text{ zeros}}}{\dot {1}}$

$nM<dM=10^{l}-1$ なので $nM=a_{l-1}\cdot 10^{l-1}+a_{l-2}\cdot 10^{l-2}+\cdots +a_{1}\cdot 10+a_{0}(0\leq a_{0},a_{1},\ldots ,a_{l-1}\leq 9$ と10進展開すると

${\frac {n}{d}}=0.{\dot {a}}_{l-1}a_{l-2}\ldots {\dot {a}}_{0}$

となり、純循環小数であらわされる。

さて、一般の場合、任意の正の整数 $d$ は $d=2^{e}5^{f}m,\gcd(m,10)=1$ とあらわされる。

${\frac {n}{d}}={\frac {n}{2^{e}5^{f}m}}={\begin{cases}{\frac {2^{f-e}n}{10^{e}m}},&f\geq e\\{\frac {5^{e-f}n}{10^{f}m}},&e\geq f\end{cases}}$

となる。ここでそれぞれの場合に $2^{f-e}n=qm+r(0<r<m)$ あるいは $5^{e-f}n=qm+r(0<r<m)$ とおくと

${\frac {2^{f-e}n}{10^{f}m}}={\frac {qm+r}{10^{f}m}}={\frac {q}{10^{f}}}+{\frac {r}{10^{f}m}}$

あるいは

${\frac {5^{e-f}n}{10^{e}m}}={\frac {qm+r}{10^{e}m}}={\frac {q}{10^{e}}}+{\frac {r}{10^{e}m}}$

となる。ここで $q=b_{f-1}\cdot 10^{f-1}+b_{f-2}\cdot 10^{f-2}+\cdots +b_{1}\cdot 10+b_{0}(0\leq b_{0},b_{1},\ldots ,b_{e-1}\leq 9)$ あるいは $q=b_{e-1}\cdot 10^{e-1}+b_{e-2}\cdot 10^{e-2}+\cdots +b_{1}\cdot 10+b_{0}(0\leq b_{0},b_{1},\ldots ,b_{e-1}\leq 9)$ と10進展開すると、

${\frac {q}{10^{f}}}=0.b_{f-1}b_{f-2}\ldots b_{0}$

あるいは

${\frac {q}{10^{e}}}=0.b_{e-1}b_{e-2}\ldots b_{0}$

となる。さらに、先の場合と同様に $10{\pmod {m}}$ の位数を $l$ とし、$10^{l}-1=mM$ とおくと $rM<mM=10^{l}-1$ なので $rM=a_{l-1}\cdot 10^{l-1}+a_{l-2}\cdot 10^{l-2}+\cdot +a_{1}\cdot 10+a_{0}(0\leq a_{0},a_{1},\ldots ,a_{l-1}\leq 9)$ と10進展開すると

${\frac {r}{m}}=0.{\dot {a}}_{l-1}a_{l-2}\ldots {\dot {a}}_{0}$

より

${\frac {r}{10^{f}m}}=0.\underbrace {00\ldots 0} _{f{\text{ zeros}}}{\dot {a}}_{l-1}a_{l-2}\ldots {\dot {a}}_{0}$

あるいは

${\frac {r}{10^{e}m}}=0.\underbrace {00\ldots 0} _{e{\text{ zeros}}}{\dot {a}}_{l-1}a_{l-2}\ldots {\dot {a}}_{0}$

となる。

以上より、10進展開は次のようになる。

定理

$d=2^{e}5^{f}m,\gcd(m,10)=1$ と分解し、 $f\geq e$ のとき $2^{f-e}n=qm+r(0<r<m)$ となるように $q,r$ を定め $q=b_{f-1}\cdot 10^{f-1}+a_{f-2}\cdot 10^{f-2}+\cdots +b_{1}\cdot 10+b_{0}(0\leq b_{0},b_{1},\ldots ,b_{e-1}\leq 9)$ と10進展開する。 $e\geq f$ のとき $5^{e-f}n=qm+r(0<r<m)$ となるように $q,r$ を定め $q=b_{e-1}\cdot 10^{e-1}+b_{e-2}\cdot 10^{e-2}+\cdots +b_{1}\cdot 10+b_{0}(0\leq b_{0},b_{1},\ldots ,b_{e-1}\leq 9)$ と10進展開する。 $e=f$ のときは $q=0,r=1$ とする。

さらに $10{\pmod {m}}$ の位数を $l$ とし、$10^{l}-1=mM$ に対して $rM=a_{l-1}\cdot 10^{l-1}+a_{l-2}\cdot 10^{l-2}+\cdots +a_{1}\cdot 10+a_{0}(0\leq a_{0},a_{1},\ldots ,a_{l-1}\leq 9)$ と10進展開する。 このとき ${\frac {n}{d}}$ の小数展開は

${\frac {n}{d}}={\begin{cases}0.b_{f-1}b_{f-2}\ldots b_{0}{\dot {a}}_{l-1}a_{l-2}\ldots {\dot {a}}_{0},&f\geq e\\0.b_{e-1}b_{e-2}\ldots b_{0}{\dot {a}}_{l-1}a_{l-2}\ldots {\dot {a}}_{0},&e\geq f\end{cases}}$

により与えられる。

さらに、次のことがわかる。

定理
$d=2^{e}5^{f}m,\gcd(m,10)=1$ と分解する。 $\gcd(d,n)=1$ ならば ${\frac {n}{d}}$ の小数展開の周期は $10{\pmod {m}}$ の位数 $l$ と一致する。

証明
上の小数展開において

$0.{\dot {a}}_{l-1}a_{l-2}\ldots {\dot {a}}_{0}=0.{\dot {c}}_{k-1}c_{k-2}\ldots {\dot {c}}_{0}$

ならば

${\frac {c}{10^{k}-1}}={\frac {a}{10^{l}-1}}={\frac {r}{m}}$

であるが、$r=2^{f-e}n-qm$ または $r=5^{e-f}n-qm$ であるから、$\gcd(n,m)=\gcd(10,m)=1$ より $\gcd(r,m)=1$ である。よって $10^{k}\equiv 1{\pmod {m}}$ より $k\geq l$ でなければならない。

同様にして、基数が10以外のときでも次の定理が成り立つ。

定理
$d=bm,\gcd(m,a)=1$ と分解する。 $\gcd(d,n)=1$ ならば ${\frac {n}{d}}$ の $a$ 進小数展開の周期は $a{\pmod {m}}$ の位数と一致する。

このことから $a$ 進小数展開の周期は高々 $m-1$ であることがわかる。さらに等号は $d$ が素数で $a{\pmod {d}}$ が原始根であるとき、そしてそのときに限り成り立つ。つまり小数展開の周期が可能な限り大きい場合は、 $a{\pmod {p}}$ が原始根である場合と一致するといえる。先に述べたように、そのような素数 $p$ が無数に存在するかどうかは未だ解決されていない。