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

初等整数論/フェルマーの小定理 で、フェルマーの小定理を用いて、素数を法とする剰余類の構造を調べたので、次に、一般の自然数を法とする合同式について考えたい。まず、素数の冪を法とする場合について考え、次に一般の法について考える。
p e {\displaystyle p^{e}} を法とする剰余類は 0 , 1 , ... , p e − 1 {\displaystyle 0,1,\ldots ,p^{e}-1} の 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)} 個存在する。
一方、 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つの場合に分かれる。
1. g ≥ e {\displaystyle g\geq e} のとき b ≡ 0 ( mod p e ) {\displaystyle b\equiv 0{\pmod {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} より、この合同式は解を持たない。
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)} を解に持つ。
次に、合同方程式 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} に対して
より
が成り立つことから、次のことがわかる。
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}}} ならば
となる 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}}} に対して (*) が成り立つ。
数学的帰納法より、次の定理がすぐに導かれる。
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}}} ならば
となる b ( mod p e − 1 ) {\displaystyle b{\pmod {p^{e-1}}}} はちょうど1つ定まる。
例 任意の素数 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)} は、多くの場合、より小さな値をとる関数で置き換えられることを合成数を法とする剰余類の構造で見る)。