初等整数論/合同の応用
一次合同方程式の定理

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

証明 (i) ( a , m ) = 1 {\displaystyle (a,m)=1} のとき
一次合同方程式の定理

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

(ii) ( a , m ) = g {\displaystyle (a,m)=g} のとき
一次合同方程式の定理

a x − b = m y {\displaystyle ax-b=my} とおくと、 b = a x − m y {\displaystyle b=ax-my} より b {\displaystyle b} は g = ( a , m ) {\displaystyle g=(a,m)} で割り切れる。
一次合同方程式の定理

そこで a = g a ′ , b = g b ′ , m = g m ′ {\displaystyle a=ga',b=gb',m=gm'} とおく。
一次合同方程式の定理

a x − b | m ⟺ a ′ x − b ′ | m ′ ⟺ a ′ x ≡ b ′ ( mod m ′ ) ⋯ ( 1 ) {\displaystyle ax-b\,|\,m\iff a'x-b'\,|\,m'\iff a'x\equiv b'{\pmod {m'}}\cdots (1)} となる。
一次合同方程式の定理

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

つまり t 1 ≡ t 2 ( mod g ) {\displaystyle t_{1}\equiv t_{2}{\pmod {g}}} であり、 t {\displaystyle t} に 0 , 1 , ⋯ , g − 1 {\displaystyle 0,1,\cdots ,g-1} の g {\displaystyle g} 個の値を与えるときに合同式の全ての解を得られる。つまり、解の個数は g {\displaystyle g} 個である。
有理数の小数展開

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

まず d > 1 {\displaystyle d>1} が2と5のみを素因数に持つ場合、 d = 2 e 5 f {\displaystyle d=2^{e}5^{f}} とおくと
有理数の小数展開

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

次に d > 1 {\displaystyle d>1} が10と互いに素な場合を考える。ここで 10 ( mod n ) {\displaystyle 10{\pmod {n}}} の位数を l {\displaystyle l} とし、 10 l − 1 = d M {\displaystyle 10^{l}-1=dM} とおくと
有理数の小数展開

n M < d M = 10 l − 1 {\displaystyle nM<dM=10^{l}-1} なので n M = a l − 1 ⋅ 10 l − 1 + a l − 2 ⋅ 10 l − 2 + ⋯ + a 1 ⋅ 10 + a 0 ( 0 ≤ a 0 , a 1 , ... , a l − 1 ≤ 9 {\displaystyle 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進展開すると
有理数の小数展開

となり、純循環小数であらわされる。
有理数の小数展開

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

となる。ここでそれぞれの場合に 2 f − e n = q m + r ( 0 < r < m ) {\displaystyle 2^{f-e}n=qm+r(0<r<m)} あるいは 5 e − f n = q m + r ( 0 < r < m ) {\displaystyle 5^{e-f}n=qm+r(0<r<m)} とおくと
有理数の小数展開

あるいは
有理数の小数展開

となる。ここで q = b f − 1 ⋅ 10 f − 1 + b f − 2 ⋅ 10 f − 2 + ⋯ + b 1 ⋅ 10 + b 0 ( 0 ≤ b 0 , b 1 , ... , b e − 1 ≤ 9 ) {\displaystyle 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 ⋅ 10 e − 1 + b e − 2 ⋅ 10 e − 2 + ⋯ + b 1 ⋅ 10 + b 0 ( 0 ≤ b 0 , b 1 , ... , b e − 1 ≤ 9 ) {\displaystyle 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進展開すると、
有理数の小数展開

あるいは
有理数の小数展開

となる。さらに、先の場合と同様に 10 ( mod m ) {\displaystyle 10{\pmod {m}}} の位数を l {\displaystyle l} とし、 10 l − 1 = m M {\displaystyle 10^{l}-1=mM} とおくと r M < m M = 10 l − 1 {\displaystyle rM<mM=10^{l}-1} なので r M = a l − 1 ⋅ 10 l − 1 + a l − 2 ⋅ 10 l − 2 + ⋅ + a 1 ⋅ 10 + a 0 ( 0 ≤ a 0 , a 1 , ... , a l − 1 ≤ 9 ) {\displaystyle 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進展開すると
有理数の小数展開

より
有理数の小数展開

あるいは
有理数の小数展開

となる。
有理数の小数展開

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

定理
有理数の小数展開

d = 2 e 5 f m , gcd ( m , 10 ) = 1 {\displaystyle d=2^{e}5^{f}m,\gcd(m,10)=1} と分解し、 f ≥ e {\displaystyle f\geq e} のとき 2 f − e n = q m + r ( 0 < r < m ) {\displaystyle 2^{f-e}n=qm+r(0<r<m)} となるように q , r {\displaystyle q,r} を定め q = b f − 1 ⋅ 10 f − 1 + a f − 2 ⋅ 10 f − 2 + ⋯ + b 1 ⋅ 10 + b 0 ( 0 ≤ b 0 , b 1 , ... , b e − 1 ≤ 9 ) {\displaystyle 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 ≥ f {\displaystyle e\geq f} のとき 5 e − f n = q m + r ( 0 < r < m ) {\displaystyle 5^{e-f}n=qm+r(0<r<m)} となるように q , r {\displaystyle q,r} を定め q = b e − 1 ⋅ 10 e − 1 + b e − 2 ⋅ 10 e − 2 + ⋯ + b 1 ⋅ 10 + b 0 ( 0 ≤ b 0 , b 1 , ... , b e − 1 ≤ 9 ) {\displaystyle 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 {\displaystyle e=f} のときは q = 0 , r = 1 {\displaystyle q=0,r=1} とする。
有理数の小数展開

さらに 10 ( mod m ) {\displaystyle 10{\pmod {m}}} の位数を l {\displaystyle l} とし、 10 l − 1 = m M {\displaystyle 10^{l}-1=mM} に対して r M = a l − 1 ⋅ 10 l − 1 + a l − 2 ⋅ 10 l − 2 + ⋯ + a 1 ⋅ 10 + a 0 ( 0 ≤ a 0 , a 1 , ... , a l − 1 ≤ 9 ) {\displaystyle 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進展開する。 このとき n d {\displaystyle {\frac {n}{d}}} の小数展開は
有理数の小数展開

により与えられる。
有理数の小数展開

さらに、次のことがわかる。
有理数の小数展開

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

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

ならば
有理数の小数展開

であるが、 r = 2 f − e n − q m {\displaystyle r=2^{f-e}n-qm} または r = 5 e − f n − q m {\displaystyle r=5^{e-f}n-qm} であるから、 gcd ( n , m ) = gcd ( 10 , m ) = 1 {\displaystyle \gcd(n,m)=\gcd(10,m)=1} より gcd ( r , m ) = 1 {\displaystyle \gcd(r,m)=1} である。よって 10 k ≡ 1 ( mod m ) {\displaystyle 10^{k}\equiv 1{\pmod {m}}} より k ≥ l {\displaystyle k\geq l} でなければならない。
有理数の小数展開

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

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

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