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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

より
p

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

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

e




{\displaystyle p^{e}}

 を法とする合同式について

となる b ( mod p e − 1 ) {\displaystyle b{\pmod {p^{e-1}}}} はちょうど1つ定まる。
p

e




{\displaystyle p^{e}}

 を法とする合同式について

例 任意の素数 p {\displaystyle p} と正の整数 e {\displaystyle e} に対し、合同方程式 x p − 1 ≡ 1 ( mod p e ) {\displaystyle x^{p-1}\equiv 1{\pmod {p^{e}}}} の解の個数は p − 1 {\displaystyle p-1} 個である。より詳しく、各 a = 1 , 2 , ... , p − 1 {\displaystyle a=1,2,\ldots ,p-1} に対し、 x p − 1 ≡ 1 ( mod p e ) , x ≡ a ( mod p ) {\displaystyle x^{p-1}\equiv 1{\pmod {p^{e}}},x\equiv a{\pmod {p}}} となる x ( mod p e ) {\displaystyle x{\pmod {p^{e}}}} が1個ずつある。
中国の剰余定理

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

問 7 で割って 6 余り、13 で割って 12 余り、19 で割って 18 余る数はいくつか?
中国の剰余定理

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

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

m 1 , m 2 , ⋯ , m k {\displaystyle m_{1},m_{2},\cdots ,m_{k}} のどの2つをとっても互いに素であるとき、任意の整数 a 1 , a 2 , ⋯ , a k {\displaystyle a_{1},a_{2},\cdots ,a_{k}} について、
中国の剰余定理

を満たす x {\displaystyle x} は m 1 m 2 m 3 ⋯ m k {\displaystyle m_{1}m_{2}m_{3}\cdots m_{k}} を法としてただひとつ存在する。(ここでの「ただひとつ」というのは、互いに合同なものは同じとみなすという意味である。)
中国の剰余定理

証明 1
中国の剰余定理

まず、 k = 2 {\displaystyle k=2} のときを証明する。
中国の剰余定理

{ x ≡ a 1 ( mod m 1 ) ⋯ ( 1 ) x ≡ a 2 ( mod m 2 ) ⋯ ( 2 ) {\displaystyle {\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 {\displaystyle (m_{1},m_{2})=1} より、一次不定方程式に関する定理 1.9 より m 1 u + m 2 v = 1 {\displaystyle m_{1}u+m_{2}v=1} と表せる。このとき、
中国の剰余定理

{ m 2 v ≡ 1 ( mod m 1 ) ⋯ ( 3 ) m 1 u ≡ 1 ( mod m 2 ) ⋯ ( 4 ) {\displaystyle {\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 ≡ a 1 m 2 v + a 2 m 1 u ( mod m 1 m 2 ) {\displaystyle 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 {\displaystyle x-a_{1}=a_{1}(m_{2}v-1)+a_{2}m_{1}u} となる。(4) より、 m 2 v − 1 = m 1 M {\displaystyle m_{2}v-1=m_{1}M} とおけば、
中国の剰余定理

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

よって、解が存在することが証明された。
中国の剰余定理

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

となり、唯一性が保証された。
中国の剰余定理

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

(i) k = 1 のとき x ≡ a 1 ( mod m 1 ) {\displaystyle x\equiv a_{1}{\pmod {m_{1}}}} は x = a 1 {\displaystyle x=a_{1}} が唯一の解である(除法の原理より唯一性は保証される)。
中国の剰余定理

(ii) k = n のとき成り立つと仮定する
中国の剰余定理

{ x ≡ a 1 ( mod m 1 ) x ≡ a 2 ( mod m 2 ) ⋯ x ≡ a n ( mod m n ) x ≡ a n + 1 ( mod m n + 1 ) {\displaystyle {\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 ≡ b ( mod m 1 m 2 ⋯ m n ) {\displaystyle x\equiv b{\pmod {m_{1}m_{2}\cdots m_{n}}}} なる b {\displaystyle b} がただひとつ存在する。
中国の剰余定理

ゆえに、
中国の剰余定理

{ x ≡ b ( mod m 1 m 2 ⋯ m n ) x ≡ a n + 1 ( mod m n + 1 ) {\displaystyle {\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 ⋯ m n , m n + 1 ) = 1 {\displaystyle (m_{1}m_{2}\cdots m_{n},m_{n+1})=1} であるから、k = 2 の場合に当てはめて、この方程式を満たす x {\displaystyle x} が、 m 1 m 2 ⋯ m n m n + 1 {\displaystyle m_{1}m_{2}\cdots m_{n}m_{n+1}} を法としてただひとつ存在する。
中国の剰余定理

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

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

証明 2 この証明はガウスによる。
中国の剰余定理

M = m 1 m 2 ⋯ m n {\displaystyle M=m_{1}m_{2}\cdots m_{n}} とおき、
中国の剰余定理

M = m 1 M 1 = m 2 M 2 = ⋯ = m n M n {\displaystyle M=m_{1}M_{1}=m_{2}M_{2}=\cdots =m_{n}M_{n}}
中国の剰余定理

とおく。仮定より、 ( M k , m k ) = 1 ( k = 1 , 2 , ⋯ , n ) {\displaystyle (M_{k},m_{k})=1\ \ (k=1,2,\cdots ,n)} なので定理 1.8 から
中国の剰余定理

M k t k ≡ 1 ( mod m k ) {\displaystyle M_{k}t_{k}\equiv 1{\pmod {m_{k}}}} なる t k {\displaystyle t_{k}} が存在する。
中国の剰余定理

すると、連立合同方程式の解は、 x ≡ a 1 M 1 t 1 + a 2 M 2 t 2 + ⋯ + a n M n t n ( mod M ) {\displaystyle x\equiv a_{1}M_{1}t_{1}+a_{2}M_{2}t_{2}+\cdots +a_{n}M_{n}t_{n}{\pmod {M}}} となる。なぜなら任意の 1 ≦ k ≦ n {\displaystyle 1\leqq k\leqq n} について、
中国の剰余定理

M k t k ≡ 1 ⇒ a k M k t k ≡ a k ( mod m k ) {\displaystyle M_{k}t_{k}\equiv 1\Rightarrow a_{k}M_{k}t_{k}\equiv a_{k}{\pmod {m_{k}}}} となり、他の全ての項は M 1 , M 2 , ⋯ , M k − 1 , M k + 1 , ⋯ , M n {\displaystyle M_{1},M_{2},\cdots ,M_{k-1},M_{k+1},\cdots ,M_{n}} の積なので m k {\displaystyle m_{k}} で割り切れる。
中国の剰余定理

したがって、 x ≡ a k ( mod x k ) {\displaystyle x\equiv a_{k}{\pmod {x_{k}}}} となる。よって x {\displaystyle x} が解である。
中国の剰余定理

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

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

n = p 1 e 1 p 2 e 2 ⋯ p k e k {\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}} と素因数分解すると、任意の整数 a 1 , a 2 , ⋯ , a k {\displaystyle a_{1},a_{2},\cdots ,a_{k}} について、
中国の剰余定理

を満たす a {\displaystyle a} は n {\displaystyle n} を法としてただひとつ存在する。 さらに、ここで gcd ( a , n ) = 1 ⟺ gcd ( a i , p i e i ) = 1 ( i = 1 , 2 , ... , k ) {\displaystyle \gcd(a,n)=1\iff \gcd(a_{i},p_{i}^{e_{i}})=1(i=1,2,\ldots ,k)} が成り立つ。
中国の剰余定理

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

逆に a , n {\displaystyle a,n} を共に割り切る素数があるとするとそれは p i {\displaystyle p_{i}} のいずれかである。そのようなものを1つ取ると a i ≡ a ≡ 0 ( mod p i ) {\displaystyle a_{i}\equiv a\equiv 0{\pmod {p_{i}}}} より gcd ( a i , p i e i ) > 1 {\displaystyle \gcd(a_{i},p_{i}^{e_{i}})>1} となる。
中国の剰余定理

この定理から、次のことがすぐにわかる。
中国の剰余定理

n = p 1 e 1 p 2 e 2 ⋯ p k e k {\displaystyle n=p_{1}^{e_{1}}p_{2}^{e_{2}}\cdots p_{k}^{e_{k}}} と素因数分解する。 n {\displaystyle n} を法とする既約剰余類の個数は ∏ i = 1 k p i e i − 1 ( p i − 1 ) {\displaystyle \prod _{i=1}^{k}p_{i}^{e_{i}-1}(p_{i}-1)} である。
中国の剰余定理

ここで現れた
中国の剰余定理

を n {\displaystyle n} の オイラー関数 (Euler's totient) という。これは円分多項式の次数として現れたものである。
フェルマー・オイラーの定理

中国の剰余定理から、フェルマーの小定理は次のように一般化される。
フェルマー・オイラーの定理

a {\displaystyle a} を n {\displaystyle n} と互いに素な整数とすると
フェルマー・オイラーの定理

が成り立つ。
フェルマー・オイラーの定理

証明 n {\displaystyle n} と互いに素な数で 1 から n − 1 {\displaystyle n-1} までのもの b 1 , ... , b k {\displaystyle b_{1},\ldots ,b_{k}} をとる。 中国の剰余定理から k = φ ( n ) {\displaystyle k=\varphi (n)} である。
フェルマー・オイラーの定理

a b i ( i = 1 , ... , k ) {\displaystyle ab_{i}(i=1,\ldots ,k)} はすべて n {\displaystyle n} と互いに素である。さらに、これらを p {\displaystyle p} で割ったとき余りはすべて異なっている。 よって、これらは n {\displaystyle n} と互いに素な数で 1 から n − 1 {\displaystyle n-1} までのものをちょうど1回ずつとる。
フェルマー・オイラーの定理

したがって、
フェルマー・オイラーの定理

である。積 b 1 b 2 ⋯ b k {\displaystyle b_{1}b_{2}\cdots b_{k}} も n {\displaystyle n} と互いに素であるから
フェルマー・オイラーの定理

が成り立つ。
フェルマー・オイラーの定理

素数を法とする場合と同様 a {\displaystyle a} を n {\displaystyle n} と互いに素な数とし、 a l ≡ 1 ( mod n ) {\displaystyle a^{l}\equiv 1{\pmod {n}}} となる最小の正の整数 l {\displaystyle l} を n {\displaystyle n} を法とする a {\displaystyle a} の位数と呼ぶ。
フェルマー・オイラーの定理

位数の法則 から
フェルマー・オイラーの定理

が成り立つ。これと、フェルマー・オイラーの定理から位数は φ ( n ) {\displaystyle \varphi (n)} の約数であることがわかる(この φ ( n ) {\displaystyle \varphi (n)} は、多くの場合、より小さな値をとる関数で置き換えられることを合成数を法とする剰余類の構造で見る)。