合同式の計算 | 初等整数論

1 合同と剰余類

定義 1.1 (合同). $m$ を正の整数とする。整数 $a,b$ について $m\mid(a-b)$ が成り立つとき、 $a$ と $b$ は法 $m$ について合同 (congruence) であるといい、 $a\equiv b\pmod m$ と書く。

命題 1.2. $m$ を正の整数、 $a,b$ を整数とする。 $a\equiv b\pmod m$ であるための必要十分条件は、 $a$ と $b$ を $m$ で割った余りが等しいことである。

証明.§A4.1 定理 2.1により、 $a=qm+r$ 、 $b=q'm+s$ 、 $0\le r,s<m$ と書く。 $a-b=(q-q')m+(r-s)$ であるので、 $m\mid(a-b)$ と $m\mid(r-s)$ は同値である。 $-m<r-s<m$ であるので、この範囲にある $m$ の倍数は $0$ だけである。したがって、 $m\mid(r-s)$ と $r=s$ は同値である。▨

定義 1.3 (剰余類). $m$ を正の整数、 $a$ を整数とする。 $a$ と法 $m$ について合同な整数全体の集合 $[a]_m=\{b\in\Z\mid b\equiv a\pmod m\}$ を、 $a$ の法 $m$ に関する剰余類 (residue class) という。 $a$ を剰余類 $[a]_m$ の代表元 (representative) という。

命題 1.2により、合同関係の反射律・対称律・推移律は、余りの等号の対応する性質から従います。したがって、合同関係は同値関係です。また、各整数を $m$ で割った余りは $0,1,\dots,m-1$ のいずれか一つであるので、整数全体は $m$ 個の剰余類 $[0]_m,[1]_m,\dots,[m-1]_m$ に分割されます。

2 合同式の和・差・積

命題 2.1. $m$ を正の整数、 $a,a',b,b'$ を整数とする。 $a\equiv a'\pmod m$ 、 $b\equiv b'\pmod m$ ならば、

a+b\equiv a'+b',\qquad a-b\equiv a'-b',\qquad ab\equiv a'b'\pmod m

が成り立つ。

証明. $(a+b)-(a'+b')=(a-a')+(b-b')$ 、 $(a-b)-(a'-b')=(a-a')-(b-b')$ は、いずれも $m$ の倍数である。また、 $ab-a'b'=a(b-b')+b'(a-a')$ も $m$ の倍数である。▨

命題 2.1により、代表元を替えても、和・差・積の剰余類は変わりません。したがって、剰余類どうしの和・差・積は、代表元どうしで計算した結果の剰余類として定めることができます。

3 合同式の消去

例 3.1. $2\cdot3\equiv2\cdot8\pmod{10}$ であるが、 $3\not\equiv8\pmod{10}$ である。したがって、合同式の両辺を同じ整数で割っても、合同関係が保たれるとは限らない。

命題 3.2. $m$ を正の整数、 $c$ を整数とし、 $d=\gcd(c,m)$ とおく。任意の整数 $a,b$ について、

ca\equiv cb\pmod m \quad\Longleftrightarrow\quad a\equiv b\pmod{m/d}

が成り立つ。したがって、すべての整数 $a,b$ について、 $ca\equiv cb\pmod m$ から $a\equiv b\pmod m$ が従うための必要十分条件は、 $\gcd(c,m)=1$ である。

証明. $c=dc'$ 、 $m=dm'$ と書く。§A4.3 補題 1.1により、 $cu+mv=d$ を満たす整数 $u,v$ を取ると、 $c'u+m'v=1$ である。 $m\mid c(a-b)$ と $m'\mid c'(a-b)$ は同値である。 $m'\mid c'(a-b)$ ならば、

a-b=u c'(a-b)+v m'(a-b)

より $m'\mid(a-b)$ である。逆に、 $m'\mid(a-b)$ ならば $m'\mid c'(a-b)$ である。よって最初の同値が成り立つ。

$d=1$ ならば $m'=m$ なので、法を変えずに $c$ を消去することができる。 $d>1$ ならば $a=m/d$ 、 $b=0$ とおく。 $ca=m(c/d)$ は $m$ の倍数であるが、 $0<a<m$ なので $a$ は $m$ の倍数ではない。したがって、すべての $a,b$ について法を変えずに消去することはできない。▨

例 3.3. 合同式 $6x\equiv8\pmod{14}$ は、 $14\mid2(3x-4)$ と同値であり、両辺と法から共通因子 $2$ を除くと $3x\equiv4\pmod7$ となる。 $3\cdot5\equiv1\pmod7$ なので、両辺に $5$ を掛けると $x\equiv6\pmod7$ を得る。逆に、 $x\equiv6\pmod7$ ならば $3x\equiv18\equiv4\pmod7$ である。したがって整数解は $x=6+7t$ （ $t\in\Z$ ）であり、法 $14$ では $x\equiv6,13\pmod{14}$ の二つの類となる。

4 累乗の余りと周期

命題 4.1. $m$ を正の整数、 $a$ を整数とする。正の整数 $i,T$ が存在して、すべての整数 $n\ge i$ に対して $a^{n+T}\equiv a^n\pmod m$ が成り立つ。

証明. $a^1,a^2,\dots,a^{m+1}$ の余りは $m$ 個の値しか取らないので、 $1\le i<j\le m+1$ かつ $a^i\equiv a^j\pmod m$ を満たす $i,j$ が存在する。任意の整数 $k\ge0$ について、命題 2.1により両辺に $a^k$ を掛けると $a^{i+k}\equiv a^{j+k}\pmod m$ となる。 $T=j-i$ とおけば、すべての $n\ge i$ で所要の合同式が成り立つ。▨

累乗の余りの周期性についての上の命題には、 $a$ と $m$ が互いに素であるという条件はありません。余りの繰り返しが初めの項から始まるとは限りません。たとえば、 $2^1$ の法 $4$ における余りは $2$ ですが、 $n\ge2$ では $2^n$ の余りは $0$ です。

例 4.2. $7^{100}$ の一の位は、法 $10$ における余りである。

7^1\equiv7,\quad7^2\equiv9,\quad7^3\equiv3,\quad7^4\equiv1\pmod{10}

であるので、任意の整数 $n\ge1$ について $7^{n+4}\equiv7^n\pmod{10}$ である。 $100=4\times25$ なので、

7^{100}=(7^4)^{25}\equiv1^{25}\equiv1\pmod{10}

となり、一の位は $1$ である。

5 法の選択による整数解の判定

問題 5.1. 非負整数 $k$ に対し、 $8k+7$ は三つの整数の平方の和として表すことができないことを示せ。

解答.

整数 $t$ が偶数ならば $t=2u$ と書くことができ、 $t^2=4u^2$ の法 $8$ における余りは $0$ または $4$ である。 $t$ が奇数ならば $t=2u+1$ と書くことができる。 $u(u+1)$ は偶数なので、

t^2=4u(u+1)+1\equiv1\pmod8

となる。

$x^2+y^2+z^2=8k+7$ を満たす整数 $x,y,z$ が存在すると仮定する。 $r$ を $x,y,z$ のうち奇数であるものの個数とする。 $r=0$ ならば平方和の余りは $0$ または $4$ 、 $r=1$ ならば $1$ または $5$ 、 $r=2$ ならば $2$ または $6$ 、 $r=3$ ならば $3$ である。いずれの場合も余りは $7$ ではない。これは $8k+7\equiv7\pmod8$ に反する。したがって、所要の整数 $x,y,z$ は存在しない。▨

6 曜日の計算

例 6.1. 日曜日を $0$ 、月曜日を $1$ 、順に土曜日を $6$ と対応させる。今日が日曜日ならば、非負整数 $n$ に対し、 $n$ 日後の曜日は $n$ を $7$ で割った余りで定まる。たとえば、 $100=7\times14+2$ なので、 $100$ 日後は $2$ 日後と同じ火曜日である。

閑話休題：チェックディジットによる入力誤りの検出 ISBN-13 やクレジットカード番号の最後の1桁は、チェックディジットと呼ばれ、合同式を利用して入力誤りを検出するために用いられます。 ISBN-13 では、各桁に $1,3,1,3,\dots$ の重みを掛けた和が $10$ で割り切れるように最後の桁を定めます。クレジットカード番号のルーン・アルゴリズムでは、1桁おきに桁の数字を2倍し、2倍した値が $9$ を超える場合には、その値から $9$ を引きます。こうして得た各桁の値の総和が法 $10$ で $0$ になるように、最後の桁を定めます。

ISBN-13 の1桁を $a$ から異なる数字 $a'$ に替えたとき、重みを $w\in\{1,3\}$ とすると、和の変化は $w(a'-a)$ です。 $w$ と $10$ は互いに素であるので、命題 3.2により $w(a'-a)\equiv0\pmod{10}$ ならば $a'\equiv a\pmod{10}$ です。 $0\le a,a'\le9$ なので、この合同式は $a'=a$ を意味します。したがって、1桁の入力誤りは必ず検出されます。

一方、ISBN-13 の隣接する異なる2桁 $a,b$ を入れ替えると、和の変化は $2(a-b)$ または $-2(a-b)$ です。命題 3.2により、この変化が $10$ で割り切れるための必要十分条件は $a-b\equiv0\pmod5$ です。 $a,b$ が異なる数字であることから、入れ替えが検出されないのは2桁の差の絶対値が $5$ のときです。たとえば、 $0$ と $5$ 、 $1$ と $6$ の入れ替えが該当します。

ISBN-10 では、法を素数 $11$ に取ります。桁の入れ替えによる和の変化を $k(a-b)$ とすると、 $11$ が $k$ を割り切らない限り、命題 3.2により $k(a-b)\equiv0\pmod{11}$ から $a\equiv b\pmod{11}$ が従います。 $0\le a,b\le9$ では、この合同式は $a=b$ を意味するので、異なる数字の入れ替えは検出されます。法と重みの選択によって、検出することができる入力誤りの範囲が変わります。

7 例題

レベル1 — 合同式のべき乗

次の合同式の値を求めよ（法より小さい非負の整数で答えること）。

解法の型位数（ $a^k \equiv 1$ となる最小の $k$ ）を求め、指数を位数で割った余りに落とす

例 7.1.

4^{57} \pmod{13}

答 $12$

注意 $4^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 6$ 。 $57 = 9\times 6 + 3$ より $4^{57} \equiv 4^{3} \equiv 12 \pmod{13}$

例 7.2.

7^{83} \pmod{11}

答 $2$

注意 $7^k \equiv 1 \pmod{11}$ となる最小の $k$ （位数）は $d = 10$ 。 $83 = 8\times 10 + 3$ より $7^{83} \equiv 7^{3} \equiv 2 \pmod{11}$

例 7.3.

5^{55} \pmod{7}

答 $5$

注意 $5^k \equiv 1 \pmod{7}$ となる最小の $k$ （位数）は $d = 6$ 。 $55 = 9\times 6 + 1$ より $5^{55} \equiv 5^{1} \equiv 5 \pmod{7}$

例 7.4.

2^{56} \pmod{13}

答 $9$

注意 $2^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 12$ 。 $56 = 4\times 12 + 8$ より $2^{56} \equiv 2^{8} \equiv 9 \pmod{13}$

例 7.5.

6^{82} \pmod{11}

答 $3$

注意 $6^k \equiv 1 \pmod{11}$ となる最小の $k$ （位数）は $d = 10$ 。 $82 = 8\times 10 + 2$ より $6^{82} \equiv 6^{2} \equiv 3 \pmod{11}$

例 7.6.

3^{44} \pmod{13}

答 $9$

注意 $3^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 3$ 。 $44 = 14\times 3 + 2$ より $3^{44} \equiv 3^{2} \equiv 9 \pmod{13}$

例 7.7.

8^{72} \pmod{7}

答 $1$

注意 $8^k \equiv 1 \pmod{7}$ となる最小の $k$ （位数）は $d = 1$ 。 $72 = 72\times 1 + 0$ より $8^{72} \equiv 8^{0} \equiv 1 \pmod{7}$

例 7.8.

8^{70} \pmod{13}

答 $12$

注意 $8^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 4$ 。 $70 = 17\times 4 + 2$ より $8^{70} \equiv 8^{2} \equiv 12 \pmod{13}$

例 7.9.

2^{66} \pmod{7}

答 $1$

注意 $2^k \equiv 1 \pmod{7}$ となる最小の $k$ （位数）は $d = 3$ 。 $66 = 22\times 3 + 0$ より $2^{66} \equiv 2^{0} \equiv 1 \pmod{7}$

例 7.10.

4^{69} \pmod{11}

答 $3$

注意 $4^k \equiv 1 \pmod{11}$ となる最小の $k$ （位数）は $d = 5$ 。 $69 = 13\times 5 + 4$ より $4^{69} \equiv 4^{4} \equiv 3 \pmod{11}$

8 演習

レベル1 — 合同式のべき乗

次の合同式の値を求めよ（法より小さい非負の整数で答えること）。

解法の型位数（ $a^k \equiv 1$ となる最小の $k$ ）を求め、指数を位数で割った余りに落とす

問題 8.1.

7^{83} \pmod{10}

解答.

答 $3$

注意 $7^k \equiv 1 \pmod{10}$ となる最小の $k$ （位数）は $d = 4$ 。 $83 = 20\times 4 + 3$ より $7^{83} \equiv 7^{3} \equiv 3 \pmod{10}$ ▨

問題 8.2.

6^{54} \pmod{13}

解答.

答 $12$

注意 $6^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 12$ 。 $54 = 4\times 12 + 6$ より $6^{54} \equiv 6^{6} \equiv 12 \pmod{13}$ ▨

問題 8.3.

6^{24} \pmod{13}

解答.

答 $1$

注意 $6^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 12$ 。 $24 = 2\times 12 + 0$ より $6^{24} \equiv 6^{0} \equiv 1 \pmod{13}$ ▨

問題 8.4.

3^{53} \pmod{13}

解答.

答 $9$

注意 $3^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 3$ 。 $53 = 17\times 3 + 2$ より $3^{53} \equiv 3^{2} \equiv 9 \pmod{13}$ ▨

問題 8.5.

9^{71} \pmod{13}

解答.

答 $3$

注意 $9^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 3$ 。 $71 = 23\times 3 + 2$ より $9^{71} \equiv 9^{2} \equiv 3 \pmod{13}$ ▨

問題 8.6.

5^{76} \pmod{11}

解答.

答 $5$

注意 $5^k \equiv 1 \pmod{11}$ となる最小の $k$ （位数）は $d = 5$ 。 $76 = 15\times 5 + 1$ より $5^{76} \equiv 5^{1} \equiv 5 \pmod{11}$ ▨

問題 8.7.

6^{91} \pmod{11}

解答.

答 $6$

注意 $6^k \equiv 1 \pmod{11}$ となる最小の $k$ （位数）は $d = 10$ 。 $91 = 9\times 10 + 1$ より $6^{91} \equiv 6^{1} \equiv 6 \pmod{11}$ ▨

問題 8.8.

5^{25} \pmod{13}

解答.

答 $5$

注意 $5^k \equiv 1 \pmod{13}$ となる最小の $k$ （位数）は $d = 4$ 。 $25 = 6\times 4 + 1$ より $5^{25} \equiv 5^{1} \equiv 5 \pmod{13}$ ▨

問題 8.9.

3^{82} \pmod{7}

解答.

答 $4$

注意 $3^k \equiv 1 \pmod{7}$ となる最小の $k$ （位数）は $d = 6$ 。 $82 = 13\times 6 + 4$ より $3^{82} \equiv 3^{4} \equiv 4 \pmod{7}$ ▨

問題 8.10.

2^{34} \pmod{7}

解答.

答 $2$

注意 $2^k \equiv 1 \pmod{7}$ となる最小の $k$ （位数）は $d = 3$ 。 $34 = 11\times 3 + 1$ より $2^{34} \equiv 2^{1} \equiv 2 \pmod{7}$ ▨

問題 8.11.

6^{32} \pmod{11}

解答.

答 $3$

注意 $6^k \equiv 1 \pmod{11}$ となる最小の $k$ （位数）は $d = 10$ 。 $32 = 3\times 10 + 2$ より $6^{32} \equiv 6^{2} \equiv 3 \pmod{11}$ ▨

問題 8.12.

5^{97} \pmod{11}

解答.

答 $3$

注意 $5^k \equiv 1 \pmod{11}$ となる最小の $k$ （位数）は $d = 5$ 。 $97 = 19\times 5 + 2$ より $5^{97} \equiv 5^{2} \equiv 3 \pmod{11}$ ▨

問題 8.13.

5^{59} \pmod{7}

解答.

答 $3$

注意 $5^k \equiv 1 \pmod{7}$ となる最小の $k$ （位数）は $d = 6$ 。 $59 = 9\times 6 + 5$ より $5^{59} \equiv 5^{5} \equiv 3 \pmod{7}$ ▨

問題 8.14.

3^{97} \pmod{10}

解答.

答 $3$

注意 $3^k \equiv 1 \pmod{10}$ となる最小の $k$ （位数）は $d = 4$ 。 $97 = 24\times 4 + 1$ より $3^{97} \equiv 3^{1} \equiv 3 \pmod{10}$ ▨

問題 8.15.

8^{35} \pmod{7}

解答.

答 $1$

注意 $8^k \equiv 1 \pmod{7}$ となる最小の $k$ （位数）は $d = 1$ 。 $35 = 35\times 1 + 0$ より $8^{35} \equiv 8^{0} \equiv 1 \pmod{7}$ ▨

§A4.5合同式の計算

1 合同と剰余類

2 合同式の和・差・積

3 合同式の消去

4 累乗の余りと周期

5 法の選択による整数解の判定

6 曜日の計算

7 例題

8 演習

前提記事