初等整数論/合同式

ここでは合同式について説明する。

はじめに

次のような問題を考えてみよう。

問 12345⁶を7で割った余りを求めよ。

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

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

定義

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

1. $a,b$ を $c$ で割った余りが等しいとき、「$a,b$ は $c$ を法として合同」といい、$a\equiv b\ \ {\pmod {c}}$ とかく。
2. $a,b$ について、$c\,|\,a-b$ のとき、「$a,b$ は $c$ を法として合同」といい、$a\equiv b\ \ {\pmod {c}}$ とかく。

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

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

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

${\begin{aligned}a-b&=(cq+r)-(cq'+r')&=c(q-q')\ \ \ (\because (1))\end{aligned}}$

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

次に、1 の意味で合同でない、すなわち $r\neq r'\cdots (2)$ ならば、2 の意味で合同でないことを証明する。

${\begin{aligned}a-b&=(cq+r)-(cq'+r')&=c(q-q')+(r-r')\end{aligned}}$

このとき、$(2)\iff r-r'\neq 0$ より、$a-b$ は $c$ で割り切れない。

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

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

性質

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

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

定理 2.1.1

(i) （反射律）$a\equiv a\ \ {\pmod {n}}$
(ii) （対称律）$a\equiv b\Rightarrow b\equiv a{\pmod {n}}$
(iii)（推移律）$a\equiv b\wedge b\equiv c\Rightarrow a\equiv c\ \ {\pmod {n}}$
(iv) $a\equiv b\wedge c\equiv d\Rightarrow a\pm c\equiv b\pm d\ \ \ {\pmod {n}}$
(v) $a\equiv b\wedge c\equiv d\Rightarrow ac\equiv bd\ \ \ {\pmod {n}}$
(vi) $ab\equiv ac\wedge \gcd(a,n)=1\Rightarrow b\equiv c\ \ {\pmod {n}}$
(vii) $f(a,b,c,\cdots )$ を整数係数多項式とすれば、$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$ ならば任意の整数 $b$ に対し、 $ak\equiv b{\pmod {n}}$ となる $k$ が存在し $n$ を法としてただ1つに定まる（つまり $k$ を $n$ で割った余りが1つに定まる）。

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

(ii) $b-a=-1(a-b)$ なので、$n\,|\,a-b\Rightarrow p\,|\,b-a$ したがって定義より $a\equiv b\Rightarrow b\equiv a{\pmod {n}}$

(iii) (ii) より $a\equiv b\wedge b\equiv c\Rightarrow a\equiv b\wedge c\equiv b\ \ {\pmod {n}}$

$a-c=(a-b)-(c-b)$ より、定理 1.1 から $n\,|\,a-b,c-b\Rightarrow n\,|\,a-c$

$\therefore a\equiv c\ \ {\pmod {n}}$

(iv) $a\equiv b\wedge c\equiv d\ {\pmod {n}}\iff n\,|\,a-b,c-d$

定理 1.1 より $n\,|\,(a-b)+(c-d)\iff n|(a+c)-(c+d)\iff a+c\equiv b+d\ \ \ {\pmod {n}}$

マイナスの方については、$a\equiv b\Rightarrow -a\equiv -b\ \ {\pmod {n}}$ を利用すれば良い。

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

(v)
${\begin{aligned}bd-ac&=bd+ad-ac-ad\\&=d(a-b)+a(c-d)\cdots (1)\end{aligned}}$

ここで、$a\equiv b\wedge c\equiv d\ \ {\pmod {n}}$ であることから、$a-b=nq,c-d=nr$ とおく。すると、

${\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) $ab-ac\,|\,n\iff a(b-c)\,|\,p$

ここで、$(a,n)=1$ なので定理 1.6 より $b-c\,|\,n\iff b\equiv c\ \ {\pmod {p}}$

(vii)
$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}+\cdots +a^{2}b^{k-3}+ab^{k-2}+b^{k-1})$ と $a-b$ を因数に持つことから自明である（(v) を使い、帰納的に証明することもできる）。

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

$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,\cdots )$ なのだから、(iv) を繰り返し使ってこれが証明される。

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

先ほどの問題

問 12345⁶を7で割った余りを求めよ。

これを合同式を用いて解いてみよう。

$12345\equiv 4\ \ {\pmod {7}}$ であるから、定理 2.1 (vii) を用いて、$12345^{6}\equiv 4^{6}\equiv 16^{3}\ \ {\pmod {7}}$

ここで再び、$16\equiv 2{\pmod {7}}$ だから、$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,31\equiv 3,3+28\equiv 3,3+31\equiv 6,6+30\equiv 1,1+31\equiv 4,4+30\equiv 6,6+31\equiv 2,2+31\equiv 5,5+30\equiv 0,0+31\equiv 3,3+30\equiv 5$（平年）

$0,31\equiv 3,3+29\equiv 4,4+31\equiv 0,0+30\equiv 2,2+31\equiv 5,5+30\equiv 0,0+31\equiv 3,3+31\equiv 6,6+30\equiv 1,1+31\equiv 4,4+30\equiv 6$（閏年）

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

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

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

例 3 $4n+3$ の形の素数は無限に多く存在し、 $6n+5$ の形の素数も無限に多く存在する。

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

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

合同方程式の基本定理

まず、2つの多項式 $f(x),g(x)$ が $n$ を法として合同とは、その各係数がすべて $n$ を法として合同であることをいう。合同式に関する定理 2.1.1. (i)-(v) は多項式に対してもそのまま成り立つことが容易にわかる。実際、例えば $f_{1}(x)\equiv g_{1}(x){\pmod {n}},f_{2}(x)\equiv g_{2}(x){\pmod {n}}$ ならば $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)$ が存在するから $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)$ とある整数 $n$ における法について、$f(x)\equiv 0{\pmod {n}}$ という形の式である。定理 2.1.1 より $a\equiv b\Rightarrow f(a)\equiv f(b){\pmod {n}}$ だから、$0,1,\cdots ,n-1$ まで全て代入して確かめてみれば原理的には解けるのである。

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

$p$ を素数とすると、$f(x)\equiv 0{\pmod {p}}$ が m 次の合同式で、 $g(x)\equiv 0{\pmod {p}}$ が n 次の合同式であるとき $f(x)g(x)\equiv 0{\pmod {p}}$ は m+n 次の合同式である。実際 $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}+\cdots$ と n 次の多項式 $g_{1}(x)=b_{n}x^{n}+b_{n-1}x^{n-1}+\cdots$ をとれば $f(x)g(x)\equiv f_{1}(x)g_{1}(x){\pmod {p}}$ となる。ここで $f_{1}(x)g_{1}(x)$ の m+n 次の係数は $a_{m}b_{n}$ である。しかし $f(x)\equiv 0{\pmod {p}}$ は m 次の合同式で、$g(x)\equiv 0{\pmod {p}}$ は n 次の合同式だから $a_{m},b_{n}$ は $p$ で割り切れない。よって $a_{m}b_{n}$ も $p$ で割り切れない（ここで法が素数であることを用いている）。よって $f(x)g(x)\equiv f_{1}(x)g_{1}(x)\equiv 0{\pmod {p}}$ は m+n 次の合同式である。

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

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

定理 2.1.2 (合同方程式の基本定理)

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

$f(x)\equiv (x-x_{1})(x-x_{2})\cdots (x-x_{m})g(x){\pmod {p}},g(x)\not \equiv 0{\pmod {p}}$

と因数分解できる（特に $m\leq n$ である）。

証明
n に関する数学的帰納法で証明する。

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

$a_{1}x+a_{0}\equiv a_{1}(x-x_{1}){\pmod {p}}$

となる。$\gcd(a_{1},p)=1$ より定理は正しい。

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

$f(x)\equiv (x-x_{m})f_{1}(x){\pmod {p}}$

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

$f_{1}(x)\equiv (x-x_{1})(x-x_{2})\cdots (x-x_{m-1})g(x){\pmod {p}}$

となる $g(x)\not \equiv 0{\pmod {p}}$ が存在する。よって

$f(x)\equiv (x-x_{1})\cdots (x-x_{m-1})(x-x_{m})g(x){\pmod {p}}$

となり、この n についても定理が正しい。

よって以上より数学的帰納法によって定理は証明された。

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

剰余系

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

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

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

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

${\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\}$）。このとき、これらの 7 個の整数を「7 を法としての各類の代表の一組、または剰余系」という。

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

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

定理 2.1.3

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

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

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

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

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

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

剰余類環

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

加法

+	0	1	2	3	4	5	6
0	0	1	2	3	4	5	6
1	1	2	3	4	5	6	0
2	2	3	4	5	6	0	1
3	3	4	5	6	0	1	2
4	4	5	6	0	1	2	3
5	5	6	0	1	2	3	4
6	6	0	1	2	3	4	5

乗法

×	0	1	2	3	4	5	6
0	0	0	0	0	0	0	0
1	0	1	2	3	4	5	6
2	0	2	4	6	1	3	5
3	0	3	6	2	5	1	4
4	0	4	1	5	2	6	3
5	0	5	3	1	6	4	2
6	0	6	5	4	3	2	1

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

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

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

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