初等整数論/合同式
ここでは合同式について説明する。
はじめに

次のような問題を考えてみよう。
はじめに

問 12345を7で割った余りを求めよ。
はじめに

問題の意味だけなら整数の掛け算と割り算を知っていれば理解できるし、原理的にはそれだけの知識でこの問題を解くことはできる。しかし、それはとても大変である。一口に12345というが、これを計算すると3539537889086624823140625(日本語で読めば3𥝱5395垓3788京9086兆6248億2314万625)という25ケタの数であり、これを計算してさらに7で割るなど、手計算ではとてもする気にならない。電卓やそろばんでもこの桁数の計算はできない物が多い。
はじめに

そこで、ここではこの問題をこのような大計算をせずに解く方法を考えてみたい。その道具としての見方から、合同式というものを解説する。
定義

合同の定義には流儀が2つある。
定義

まずはこれらが同値であることを証明する。
定義

除法の原理に基づいて、 a = c q + r ( 0 ≦ r < c ) , b = c q ′ + r ′ ( 0 ≦ r ′ < c ) {\displaystyle a=cq+r\ \ (0\leqq r<c),\ \ \ b=cq'+r'\ \ (0\leqq r'<c)} とおく。まず、1 の意味で合同、すなわち r = r ′ ⋯ ( 1 ) {\displaystyle r=r'\cdots (1)}
定義

ならば、2 の意味で合同であることを証明する。
定義

a − b = ( c q + r ) − ( c q ′ + r ′ ) = c ( q − q ′ ) ( ∵ ( 1 ) ) {\displaystyle {\begin{aligned}a-b&=(cq+r)-(cq'+r')&=c(q-q')\ \ \ (\because (1))\end{aligned}}}
定義

より、1 の意味で合同 ⇒ 2 の意味で合同
定義

次に、1 の意味で合同でない、すなわち r ≠ r ′ ⋯ ( 2 ) {\displaystyle r\neq r'\cdots (2)} ならば、2 の意味で合同でないことを証明する。
定義

a − b = ( c q + r ) − ( c q ′ + r ′ ) = c ( q − q ′ ) + ( r − r ′ ) {\displaystyle {\begin{aligned}a-b&=(cq+r)-(cq'+r')&=c(q-q')+(r-r')\end{aligned}}}
定義

このとき、 ( 2 ) ⟺ r − r ′ ≠ 0 {\displaystyle (2)\iff r-r'\neq 0} より、 a − b {\displaystyle a-b} は c {\displaystyle c} で割り切れない。
定義

したがって、1 の意味で合同でない ⇒ 2 の意味で合同でない
定義

以上より、「1 の意味で合同 ⇔ 2 の意味で合同」が証明される。
性質

除法の原理から、どの整数も n を法として、n で割った余りと合同である。つまり n を法として 0 , 1 , ... , n − 1 {\displaystyle 0,1,\ldots ,n-1} のいずれかと合同である。
性質

ガウスは、合同には = {\displaystyle =} と非常によく似た性質があるから採用した、と述べている。その具体的な性質が次に挙げる定理である。
性質

(i) (反射律) a ≡ a ( mod n ) {\displaystyle a\equiv a\ \ {\pmod {n}}} (ii) (対称律) a ≡ b ⇒ b ≡ a ( mod n ) {\displaystyle a\equiv b\Rightarrow b\equiv a{\pmod {n}}} (iii)(推移律) a ≡ b ∧ b ≡ c ⇒ a ≡ c ( mod n ) {\displaystyle a\equiv b\wedge b\equiv c\Rightarrow a\equiv c\ \ {\pmod {n}}} (iv) a ≡ b ∧ c ≡ d ⇒ a ± c ≡ b ± d ( mod n ) {\displaystyle a\equiv b\wedge c\equiv d\Rightarrow a\pm c\equiv b\pm d\ \ \ {\pmod {n}}} (v) a ≡ b ∧ c ≡ d ⇒ a c ≡ b d ( mod n ) {\displaystyle a\equiv b\wedge c\equiv d\Rightarrow ac\equiv bd\ \ \ {\pmod {n}}} (vi) a b ≡ a c ∧ gcd ( a , n ) = 1 ⇒ b ≡ c ( mod n ) {\displaystyle ab\equiv ac\wedge \gcd(a,n)=1\Rightarrow b\equiv c\ \ {\pmod {n}}} (vii) f ( a , b , c , ⋯ ) {\displaystyle f(a,b,c,\cdots )} を整数係数多項式とすれば、 a ≡ a ′ , b ≡ b ′ , c ≡ c ′ , ⋯ ⇒ f ( a , b , c , ⋯ ) ≡ f ( a ′ , b ′ , c ′ , ⋯ ) ( mod n ) {\displaystyle a\equiv a',b\equiv b',c\equiv c',\cdots \Rightarrow f(a,b,c,\cdots )\equiv f(a',b',c',\cdots )\ \ {\pmod {n}}} (viii) gcd ( a , n ) = 1 {\displaystyle \gcd(a,n)=1} ならば任意の整数 b {\displaystyle b} に対し、 a k ≡ b ( mod n ) {\displaystyle ak\equiv b{\pmod {n}}} となる k {\displaystyle k} が存在し n {\displaystyle n} を法としてただ1つに定まる(つまり k {\displaystyle k} を n {\displaystyle n} で割った余りが1つに定まる)。
性質

証明 (i) a − a = 0 {\displaystyle a-a=0} は全ての整数で割り切れる。したがって、 a ≡ a ( mod n ) {\displaystyle a\equiv a\ {\pmod {n}}}
性質

(ii) b − a = − 1 ( a − b ) {\displaystyle b-a=-1(a-b)} なので、 n | a − b ⇒ p | b − a {\displaystyle n\,|\,a-b\Rightarrow p\,|\,b-a} したがって定義より a ≡ b ⇒ b ≡ a ( mod n ) {\displaystyle a\equiv b\Rightarrow b\equiv a{\pmod {n}}}
性質

(iii) (ii) より a ≡ b ∧ b ≡ c ⇒ a ≡ b ∧ c ≡ b ( mod n ) {\displaystyle a\equiv b\wedge b\equiv c\Rightarrow a\equiv b\wedge c\equiv b\ \ {\pmod {n}}}
性質

a − c = ( a − b ) − ( c − b ) {\displaystyle a-c=(a-b)-(c-b)} より、定理 1.1 から n | a − b , c − b ⇒ n | a − c {\displaystyle n\,|\,a-b,c-b\Rightarrow n\,|\,a-c}
性質

∴ a ≡ c ( mod n ) {\displaystyle \therefore a\equiv c\ \ {\pmod {n}}}
性質

(iv) a ≡ b ∧ c ≡ d ( mod n ) ⟺ n | a − b , c − d {\displaystyle a\equiv b\wedge c\equiv d\ {\pmod {n}}\iff n\,|\,a-b,c-d}
性質

定理 1.1 より n | ( a − b ) + ( c − d ) ⟺ n | ( a + c ) − ( c + d ) ⟺ a + c ≡ b + d ( mod n ) {\displaystyle n\,|\,(a-b)+(c-d)\iff n|(a+c)-(c+d)\iff a+c\equiv b+d\ \ \ {\pmod {n}}}
性質

マイナスの方については、 a ≡ b ⇒ − a ≡ − b ( mod n ) {\displaystyle a\equiv b\Rightarrow -a\equiv -b\ \ {\pmod {n}}} を利用すれば良い。
性質

問 マイナスの方を証明せよ。
性質

(v) b d − a c = b d + a d − a c − a d = d ( a − b ) + a ( c − d ) ⋯ ( 1 ) {\displaystyle {\begin{aligned}bd-ac&=bd+ad-ac-ad\\&=d(a-b)+a(c-d)\cdots (1)\end{aligned}}}
性質

ここで、 a ≡ b ∧ c ≡ d ( mod n ) {\displaystyle a\equiv b\wedge c\equiv d\ \ {\pmod {n}}} であることから、 a − b = n q , c − d = n r {\displaystyle a-b=nq,c-d=nr} とおく。すると、
性質

( 1 ) ⟺ b d − a c = d n q + a n r ⟺ b d − a c = n ( d q + a r ) ⟺ b d ≡ a c ( mod n ) ⇒ a c ≡ b d ( mod n ) ( ∵ ( i i ) ) {\displaystyle {\begin{aligned}(1)&\iff bd-ac=dnq+anr\\&\iff bd-ac=n(dq+ar)\\&\iff bd\equiv ac\ \ {\pmod {n}}\\&\Rightarrow ac\equiv bd\ \ {\pmod {n}}(\because (ii))\end{aligned}}}
性質

(vi) a b − a c | n ⟺ a ( b − c ) | p {\displaystyle ab-ac\,|\,n\iff a(b-c)\,|\,p}
性質

ここで、 ( a , n ) = 1 {\displaystyle (a,n)=1} なので定理 1.6 より b − c | n ⟺ b ≡ c ( mod p ) {\displaystyle b-c\,|\,n\iff b\equiv c\ \ {\pmod {p}}}
性質

(vii) a ≡ b ⇒ a k ≡ b k ( mod p ) {\displaystyle a\equiv b\Rightarrow a^{k}\equiv b^{k}\ \ {\pmod {p}}} をまずは証明する。これは、
性質

a k − b k = ( a − b ) ( a k − 1 + a k − 2 b + a k − 3 b 2 + ⋯ + a 2 b k − 3 + a b k − 2 + b k − 1 ) {\displaystyle a^{k}-b^{k}=(a-b)(a^{k-1}+a^{k-2}b+a^{k-3}b^{2}+\cdots +a^{2}b^{k-3}+ab^{k-2}+b^{k-1})} と a − b {\displaystyle a-b} を因数に持つことから自明である((v) を使い、帰納的に証明することもできる)。
性質

さて、多変数の整数係数多項式とは、すなわち、 a k b l c m ⋯ {\displaystyle a^{k}b^{l}c^{m}\cdots } の総和である。先ほど証明したことから、
性質

a ≡ a ′ , b ≡ b ′ , c ≡ c ′ ⋯ ⇒ a k ≡ a ′ k , b l ≡ b ′ l , c m ≡ c ′ m , ⋯ ( mod p ) {\displaystyle a\equiv a',b\equiv b',c\equiv c'\cdots \Rightarrow a^{k}\equiv a'^{k},b^{l}\equiv b'^{l},c^{m}\equiv c'^{m},\cdots \ \ {\pmod {p}}}
性質

したがって、(v) を繰り返し使えば、一つの項についてこれは正しい。また、これらの項の総和が f ( a , b , c , ⋯ ) {\displaystyle f(a,b,c,\cdots )} なのだから、(iv) を繰り返し使ってこれが証明される。
性質

(viii) 定理 1.8 から、このような k {\displaystyle k} が存在し、 n {\displaystyle n} を法として1つに定まることがすぐに従う(なお (vi) からも a k ≡ a l ≡ b ( mod n ) {\displaystyle ak\equiv al\equiv b{\pmod {n}}} ならば k ≡ l ( mod n ) {\displaystyle k\equiv l{\pmod {n}}} であるから n {\displaystyle n} を法として1つに定まることがわかる)。
先ほどの問題

問 12345を7で割った余りを求めよ。
先ほどの問題

これを合同式を用いて解いてみよう。
先ほどの問題

12345 ≡ 4 ( mod 7 ) {\displaystyle 12345\equiv 4\ \ {\pmod {7}}} であるから、定理 2.1 (vii) を用いて、 12345 6 ≡ 4 6 ≡ 16 3 ( mod 7 ) {\displaystyle 12345^{6}\equiv 4^{6}\equiv 16^{3}\ \ {\pmod {7}}}
先ほどの問題

ここで再び、 16 ≡ 2 ( mod 7 ) {\displaystyle 16\equiv 2{\pmod {7}}} だから、 16 3 ≡ 2 3 ≡ 1 ( mod 7 ) {\displaystyle 16^{3}\equiv 2^{3}\equiv 1\ \ {\pmod {7}}}
先ほどの問題

となり、直接計算するよりかなり簡単に求まった。
単純な応用例

合同式についてより深く考察する前に、単純な応用の例をあげる。
単純な応用例

例 1 1年の間には必ず13日の金曜日が訪れる。さらに、1年の間に13日は日曜日から土曜日までのすべての曜日を取る。1月13日が 7 を法として 0 と合同となるように、各曜日を 7 を法として分類すると、1月13日から12月13日まではそれぞれ 7 を法として
単純な応用例

と合同となる。よっていずれの場合も 0 から 6 まで全て現れるので1年の間に(より正確に、1月から10月の間に)13日は日曜日から土曜日までのすべての曜日を取る。
単純な応用例

例 2 平方数を 3 で割った余りは 0 または 1 でなければならない。つまり 3 k + 2 {\displaystyle 3k+2} の形の平方数は存在しない。 0 2 ≡ 0 ( mod 3 ) , 1 2 ≡ 2 2 ≡ 1 ( mod 3 ) {\displaystyle 0^{2}\equiv 0{\pmod {3}},1^{2}\equiv 2^{2}\equiv 1{\pmod {3}}} なので n を 3 で割った余りが 0 ならば n 2 ≡ 0 ( mod 3 ) {\displaystyle n^{2}\equiv 0{\pmod {3}}} で、そうでないときは n 2 ≡ 1 ( mod 3 ) {\displaystyle n^{2}\equiv 1{\pmod {3}}} となるからである。同様にして平方数を 4 で割った余りは 0 または 1 でなければならない。つまり 4 k + 2 {\displaystyle 4k+2} あるいは 4 k + 3 {\displaystyle 4k+3} の形の平方数は存在しない。
単純な応用例

これを使い、素数の分布について、次の事実が証明できる。
単純な応用例

例 3 4 n + 3 {\displaystyle 4n+3} の形の素数は無限に多く存在し、 6 n + 5 {\displaystyle 6n+5} の形の素数も無限に多く存在する。
単純な応用例

証明 任意の素数 p に対し、それより大きな、与えられた形の素数が存在することを証明すればよい。 q = 2 2 ⋅ 3 ⋅ 5 ⋯ p − 1 {\displaystyle q=2^{2}\cdot 3\cdot 5\cdots p-1} とおくと q ≡ 3 ( mod 4 ) {\displaystyle q\equiv 3{\pmod {4}}} かつ q ≡ 5 ( mod 6 ) {\displaystyle q\equiv 5{\pmod {6}}} である。 q {\displaystyle q} の素因数を p 1 , p 2 , ... , p r {\displaystyle p_{1},p_{2},\ldots ,p_{r}} とおく。 これらがすべて 4 を法として 1 と合同ならば q = p 1 p 2 ⋯ p r ≡ 1 ( mod 4 ) {\displaystyle q=p_{1}p_{2}\cdots p_{r}\equiv 1{\pmod {4}}} となり、 q ≡ 3 ( mod 4 ) {\displaystyle q\equiv 3{\pmod {4}}} に矛盾する。 よって p i ≡ 3 ( mod 4 ) {\displaystyle p_{i}\equiv 3{\pmod {4}}} となる pi が存在する。 q = 2 2 ⋅ 3 ⋅ 5 ⋯ p − 1 {\displaystyle q=2^{2}\cdot 3\cdot 5\cdots p-1} は 2 , 3 , 5 , ... , p {\displaystyle 2,3,5,\ldots ,p} のいずれとも互いに素だから p i > p {\displaystyle p_{i}>p} でなければならない。同様に p 1 , p 2 , ... , p r {\displaystyle p_{1},p_{2},\ldots ,p_{r}} がすべて 6 を法として 1 と合同ならば q = p 1 p 2 ⋯ p r ≡ 1 ( mod 6 ) {\displaystyle q=p_{1}p_{2}\cdots p_{r}\equiv 1{\pmod {6}}} となり、 q ≡ 5 ( mod 6 ) {\displaystyle q\equiv 5{\pmod {6}}} に矛盾する。よって p j ≡ 5 ( mod 6 ) {\displaystyle p_{j}\equiv 5{\pmod {6}}} となる pj が存在し、 p j > p {\displaystyle p_{j}>p} でなければならない。
単純な応用例

例 2 は平方数をある数で割った余りがどのような数になることができ、どのような数になり得ないかという問題に一般化できる。これを表したものが平方剰余である。さらに一般の累乗に拡張したものがべき剰余である。
合同方程式の基本定理

まず、2つの多項式 f ( x ) , g ( x ) {\displaystyle f(x),g(x)} が n {\displaystyle n} を法として合同とは、その各係数がすべて n {\displaystyle n} を法として合同であることをいう。合同式に関する定理 2.1.1. (i)-(v) は多項式に対してもそのまま成り立つことが容易にわかる。実際、例えば f 1 ( x ) ≡ g 1 ( x ) ( mod n ) , f 2 ( x ) ≡ g 2 ( x ) ( mod n ) {\displaystyle f_{1}(x)\equiv g_{1}(x){\pmod {n}},f_{2}(x)\equiv g_{2}(x){\pmod {n}}} ならば f 1 ( x ) = g 1 ( x ) + n h 1 ( x ) , f 2 ( x ) ≡ g 2 ( x ) + n h 2 ( x ) {\displaystyle f_{1}(x)=g_{1}(x)+nh_{1}(x),f_{2}(x)\equiv g_{2}(x)+nh_{2}(x)} となる整数係数の多項式 h 1 ( x ) , h 2 ( x ) {\displaystyle h_{1}(x),h_{2}(x)} が存在するから f 1 ( x ) f 2 ( x ) ≡ g 1 ( x ) g 2 ( x ) + n ( g 1 ( x ) h 2 ( x ) + g 2 h 1 ( x ) ) + n 2 h 1 ( x ) h 2 ( x ) ≡ g 1 ( x ) g 2 ( x ) ( mod n ) {\displaystyle f_{1}(x)f_{2}(x)\equiv g_{1}(x)g_{2}(x)+n(g_{1}(x)h_{2}(x)+g_{2}h_{1}(x))+n^{2}h_{1}(x)h_{2}(x)\equiv g_{1}(x)g_{2}(x){\pmod {n}}} が成り立つ。
合同方程式の基本定理

合同方程式とは、多項式 f ( x ) {\displaystyle f(x)} とある整数 n {\displaystyle n} における法について、 f ( x ) ≡ 0 ( mod n ) {\displaystyle f(x)\equiv 0{\pmod {n}}} という形の式である。定理 2.1.1 より a ≡ b ⇒ f ( a ) ≡ f ( b ) ( mod n ) {\displaystyle a\equiv b\Rightarrow f(a)\equiv f(b){\pmod {n}}} だから、 0 , 1 , ⋯ , n − 1 {\displaystyle 0,1,\cdots ,n-1} まで全て代入して確かめてみれば原理的には解けるのである。
合同方程式の基本定理

f ( x ) = a n x n + a n − 1 x n − 1 + ⋯ + a 1 x + a 0 {\displaystyle f(x)=a_{n}x^{n}+a_{n-1}x^{n-1}+\cdots +a_{1}x+a_{0}} について、各係数 a γ {\displaystyle a_{\gamma }} を他の合同な数で置き換えても良い。特に、法 k {\displaystyle k} で割り切れるときは、その項を消去しても良い。この操作をしたとき、 a n ≢ 0 ( mod k ) {\displaystyle a_{n}\not \equiv 0{\pmod {k}}} のとき、この合同式を n 次といい、 合同式 f ( x ) ≡ 0 ( mod k ) {\displaystyle f(x)\equiv 0{\pmod {k}}} が n 次であることの必要十分条件は f ( x ) ≡ g ( x ) ( mod k ) {\displaystyle f(x)\equiv g(x){\pmod {k}}} となる多項式 g ( x ) {\displaystyle g(x)} の中で最低次数のものが n 次であることである。そのような g ( x ) {\displaystyle g(x)} の最高次、つまり n 次の係数は k {\displaystyle k} で割り切れない(割り切れるならば、その係数を消去することで、さらに低い次数の、 f ( x ) {\displaystyle f(x)} と合同な多項式がとれるからである)。
合同方程式の基本定理

p {\displaystyle p} を素数とすると、 f ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}} が m 次の合同式で、 g ( x ) ≡ 0 ( mod p ) {\displaystyle g(x)\equiv 0{\pmod {p}}} が n 次の合同式であるとき f ( x ) g ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)g(x)\equiv 0{\pmod {p}}} は m+n 次の合同式である。実際 f ( x ) = p f 0 ( x ) + f 1 ( x ) , g ( x ) = p g 0 ( x ) + g 1 ( x ) {\displaystyle f(x)=pf_{0}(x)+f_{1}(x),g(x)=pg_{0}(x)+g_{1}(x)} となるように m次の多項式 f 1 ( x ) = a m x m + a m − 1 x m − 1 + ⋯ {\displaystyle f_{1}(x)=a_{m}x^{m}+a_{m-1}x^{m-1}+\cdots } と n 次の多項式 g 1 ( x ) = b n x n + b n − 1 x n − 1 + ⋯ {\displaystyle g_{1}(x)=b_{n}x^{n}+b_{n-1}x^{n-1}+\cdots } をとれば f ( x ) g ( x ) ≡ f 1 ( x ) g 1 ( x ) ( mod p ) {\displaystyle f(x)g(x)\equiv f_{1}(x)g_{1}(x){\pmod {p}}} となる。ここで f 1 ( x ) g 1 ( x ) {\displaystyle f_{1}(x)g_{1}(x)} の m+n 次の係数は a m b n {\displaystyle a_{m}b_{n}} である。しかし f ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}} は m 次の合同式で、 g ( x ) ≡ 0 ( mod p ) {\displaystyle g(x)\equiv 0{\pmod {p}}} は n 次の合同式だから a m , b n {\displaystyle a_{m},b_{n}} は p {\displaystyle p} で割り切れない。よって a m b n {\displaystyle a_{m}b_{n}} も p {\displaystyle p} で割り切れない(ここで法が素数であることを用いている)。よって f ( x ) g ( x ) ≡ f 1 ( x ) g 1 ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)g(x)\equiv f_{1}(x)g_{1}(x)\equiv 0{\pmod {p}}} は m+n 次の合同式である。
合同方程式の基本定理

これは素数以外の法では一般に正しくない。たとえば ( 2 x + 1 ) ( 3 x + 1 ) ≡ 5 x + 1 ( mod 6 ) {\displaystyle (2x+1)(3x+1)\equiv 5x+1{\pmod {6}}} となる。左辺の 1 次の係数同士を掛けると 6 を法として消えてしまうからである。
合同方程式の基本定理

素数を法とする合同方程式について、以下の基本的な事実が成り立つ。
合同方程式の基本定理

法 p {\displaystyle p} が素数のとき、n 次の合同式 f ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}} は高々 n 個の解を持つ。もちろん解は p を法として互いに不合同なものを数える。より強く、n 次の合同式 f ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}} が互いに不合同な解 x = x 1 , x 2 , ... , x m {\displaystyle x=x_{1},x_{2},\ldots ,x_{m}} を持つならば、
合同方程式の基本定理

と因数分解できる(特に m ≤ n {\displaystyle m\leq n} である)。
合同方程式の基本定理

証明 n に関する数学的帰納法で証明する。
合同方程式の基本定理

n = 1 {\displaystyle n=1} のときは f ( x ) {\displaystyle f(x)} と合同な 1次式を g ( x ) = a 1 x + a 0 {\displaystyle g(x)=a_{1}x+a_{0}} とおく。 gcd ( a 1 , p ) = 1 {\displaystyle \gcd(a_{1},p)=1} であるから定理 1.8 より、 a 1 x {\displaystyle a_{1}x} が − a 0 {\displaystyle -a_{0}} と合同になるような x = x 1 {\displaystyle x=x_{1}} が p {\displaystyle p} を法として、ただひとつ存在する。すなわち、 a 1 x + a 0 ≡ 0 ( mod p ) {\displaystyle a_{1}x+a_{0}\equiv 0{\pmod {p}}} はただひとつの解を有する。そしてこのとき
合同方程式の基本定理

となる。 gcd ( a 1 , p ) = 1 {\displaystyle \gcd(a_{1},p)=1} より定理は正しい。
合同方程式の基本定理

n-1 次の合同式に対して定理が正しいと仮定し、 f ( x ) ≡ 0 ( mod p ) {\displaystyle f(x)\equiv 0{\pmod {p}}} を n 次の合同式とする。 f ( x m ) ≡ 0 ( mod p ) {\displaystyle f(x_{m})\equiv 0{\pmod {p}}} より f ( x ) = ( x − x m ) f 1 ( x ) + f ( x m ) {\displaystyle f(x)=(x-x_{m})f_{1}(x)+f(x_{m})} となる多項式 f 1 ( x ) {\displaystyle f_{1}(x)} が存在する。 f ( x m ) ≡ 0 ( mod p ) {\displaystyle f(x_{m})\equiv 0{\pmod {p}}} より
合同方程式の基本定理

を得る。上の事実から f 1 ( x ) ≡ 0 ( mod p ) {\displaystyle f_{1}(x)\equiv 0{\pmod {p}}} は n-1 次の合同式である。 p {\displaystyle p} は素数なのだから、定理 1.12 より与式は x − x m {\displaystyle x-x_{m}} または f 1 ( x ) {\displaystyle f_{1}(x)} が p {\displaystyle p} で割り切れるときにだけ成り立つ。したがって、 f ( x ) ≡ 0 {\displaystyle f(x)\equiv 0} の x m {\displaystyle x_{m}} 以外の解 x 1 , x 2 , ... , x m − 1 {\displaystyle x_{1},x_{2},\ldots ,x_{m-1}} は f 1 ( x ) ≡ 0 {\displaystyle f_{1}(x)\equiv 0} の解である( x m {\displaystyle x_{m}} も依然として f 1 ( x ) ≡ 0 {\displaystyle f_{1}(x)\equiv 0} の解かも知れないが、証明には影響しない)。 f 1 ( x ) ≡ 0 ( mod p ) {\displaystyle f_{1}(x)\equiv 0{\pmod {p}}} は n-1 次の合同式だから、帰納法の仮定より
合同方程式の基本定理

となる g ( x ) ≢ 0 ( mod p ) {\displaystyle g(x)\not \equiv 0{\pmod {p}}} が存在する。よって
合同方程式の基本定理

となり、この n についても定理が正しい。
合同方程式の基本定理

よって以上より数学的帰納法によって定理は証明された。
合同方程式の基本定理

x ( x − 1 ) ≡ 0 ( mod 2 ) {\displaystyle x(x-1)\equiv 0{\pmod {2}}} はすべての整数 x=k に対して成り立つが、左辺の多項式は 2 を法としても 0 (正確には零多項式)と合同ではない。このように、すべての整数 k に対して f ( k ) ≡ g ( k ) ( mod n ) {\displaystyle f(k)\equiv g(k){\pmod {n}}} となるからといって多項式 f ( x ) , g ( x ) {\displaystyle f(x),g(x)} が n を法として合同であるとは限らないので注意しなければならない。
剰余系

法を 7 とした場合、余りとして可能性のあるのは 0 , 1 , 2 , 3 , 4 , 5 , 6 {\displaystyle 0,1,2,3,4,5,6} の 7 種類である。
剰余系

そこで、同じ余りの数の集合、例えば { ⋯ − 13 , − 6 , 1 , 8 , 15 ⋯ } {\displaystyle \{\cdots -13,-6,1,8,15\cdots \}} は、どの2つをとっても合同である。この集合のことを、一般に「m を法としての類」という。
剰余系

m を法としての類に属する全ての数は、類の任意の1つの数 a {\displaystyle a} を取ってきて、 a + n t ( t = ⋯ , − 2 , − 1 , 0 , 1 , 2 ⋯ ) {\displaystyle a+nt\ \ (t=\cdots ,-2,-1,0,1,2\cdots )} と表せる。この a {\displaystyle a} を類の「代表」の元、という。
剰余系

さて、あまりの可能性としてあるのは 7 種類だったから、7 を法としての類は全部で 7 種類できる。
剰余系

{ ⋯ − 14 , − 7 , 0 , 7 , 14 ⋯ } { ⋯ − 13 , − 6 , 1 , 8 , 15 ⋯ } { ⋯ − 12 , − 5 , 2 , 9 , 16 ⋯ } { ⋯ − 11 , − 4 , 3 , 10 , 17 ⋯ } { ⋯ − 10 , − 3 , 4 , 11 , 18 ⋯ } { ⋯ − 9 , − 2 , 5 , 12 , 19 ⋯ } { ⋯ − 8 , − 1 , 6 , 13 , 20 ⋯ } {\displaystyle {\begin{aligned}&\{\cdots -14,-7,0,7,14\cdots \}\\&\{\cdots -13,-6,1,8,15\cdots \}\\&\{\cdots -12,-5,2,9,16\cdots \}\\&\{\cdots -11,-4,3,10,17\cdots \}\\&\{\cdots -10,-3,4,11,18\cdots \}\\&\{\cdots -9,-2,5,12,19\cdots \}\\&\{\cdots -8,-1,6,13,20\cdots \}\\\end{aligned}}}
剰余系

が全ての類である。このとき、これらの 7 種類の類から数を1つずつ取り出してきたとする(例えば、 { 0 , 1 , 2 , 3 , 4 , 5 , 6 } , { − 14 , 8 , 2 , 10 , − 3 , − 2 , 6 } {\displaystyle \{0,1,2,3,4,5,6\},\{-14,8,2,10,-3,-2,6\}} )。このとき、これらの 7 個の整数を「7 を法としての各類の代表の一組、または剰余系」という。
剰余系

一般に、m を法としての m 種類の類から数を1つずつ取り出したとき、これらの m 個の数は「m を法としての各類の代表の一組、または剰余系」という。
剰余系

さて、剰余系に関して、次の定理が成り立つ。
剰余系

要素が m {\displaystyle m} 個の集合 M {\displaystyle M} が m {\displaystyle m} を法としての剰余系であるための必要十分条件は、 M {\displaystyle M} のどの2つをとっても互いに不合同であることである。
剰余系

証明 定義より、 M {\displaystyle M} が剰余系ならば M {\displaystyle M} のどの2つをとっても互いに不合同なのは自明。
剰余系

要素が m {\displaystyle m} 個の集合 M {\displaystyle M} のどの2つをとっても互いに不合同であるとしよう。余りの種類は 0 , 1 , ⋯ , m − 1 {\displaystyle 0,1,\cdots ,m-1} の m {\displaystyle m} 種類である。合同の定義より、どの2つをとっても互いに不合同であるので、割った余りを定めればそれに対応する M {\displaystyle M} の要素は見つかるはずである。(w:鳩の巣原理)
剰余系

除法の原理より、全ての整数はただ一通りに k = m q + r ( 0 ≦ r < m ) {\displaystyle k=mq+r\ (0\leqq r<m)} と表せる。先ほどの議論から、 t ∈ M , t ≡ r ( mod m ) {\displaystyle t\in M,\ t\equiv r{\pmod {m}}} となる t {\displaystyle t} が存在する。合同の定義より、 t − r = m s {\displaystyle t-r=ms} とおくと、
剰余系

r = t − m s ⟺ m q + r = t − m s + m q ⟺ k = t + m ( q − s ) {\displaystyle r=t-ms\iff mq+r=t-ms+mq\iff k=t+m(q-s)} となり、 k {\displaystyle k} を、 t {\displaystyle t} によって代表される類の数として表すことが出来た。またこれはただ一通りであり、 k {\displaystyle k} は任意の数である。すなわち、 M {\displaystyle M} は剰余系をなしている。
剰余系

さて、規約剰余系というものが出てきたが、一般に ( r , m ) = d ⇒ ( r + m t , m ) = d {\displaystyle (r,m)=d\Rightarrow (r+mt,m)=d} であるので、類の数は全て法と互いに素、もしくは一定の最大公約数を持つ。そのうち、互いに素な数のみの類を既約類といい、剰余系のうち既約類のみから数を取り出したものを規約剰余系という。
剰余系

7 を法とした剰余系として最も簡単なものは、おそらく M = { 0 , 1 , 2 , 3 , 4 , 5 , 6 } {\displaystyle M=\{0,1,2,3,4,5,6\}} だろう。これに、加法と乗法を定義する。
剰余系

どのようにこの表を作っているかというと、 M {\displaystyle M} は剰余系なので、任意の数 k {\displaystyle k} は m ≡ k ( mod 7 ) {\displaystyle m\equiv k{\pmod {7}}} なる m ∈ M {\displaystyle m\in M} がただひとつ存在する。そこで、 a , b ∈ M {\displaystyle a,b\in M} について、 a + b , a b {\displaystyle a+b,ab} を M {\displaystyle M} のただひとつの要素 m , n {\displaystyle m,n} と合同であるようにすることができる。そのときの m , n {\displaystyle m,n} をそれぞれ、 a + b = m , a b = n {\displaystyle a+b=m,ab=n} と定義するのである。
剰余系

この概念は任意の法に拡張することができる。そのとき法とする数によって、 Z / m Z {\displaystyle \mathbb {Z} /m\mathbb {Z} } と書く。また、これは類の代表の元の選び方によらない。
剰余系

このようにして定義された加法と乗法による剰余系は、環をなす。
剰余系

また 定理 2.1.1 (viii) より gcd ( a , n ) = 1 {\displaystyle \gcd(a,n)=1} である限り a k ≡ b ( mod n ) {\displaystyle ak\equiv b{\pmod {n}}} となる k {\displaystyle k} が存在し、しかもそのような k {\displaystyle k} の属する剰余類はただ1つに定まることがわかる。特に a k ≡ 1 ( mod n ) {\displaystyle ak\equiv 1{\pmod {n}}} となる k {\displaystyle k} の属する剰余類は乗法に関する a {\displaystyle a} の逆元である。これを a ̄ {\displaystyle {\bar {a}}} であらわすことがある。このとき a k ≡ b ( mod n ) ⟺ k ≡ b a ̄ ( mod p ) {\displaystyle ak\equiv b{\pmod {n}}\iff k\equiv b{\bar {a}}{\pmod {p}}} である。 また特に、法が素数のとき、0以外の剰余類はすべて逆元をもつので、この剰余系は(有限)体をなす。