初等整数論/合同の応用

一次合同方程式 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} が無数に存在するかどうかは未だ解決されていない。