目次 ／ 整数の性質 ／ 数学A

第5章　余りと合同式

—— 整数を「割った余り」だけで見分け、余りどうしで計算する ——

整数の問題では、数そのものの大きさより「何で割ると、いくつ余るか」が決め手になることがよくあります。この章では、整数を余りによって仲間分けする考え方から出発し、余りだけで足し算や掛け算ができることを確かめます。そのうえで、余りの計算をすっきり書ける記号「合同式」を導入し、大きな累乗の余りや、余りについての方程式を解く方法を学びます。合同式は発展的な道具なので、使わずに解く方法もあわせて示します。

問題マップ記録を読み込み中…
基1基2基3基4基51234567891011121314151617181920
未回答 25× 0○ 01か月定着 0

余りに注目する

第2章で、整数 aa と正の整数 mm に対して

a\displaystyle a=mq\displaystyle {}= mq+r\displaystyle {}+ r(0≦r<m)\displaystyle (0 \leqq r < m)

となる整数 qq，rr がただ1組決まることを学びました（割り算の等式）。第4章では、nn で割った余りが nn 進法の最下位の数字になることも見ました。この章では、商 qq のほうはいったん忘れて、余り rr だけに注目します。

「20262026 は偶数か」「720267^{2026} の一の位は何か」「n2n^2+1{}+ 1 は 33 の倍数になりうるか」。こうした問いは、数を最後まで計算しなくても、余りを見るだけで答えられます。余りは 00 から mm−1{}- 1 までの mm 通りしかないので、無限にある整数の問題を、有限個の場合の確認に置きかえられるのです。

これまでの章と同じく、とくに断らないかぎり文字は整数を表します。

余りによる分類

公式1：余りによる整数の分類

mm を 22 以上の整数とする。すべての整数 nn は、ある整数 kk を用いて

n\displaystyle n=mk,\displaystyle {}= mk,mk\displaystyle mk+1,\displaystyle {}+ 1,mk\displaystyle mk+2,\displaystyle {}+ 2,…,\displaystyle \ldots,mk\displaystyle mk+(m−1)\displaystyle {}+ (m - 1)

のどれかただ1つの形に表せる。これは nn を mm で割った余りが 0,0, 1,\ 1, …,\ \ldots, m\ m−1{}- 1 のどれかであることを言いかえたものである。

mm=2{}= 2 なら、整数は 2k2k（偶数）と 2k2k+1{}+ 1（奇数）に分かれます。mm=3{}= 3 なら 3k3k，3k3k+1{}+ 1，3k3k+2{}+ 2 の3種類です。割り算の等式で余りがただ1つに決まるので、どの整数もこのうちちょうど1つに入り、2つにまたがることはありません。負の数も例外ではなく、たとえば −4-4=3⋅(−2){}= 3 \cdot (-2)+2{}+ 2 ですから、−4-4 は 3k3k+2{}+ 2 の仲間です。

余り 0（3k） 余り 1（3k + 1） 余り 2（3k + 2） −4 −3 −2 −1 0 1 2 3 4 5 6 7 8 9 10 −4 −3 −2 −1 0 1 2 3 4 5 6 7 8 9 10 −4 = 3 × (−2) + 2 なので、−4 も「余り 2」の段に入る

3k3k+2{}+ 2=3(k+1){}= 3(k + 1)−1{}- 1 なので、3k3k+2{}+ 2 のかわりに 3k3k−1{}- 1 と書いてもかまいません。同じように、55 で割るときは 5k,5k, 5k\ 5k±1,{}\pm 1, 5k\ 5k±2{}\pm 2 と分けると、22 乗したときの計算が楽になります。

運動会で、出席番号 1,1, 4,\ 4, 7,\ 7, …\ \ldots の人を赤組、2,2, 5,\ 5, 8,\ 8, …\ \ldots の人を白組、3,3, 6,\ 6, 9,\ 9, …\ \ldots の人を青組にする、という組分けを考えてみてください。クラスの全員がどれか1つの組に入り、2つの組をかけもちする人はいません。「クラス全員が〇〇を満たす」ことを確かめたいとき、11 人ずつ調べる代わりに、組ごとに1回ずつ確かめれば済みます。公式1 による場合分けは、無限にいる整数を、この3つの組に分けて調べる方法です。

整数は mm で割った余りによって mm 種類に過不足なく分けられるので、すべての整数についての主張は、mm 通りの場合分けで確かめられるということです。

例題1：余りによる場合分け

nn を整数とする。

(1) n2n^2 を 33 で割った余りは 00 か 11 であることを示しなさい。

(2) n2n^2+1{}+ 1 は 33 の倍数でないことを示しなさい。

【解答】

(1) nn は 3k3k，3k3k+1{}+ 1，3k3k−1{}- 1（kk は整数）のどれかの形に表せます。

  • nn=3k{}= 3k のとき、n2n^2=9k2{}= 9k^2=3⋅3k2{}= 3 \cdot 3k^2 で、余りは 00 です。
  • nn=3k{}= 3k±1{}\pm 1 のとき（複号同順）、n2n^2=9k2{}= 9k^2±6k{}\pm 6k+1{}+ 1=3(3k2±2k){}= 3(3k^2 \pm 2k)+1{}+ 1 で、余りは 11 です。

よって、n2n^2 を 33 で割った余りは 0 か 1‾\underline{0 \ \text{か} \ 1} です。（証明終）

(2) (1) より、n2n^2=3l{}= 3l または n2n^2=3l{}= 3l+1{}+ 1（ll は整数）と書けます。このとき n2n^2+1{}+ 1=3l{}= 3l+1{}+ 1 または 3l3l+2{}+ 2 で、33 で割った余りは 11 か 22 です。余りが 00 になることはないので、n2n^2+1{}+ 1 は 33 の倍数ではありません。（証明終）

余りだけで計算する

2つの整数の和や積を mm で割った余りは、それぞれの余りさえ分かれば求められます。

公式2：余りの計算

aa を mm で割った余りを rr、bb を mm で割った余りを ss とする。このとき

  • aa+b{}+ b を mm で割った余りは、rr+s{}+ s を mm で割った余りに等しい
  • aa−b{}- b を mm で割った余りは、rr−s{}- s を mm で割った余りに等しい
  • abab を mm で割った余りは、rsrs を mm で割った余りに等しい
  • ana^n を mm で割った余りは、rnr^n を mm で割った余りに等しい（nn は自然数）

積で理由を確かめます。aa=mp{}= mp+r{}+ r，bb=mq{}= mq+s{}+ s とおくと

ab\displaystyle ab=(mp+r)(mq+s)\displaystyle {}= (mp + r)(mq + s)=m(mpq+ps+qr)\displaystyle {}= m(mpq + ps + qr)+rs\displaystyle {}+ rs

です。abab と rsrs の差は mm の倍数なので、abab を mm で割った余りと rsrs を mm で割った余りは同じになります（ある数に mm の倍数を足しても、mm で割った余りは変わりません）。和と差も同じように示せて、累乗は積のくり返しです。

rr−s{}- s が負になったときは、mm を足して 00 以上にそろえます。たとえば mm=7{}= 7，rr=2{}= 2，ss=5{}= 5 なら rr−s{}- s=−3{}= -3 で、−3-3+7{}+ 7=4{}= 4 が aa−b{}- b を 77 で割った余りです。

下1けたしか表示されない、こわれた電卓を想像してください。38×4738 \times 47 と打つと、画面には 66 とだけ出ます。この 66 は、8×78 \times 7=56{}= 56 の下1けたと同じです。3838 の 33 や 4747 の 44 をどう変えても、表示は 66 のまま動きません。下1けたとは「1010 で割った余り」のことなので、この電卓は mm=10{}= 10 の公式2 をそのまま実演しているのです。

和・差・積・累乗を mm で割った余りは、もとの数の余りだけで決まるので、大きな数は先に余りに置きかえてから計算してよいということです。

例題2：余りから余りを求める

aa を 77 で割ると 55 余り、bb を 77 で割ると 44 余る。次の数を 77 で割った余りを求めなさい。

(1) aa+b{}+ b　　(2) aa−b{}- b　　(3) abab　　(4) a2a^2

【解答】

公式2 を使い、余り 55 と 44 で計算します。

(1) 55+4{}+ 4=9{}= 9=7⋅1{}= 7 \cdot 1+2{}+ 2 なので、余りは 2‾\underline{2} です。

(2) 55−4{}- 4=1{}= 1 なので、余りは 1‾\underline{1} です。

(3) 5×45 \times 4=20{}= 20=7⋅2{}= 7 \cdot 2+6{}+ 6 なので、余りは 6‾\underline{6} です。

念のため式でも確かめます。aa=7p{}= 7p+5{}+ 5，bb=7q{}= 7q+4{}+ 4 とおくと

ab\displaystyle ab=49pq\displaystyle {}= 49pq+28p\displaystyle {}+ 28p+35q\displaystyle {}+ 35q+20\displaystyle {}+ 20=7(7pq+4p+5q+2)\displaystyle {}= 7(7pq + 4p + 5q + 2)+6\displaystyle {}+ 6

で、確かに余りは 66 です。

(4) 525^2=25{}= 25=7⋅3{}= 7 \cdot 3+4{}+ 4 なので、余りは 4‾\underline{4} です。

合同式

公式2 のように「aa を mm で割った余りは……」と毎回書くのは大変です。そこで、余りが等しいことを表す記号を用意します。

公式3：合同式

mm を正の整数とする。aa−b{}- b が mm の倍数であるとき

a\displaystyle a≡b(modm)\displaystyle {}\equiv b \pmod{m}

と書き、「mm を法として aa と bb は合同である」という。このような式を合同式という。

aa≡b(modm){}\equiv b \pmod{m} であることと、aa と bb を mm で割った余りが等しいことは同じである。

記号 ≡\equiv は「合同」、mod\mathrm{mod} は「法」を意味する英語 modulus の略で、「モッド」と読みます。たとえば

17\displaystyle 17≡2(mod5),\displaystyle {}\equiv 2 \pmod{5},−3\displaystyle {}\qquad -3≡4(mod7),\displaystyle {}\equiv 4 \pmod{7},100\displaystyle 100≡0(mod4)\displaystyle {}\equiv 0 \pmod{4}

です。1717−2{}- 2=15{}= 15，−3-3−4{}- 4=−7{}= -7，100100−0{}- 0=100{}= 100 がそれぞれ 55，77，44 の倍数になっています。

「差が mm の倍数」と「余りが等しい」が同じになる理由を見ておきます。aa=mp{}= mp+r{}+ r，bb=mq{}= mq+s{}+ s（00≦r,{}\leqq r,ss<m{}< m）とすると

a\displaystyle a−b\displaystyle {}- b=m(p−q)\displaystyle {}= m(p - q)+(r−s)\displaystyle {}+ (r - s)

です。aa−b{}- b が mm の倍数であることは、rr−s{}- s が mm の倍数であることと同じです。ところが −m-m<r{}< r−s{}- s<m{}< m なので、rr−s{}- s が mm の倍数になるのは rr−s{}- s=0{}= 0 のときだけです。つまり rr=s{}= s です。

とくに、aa を mm で割った余りが rr であることは、aa≡r(modm){}\equiv r \pmod{m}（00≦r{}\leqq r<m{}< m）と書けます。

Aさん、Bさん、Cさん、Dさん、Eさんの 55 人が、11 日目から順に 11 人ずつ掃除当番を回すとします。66 日目はまたAさんです。33 日目と 1818 日目の当番は、どちらもCさんです。1818−3{}- 3=15{}= 15 が 55 の倍数なので、当番表のうえでは 33 日目と 1818 日目は「同じ日」とみなせます。これを 1818≡3(mod5){}\equiv 3 \pmod{5} と書くのが合同式です。当番表が気にしているのは「何日目か」ではなく「誰の番か」だけで、合同式もまた、数そのものではなく「mm で割った余り」だけを見ています。

aa≡b(modm){}\equiv b \pmod{m} は「aa−b{}- b が mm の倍数」、言いかえれば「aa と bb は mm で割った余りが同じ」という関係を短く書いたものだということです。

例題3：合同式の意味

(1) 次の ①〜④ のうち、正しい合同式をすべて求めなさい。

① 2323≡2(mod7){}\equiv 2 \pmod{7}　② 4545≡−5(mod10){}\equiv -5 \pmod{10}　③ 100100≡1(mod9){}\equiv 1 \pmod{9}　④ −8-8≡3(mod6){}\equiv 3 \pmod{6}

(2) xx≡3(mod5){}\equiv 3 \pmod{5} を満たす整数 xx のうち、2020 以上 4040 以下のものをすべて求めなさい。

【解答】

(1) 左辺から右辺を引いて、法の倍数かどうかを調べます。

  • ① 2323−2{}- 2=21{}= 21=7×3{}= 7 \times 3 で、正しい。
  • ② 4545−(−5){}- (-5)=50{}= 50=10×5{}= 10 \times 5 で、正しい。
  • ③ 100100−1{}- 1=99{}= 99=9×11{}= 9 \times 11 で、正しい。
  • ④ −8-8−3{}- 3=−11{}= -11 は 66 の倍数でないので、正しくない。

よって正しいものは ①，②，③ です。

(2) xx≡3(mod5){}\equiv 3 \pmod{5} は、xx を 55 で割った余りが 33、つまり xx=5k{}= 5k+3{}+ 3 と書けることです。2020≦5k{}\leqq 5k+3{}+ 3≦40{}\leqq 40 より kk=4,{}= 4, 5,\ 5, 6,\ 6, 7\ 7 なので

x\displaystyle x=23,‾\displaystyle {}= \underline{\rule[-0.1944em]{0em}{0.8389em}23,} 28,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 28,} 33,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 33,} 38‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 38}

です。

合同式の計算

合同式の便利なところは、ふつうの等式とほとんど同じように計算できることです。

公式4：合同式の性質

aa≡b(modm){}\equiv b \pmod{m}，cc≡d(modm){}\equiv d \pmod{m} のとき

a\displaystyle a+c\displaystyle {}+ c≡b\displaystyle {}\equiv b+d,\displaystyle {}+ d,a\displaystyle a−c\displaystyle {}- c≡b\displaystyle {}\equiv b−d,\displaystyle {}- d,ac\displaystyle ac≡bd(modm)\displaystyle {}\equiv bd \pmod{m}

が成り立つ。とくに、自然数 nn に対して ana^n≡bn(modm){}\equiv b^n \pmod{m} である。

ただし、両辺を同じ数で割ることは、一般にはできない。

これは公式2 を合同式で言いかえたものです。積については

ac\displaystyle ac−bd\displaystyle {}- bd=a(c−d)\displaystyle {}= a(c - d)+d(a−b)\displaystyle {}+ d(a - b)

と変形すると、cc−d{}- d と aa−b{}- b がどちらも mm の倍数なので、acac−bd{}- bd も mm の倍数だと分かります。

この性質から、計算の途中で、どの数も合同な別の数に取りかえてよいことになります。取りかえるなら、小さい数や負の数が便利です。77 を法とすれば 3838≡3{}\equiv 3，4545≡3{}\equiv 3 で、66≡−1{}\equiv -1 のように負の数にするとさらに楽になることもあります。

割り算に注意が必要なのは、次の例で分かります。

2×3\displaystyle 2 \times 3≡2×8(mod10)\displaystyle {}\equiv 2 \times 8 \pmod{10}

は正しい（66 と 1616 の差は 1010）のに、両辺を 22 で割った 33≡8(mod10){}\equiv 8 \pmod{10} は正しくありません。割る数と法が互いに素なら、割ってもかまいません（厳密定義 定理3）。そうでないときは、法も一緒に割る必要があります（公式6 と例題6(2)）。

先ほどの掃除当番で、「1818 日目の 44 日後の当番は誰か」と聞かれたら、1818 日目を 33 日目に置きかえて「33 日目の 44 日後」＝ 77 日目、さらに 77≡2(mod5){}\equiv 2 \pmod{5} で 22 日目のBさん、と答えられます。途中で何度「同じ日」に置きかえても、答えは変わりません。公式4 は、この置きかえが足し算だけでなく掛け算でも許されることを保証しています。

合同式では、足し算・引き算・掛け算・累乗の途中で数を合同な数に取りかえてよいが、割り算だけは自由にはできないということです。

例題4：合同式を使った計算

次の数を 77 で割った余りを求めなさい。

(1) 38×4538 \times 45+62{}+ 62　　(2) 29229^2+303{}+ 30^3

【解答】

(1) 77 を法として 3838≡3{}\equiv 3，4545≡3{}\equiv 3，6262≡6{}\equiv 6≡−1{}\equiv -1 なので

38×45\displaystyle 38 \times 45+62\displaystyle {}+ 62≡3×3\displaystyle {}\equiv 3 \times 3+(−1)\displaystyle {}+ (-1)=8\displaystyle {}= 8≡1(mod7)\displaystyle {}\equiv 1 \pmod{7}

よって、余りは 1‾\underline{1} です。

（別解）合同式を使わずに、公式2 で考えます。3838，4545，6262 を 77 で割った余りは 33，33，66 です。積 38×4538 \times 45 の余りは 3×33 \times 3=9{}= 9 の余りで 22、これに 6262 を足した余りは 22+6{}+ 6=8{}= 8 の余りで 11 です。

(2) 2929=28{}= 28+1{}+ 1，3030=28{}= 28+2{}+ 2 なので、2929≡1{}\equiv 1，3030≡2(mod7){}\equiv 2 \pmod{7} です。

292\displaystyle 29^2+303\displaystyle {}+ 30^3≡12\displaystyle {}\equiv 1^2+23\displaystyle {}+ 2^3=9\displaystyle {}= 9≡2(mod7)\displaystyle {}\equiv 2 \pmod{7}

よって、余りは 2‾\underline{2} です。

倍数の判定法を合同式で見直す

第1章で学んだ倍数の判定法は、合同式を使うと1行で説明できます。

1010≡1(mod9){}\equiv 1 \pmod{9} なので、公式4 より 10i10^i≡1i{}\equiv 1^i=1(mod9){}= 1 \pmod{9} です。44 けたの数 NN=1000a{}= 1000a+100b{}+ 100b+10c{}+ 10c+d{}+ d なら

N\displaystyle N≡a\displaystyle {}\equiv a+b\displaystyle {}+ b+c\displaystyle {}+ c+d(mod9)\displaystyle {}+ d \pmod{9}

となり、「NN と各位の数字の和は、99 で割った余りが等しい」ことが分かります。99 の倍数の判定法（第1章 公式2）はそのまま出てきますし、それどころか余りそのものも各位の数字の和から求められます。33 についても 1010≡1(mod3){}\equiv 1 \pmod{3} なので同じです。

1111 では 1010≡−1(mod11){}\equiv -1 \pmod{11} を使います。10i10^i≡(−1)i{}\equiv (-1)^i なので

N\displaystyle N≡d\displaystyle {}\equiv d−c\displaystyle {}- c+b\displaystyle {}+ b−a(mod11)\displaystyle {}- a \pmod{11}

で、一の位から交互に足し引きした値で 1111 の倍数が判定できます（第1章 実践問題 j10）。第4章の厳密定義 定理3 で扱った「nn 進法での nn−1{}- 1 と nn+1{}+ 1 の倍数の判定」も、nn≡1(modn−1){}\equiv 1 \pmod{n - 1}，nn≡−1(modn+1){}\equiv -1 \pmod{n + 1} の2つの式から同じように導けます。第1章の小話で紹介した 77・1111・1313 の判定法は、10001000≡−1(mod1001){}\equiv -1 \pmod{1001} を使ったものです。

倍数の判定法は、「1010 が法に対して 11 か −1-1 と合同である」という1つの事実から、合同式でまとめて説明できるということです。

累乗の余り

31003^{100} を 77 で割った余りは、31003^{100} を計算しなくても求められます。

公式5：累乗の余りの求め方

ana^n を mm で割った余りを求めるには、

  1. aka^k≡1{}\equiv 1 または aka^k≡−1(modm){}\equiv -1 \pmod{m} となる自然数 kk を見つける。
  2. nn=kq{}= kq+r{}+ r（00≦r{}\leqq r<k{}< k）と割り算し、ana^n=(ak)q⋅ar{}= (a^k)^q \cdot a^r と変形する。
  3. aka^k を 11 または −1-1 に置きかえて計算する。

33 の累乗を 77 で割った余りを並べてみます。次の余りは、前の余りに 33 を掛けて 77 で割った余りなので、順に

n12345678余り32645132\begin{array}{c|cccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \hline \text{余り} & 3 & 2 & 6 & 4 & 5 & 1 & 3 & 2 \end{array}

となります。363^6≡1{}\equiv 1 になったところで、そのあとは 3,3, 2,\ 2, 6,\ 6, 4,\ 4, 5,\ 5, 1\ 1 のくり返しです。余りは 77 通りしかないので、累乗の余りはいつか必ずくり返しに入ります。途中の 333^3≡6{}\equiv 6≡−1{}\equiv -1 も見のがせません。−1-1 が見つかれば、その 22 倍の kk で 11 になります。

回転ずしのレーンで、皿が 66 分でちょうど1周するとします。今目の前にある皿が 100100 分後にどこにあるかは、100100=6×16{}= 6 \times 16+4{}+ 4 なので「44 分後の位置」と同じです。1616 周分は、何度回っても元の場所に戻るだけなので無視できます。公式5 の aka^k≡1{}\equiv 1 は「11 周して元に戻る」ことにあたり、指数を kk で割った余りだけを見ればよいのです。

累乗の余りは、11 か −1-1 と合同になる累乗を見つけ、指数をその周期で割った余りに縮めて求めるということです。

例題5：累乗の余り

(1) 31003^{100} を 77 で割った余りを求めなさい。

(2) 135013^{50} の一の位の数字を求めなさい。

【解答】

(1) 333^3=27{}= 27=28{}= 28−1{}- 1 なので 333^3≡−1(mod7){}\equiv -1 \pmod{7} です。100100=3×33{}= 3 \times 33+1{}+ 1 より

3100\displaystyle 3^{100}=(33)33⋅3\displaystyle {}= (3^3)^{33} \cdot 3≡(−1)33⋅3\displaystyle {}\equiv (-1)^{33} \cdot 3=−3\displaystyle {}= -3≡4(mod7)\displaystyle {}\equiv 4 \pmod{7}

よって、余りは 4‾\underline{4} です。

（別解）合同式を使わない方法です。3993^{99}=(33)33{}= (3^3)^{33}=(28−1)33{}= (28 - 1)^{33} を二項定理（数と式 第7章）で展開すると、最後の項 (−1)33(-1)^{33}=−1{}= -1 以外はすべて 2828 の倍数、したがって 77 の倍数です。よって 3993^{99}=7M{}= 7M−1{}- 1（MM は整数）と書けて

3100\displaystyle 3^{100}=3(7M−1)\displaystyle {}= 3(7M - 1)=7⋅3M\displaystyle {}= 7 \cdot 3M−3\displaystyle {}- 3=7(3M−1)\displaystyle {}= 7(3M - 1)+4\displaystyle {}+ 4

となり、余りは 44 です。

(2) 一の位の数字は 1010 で割った余りです。1313≡3(mod10){}\equiv 3 \pmod{10} で、343^4=81{}= 81≡1(mod10){}\equiv 1 \pmod{10} です。5050=4×12{}= 4 \times 12+2{}+ 2 より

1350\displaystyle 13^{50}≡350\displaystyle {}\equiv 3^{50}=(34)12⋅32\displaystyle {}= (3^4)^{12} \cdot 3^2≡112⋅9\displaystyle {}\equiv 1^{12} \cdot 9=9(mod10)\displaystyle {}= 9 \pmod{10}

よって、一の位の数字は 9‾\underline{9} です。

余りについての方程式

最後に、「33 倍して 77 で割ると 55 余る数は何か」のような、合同式の方程式を考えます。

公式6：一次合同式の解き方

xx についての合同式 axax≡b(modm){}\equiv b \pmod{m} を一次合同式という。

  • aa と mm が互いに素のとき、00≦x{}\leqq x≦m{}\leqq m−1{}- 1 の範囲に解がただ1つ x0x_0 あり、解の全体は xx≡x0(modm){}\equiv x_0 \pmod{m} である。
  • 解くには、00 から mm−1{}- 1 までを代入して調べるか、aa′aa'≡1(modm){}\equiv 1 \pmod{m} となる a′a' を見つけて両辺に掛ける。一次不定方程式 axax−my{}- my=b{}= b（第3章）として解いてもよい。
  • aa と mm の最大公約数 gg が 22 以上のときは、bb が gg の倍数でなければ解はない。gg の倍数なら、aa，bb，mm をすべて gg で割ってから解く。

aa と mm が互いに素なら解がただ1つ、という理由は、第3章 実践問題 j19 で見た事実にあります。77 を法として xx=0,{}= 0, 1,\ 1, …,\ \ldots, 6\ 6 を 33 倍すると、余りは

0,\displaystyle 0, 3,\displaystyle \ 3, 6,\displaystyle \ 6, 2,\displaystyle \ 2, 5,\displaystyle \ 5, 1,\displaystyle \ 1, 4\displaystyle \ 4

となり、00 から 66 までがちょうど1回ずつ現れます。だから、どんな bb に対しても 3x3x≡b{}\equiv b となる xx がちょうど1つ見つかるのです。

「33 倍して 77 で割った余りを出す」という操作を、鍵をかけることにたとえてみます。上の並びがすべて異なるということは、鍵をかけても中身が混ざらない、つまり元に戻せるということです。その合鍵が「55 倍する」操作です。3×53 \times 5=15{}= 15≡1(mod7){}\equiv 1 \pmod{7} なので、33 倍したものを 55 倍すると 1515 倍、つまり 11 倍と同じになり、元の数に戻ります。公式6 の a′a' は、この合鍵のことです。

一次合同式は、係数と法が互いに素なら「掛けると 11 になる数」を両辺に掛けて解け、そうでないときは最大公約数で全体を割ってから解くということです。

例題6：一次合同式と連立合同式

(1) 合同式 3x3x≡5(mod7){}\equiv 5 \pmod{7} を満たす整数 xx を、77 を法として求めなさい。

(2) 合同式 4x4x≡6(mod10){}\equiv 6 \pmod{10} を満たす整数 xx を、1010 を法として求めなさい。

(3) 77 で割ると 33 余り、55 で割ると 22 余る 100100 以下の自然数をすべて求めなさい。

【解答】

(1) 3×53 \times 5=15{}= 15≡1(mod7){}\equiv 1 \pmod{7} なので、両辺に 55 を掛けます。

15x\displaystyle 15x≡25(mod7),\displaystyle {}\equiv 25 \pmod{7},x\displaystyle x≡4(mod7)\displaystyle {}\equiv 4 \pmod{7}

よって x≡4(mod7)‾\underline{x \equiv 4 \pmod{7}} です。（確かめ）3×43 \times 4=12{}= 12=7{}= 7+5{}+ 5 です。

（別解）3x3x−5{}- 5 が 77 の倍数なので、3x3x−7y{}- 7y=5{}= 5 となる整数 yy があります。xx=4{}= 4，yy=1{}= 1 が1つの解で、第3章の方法で一般解を求めると xx=7t{}= 7t+4{}+ 4（tt は整数）です。

(2) 44 と 1010 の最大公約数は 22 で、66 は 22 の倍数なので解があります。4x4x−6{}- 6=10y{}= 10y となる整数 yy があり、両辺を 22 で割ると 2x2x−3{}- 3=5y{}= 5y、すなわち

2x\displaystyle 2x≡3(mod5)\displaystyle {}\equiv 3 \pmod{5}

です。法も 1010 から 55 に変わることに注意します。2×32 \times 3=6{}= 6≡1(mod5){}\equiv 1 \pmod{5} なので両辺に 33 を掛けて xx≡9{}\equiv 9≡4(mod5){}\equiv 4 \pmod{5} です。1010 を法として書き直すと

x≡4,‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}x \equiv 4,} 9(mod10)‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ 9 \pmod{10}}

です。（確かめ）4×44 \times 4=16{}= 16，4×94 \times 9=36{}= 36 で、どちらも 1010 で割ると 66 余ります。

(3) 77 で割ると 33 余るので xx=7k{}= 7k+3{}+ 3 とおけます。55 で割ると 22 余るので

7k\displaystyle 7k+3\displaystyle {}+ 3≡2(mod5)\displaystyle {}\equiv 2 \pmod{5}

です。77≡2{}\equiv 2 より 2k2k+3{}+ 3≡2{}\equiv 2、すなわち 2k2k≡−1{}\equiv -1≡4(mod5){}\equiv 4 \pmod{5} です。22 と 55 は互いに素なので両辺を 22 で割ってよく、kk≡2(mod5){}\equiv 2 \pmod{5} です。kk=5t{}= 5t+2{}+ 2 とおくと

x\displaystyle x=7(5t+2)\displaystyle {}= 7(5t + 2)+3\displaystyle {}+ 3=35t\displaystyle {}= 35t+17\displaystyle {}+ 17

です。11≦35t{}\leqq 35t+17{}+ 17≦100{}\leqq 100 を満たすのは tt=0,{}= 0, 1,\ 1, 2\ 2 なので

x\displaystyle x=17,‾\displaystyle {}= \underline{\rule[-0.1944em]{0em}{0.8389em}17,} 52,‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 52,} 87‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 87}

です。答えが 3535=7×5{}= 7 \times 5 ごとにくり返すことは、第3章 厳密定義 定理4（中国の剰余定理）で示したとおりです。

この章では、整数を余りで分類し、余りだけで計算する方法を学びました。合同式は、その計算を等式と同じ感覚で書けるようにする記号です。次の第6章では、10n10^n を割った余りのくり返しが、分数を小数に直したときの「循環」として姿を現すことを見ていきます。

基礎確認問題（全5問）

まずは公式をそのまま使う、ごく簡単な問題で確認しましょう。

問1

−17-17 を 55 で割った余りを求めなさい。

つまずいたときは：
答えを見る
答え

33（−17-17=5×(−4){}= 5 \times (-4)+3{}+ 3）

自己採点：
記録を読み込み中…

問2

77 を法として 33 と合同な数を、17,17, 23,\ 23, 38,\ 38, −4,{}\ -4, −10{}\ -10 の中からすべて求めなさい。

つまずいたときは：
答えを見る
答え

17,17, 38,\ 38, −4{}\ -4（33 との差が 14,14, 35,\ 35, −7{}\ -7 で 77 の倍数）

自己採点：
記録を読み込み中…

問3

aa を 66 で割ると 44 余り、bb を 66 で割ると 55 余る。aa+b{}+ b と abab を 66 で割った余りを、それぞれ求めなさい。

つまずいたときは：
答えを見る
答え

aa+b{}+ b は 33、abab は 22（44+5{}+ 5=9{}= 9，4×54 \times 5=20{}= 20 の余り）

自己採点：
記録を読み込み中…

問4

2102^{10} を 33 で割った余りを求めなさい。

つまずいたときは：
答えを見る
答え

11（22≡−1(mod3){}\equiv -1 \pmod{3} より 2102^{10}≡(−1)10{}\equiv (-1)^{10}=1{}= 1）

自己採点：
記録を読み込み中…

問5

2x2x≡3(mod5){}\equiv 3 \pmod{5} を満たす整数 xx を、00≦x{}\leqq x≦4{}\leqq 4 の範囲で求めなさい。

つまずいたときは：
答えを見る
答え

xx=4{}= 4（2×42 \times 4=8{}= 8≡3{}\equiv 3）

自己採点：
記録を読み込み中…

実践問題（全20問）

難易度マークは ★＝基礎、★★＝標準、★★★＝入試レベルです。★から順に取り組みましょう。

問1　★

nn を整数とするとき、n2n^2 を 55 で割った余りは 0,0, 1,\ 1, 4\ 4 のいずれかであることを示しなさい。

つまずいたときは：
答えを見る
答え

nn=5k,{}= 5k, 5k\ 5k±1,{}\pm 1, 5k\ 5k±2{}\pm 2 に分けると、n2n^2 はそれぞれ 5⋅5k25 \cdot 5k^2，5(5k2±2k)5(5k^2 \pm 2k)+1{}+ 1，5(5k2±4k)5(5k^2 \pm 4k)+4{}+ 4 となる。

解説

nn を 55 で割った余りで分類します。余りが 33，44 の場合は 5k5k−2{}- 2，5k5k−1{}- 1 と書けるので、nn は 5k5k，5k5k±1{}\pm 1，5k5k±2{}\pm 2（kk は整数、複号同順）のどれかの形に表せます。

  • nn=5k{}= 5k のとき、n2n^2=25k2{}= 25k^2=5⋅5k2{}= 5 \cdot 5k^2 で、余りは 00 です。
  • nn=5k{}= 5k±1{}\pm 1 のとき、n2n^2=25k2{}= 25k^2±10k{}\pm 10k+1{}+ 1=5(5k2±2k){}= 5(5k^2 \pm 2k)+1{}+ 1 で、余りは 11 です。
  • nn=5k{}= 5k±2{}\pm 2 のとき、n2n^2=25k2{}= 25k^2±20k{}\pm 20k+4{}+ 4=5(5k2±4k){}= 5(5k^2 \pm 4k)+4{}+ 4 で、余りは 44 です。

よって、n2n^2 を 55 で割った余りは 0,0, 1,\ 1, 4\ 4 のいずれかです。（証明終）

合同式で書くと、nn≡0,{}\equiv 0, ±1,{}\ \pm 1, ±2(mod5){}\ \pm 2 \pmod{5} に対して n2n^2≡0,{}\equiv 0, 1,\ 1, 4(mod5)\ 4 \pmod{5} となります。5k5k+3{}+ 3，5k5k+4{}+ 4 のまま計算しても同じ結論になりますが、負の形にしたほうが計算が短くなります。

自己採点：
記録を読み込み中…

問2　★

nn を整数とするとき、連続する3つの整数の積 n(n+1)(n+2)n(n + 1)(n + 2) は 66 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

連続する2つの整数の一方は偶数なので 22 の倍数、nn を 33 で割った余りで分けると3数のどれかが 33 の倍数なので 33 の倍数。22 と 33 は互いに素なので 66 の倍数。

解説

PP=n(n+1)(n+2){}= n(n + 1)(n + 2) とおきます。

22 の倍数であること　nn が偶数なら nn が、nn が奇数なら nn+1{}+ 1 が偶数です。どちらの場合も PP は偶数です。

33 の倍数であること　nn を 33 で割った余りで分類します。

  • nn=3k{}= 3k のとき、nn が 33 の倍数です。
  • nn=3k{}= 3k+1{}+ 1 のとき、nn+2{}+ 2=3k{}= 3k+3{}+ 3=3(k+1){}= 3(k + 1) が 33 の倍数です。
  • nn=3k{}= 3k+2{}+ 2 のとき、nn+1{}+ 1=3k{}= 3k+3{}+ 3=3(k+1){}= 3(k + 1) が 33 の倍数です。

どの場合も、3つの数のどれかが 33 の倍数なので、PP は 33 の倍数です。

PP は 22 の倍数かつ 33 の倍数で、22 と 33 は互いに素なので、PP は 66 の倍数です（第1章 厳密定義 定理5）。（証明終）

素因数分解の見方をすれば、PP の素因数に 22 と 33 が両方含まれるので 2⋅32 \cdot 3=6{}= 6 で割り切れる、ということです。

自己採点：
記録を読み込み中…

問3　★

aa を 88 で割ると 55 余り、bb を 88 で割ると 77 余る。

(1) aa+b{}+ b　　(2) aa−b{}- b　　(3) abab　　(4) a2a^2+b2{}+ b^2

上の (1)〜(4) を 88 で割った余りを、それぞれ求めなさい。

つまずいたときは：
答えを見る
答え

(1) 44　(2) 66　(3) 33　(4) 22

解説

公式2 により、余り 55 と 77 で計算してから 88 で割ります。

(1) 55+7{}+ 7=12{}= 12=8{}= 8+4{}+ 4 なので、余りは 4‾\underline{4} です。

(2) 55−7{}- 7=−2{}= -2 です。負になったので 88 を足して −2-2+8{}+ 8=6{}= 6、余りは 6‾\underline{6} です。実際、aa−b{}- b=(8p+5){}= (8p + 5)−(8q+7){}- (8q + 7)=8(p−q−1){}= 8(p - q - 1)+6{}+ 6 です。

(3) 5×75 \times 7=35{}= 35=8×4{}= 8 \times 4+3{}+ 3 なので、余りは 3‾\underline{3} です。

(4) 525^2+72{}+ 7^2=25{}= 25+49{}+ 49=74{}= 74=8×9{}= 8 \times 9+2{}+ 2 なので、余りは 2‾\underline{2} です。

合同式を使うなら、77≡−1(mod8){}\equiv -1 \pmod{8} として a2a^2+b2{}+ b^2≡25{}\equiv 25+1{}+ 1=26{}= 26≡2{}\equiv 2 と計算することもできます。

自己採点：
記録を読み込み中…

問4　★

(1) 1234×56781234 \times 5678　　(2) 567835678^3

上の (1)(2) を 99 で割った余りを、それぞれ求めなさい。

つまずいたときは：
答えを見る
答え

(1) 88　(2) 88

解説

1010≡1(mod9){}\equiv 1 \pmod{9} なので、整数は各位の数字の和と 99 を法として合同です（本文「倍数の判定法を合同式で見直す」）。

1234\displaystyle 1234≡1\displaystyle {}\equiv 1+2\displaystyle {}+ 2+3\displaystyle {}+ 3+4\displaystyle {}+ 4=10\displaystyle {}= 10≡1,\displaystyle {}\equiv 1,5678\displaystyle 5678≡5\displaystyle {}\equiv 5+6\displaystyle {}+ 6+7\displaystyle {}+ 7+8\displaystyle {}+ 8=26\displaystyle {}= 26≡8(mod9)\displaystyle {}\equiv 8 \pmod{9}

(1) 1234×56781234 \times 5678≡1×8{}\equiv 1 \times 8=8(mod9){}= 8 \pmod{9} なので、余りは 8‾\underline{8} です。

(2) 56785678≡8{}\equiv 8≡−1(mod9){}\equiv -1 \pmod{9} なので

56783\displaystyle 5678^3≡(−1)3\displaystyle {}\equiv (-1)^3=−1\displaystyle {}= -1≡8(mod9)\displaystyle {}\equiv 8 \pmod{9}

よって、余りは 8‾\underline{8} です。

（別解）合同式を使わずに、公式2 で考えることもできます。12341234=9×137{}= 9 \times 137+1{}+ 1，56785678=9×630{}= 9 \times 630+8{}+ 8 なので余りは 11 と 88 です。(1) は 1×81 \times 8=8{}= 8 の余りで 88、(2) は 838^3=512{}= 512=9×56{}= 9 \times 56+8{}+ 8 の余りで 88 です。

自己採点：
記録を読み込み中…

問5　★

5835^{83} を 1313 で割った余りを求めなさい。

つまずいたときは：
答えを見る
答え

88

解説

525^2=25{}= 25=26{}= 26−1{}- 1 なので、525^2≡−1(mod13){}\equiv -1 \pmod{13} です。8383=2×41{}= 2 \times 41+1{}+ 1 より

583\displaystyle 5^{83}=(52)41⋅5\displaystyle {}= (5^2)^{41} \cdot 5≡(−1)41⋅5\displaystyle {}\equiv (-1)^{41} \cdot 5=−5\displaystyle {}= -5≡8(mod13)\displaystyle {}\equiv 8 \pmod{13}

よって、余りは 8‾\underline{8} です。

（別解）5825^{82}=(26−1)41{}= (26 - 1)^{41} を二項定理で展開すると、最後の項 −1-1 以外は 2626 の倍数、したがって 1313 の倍数です。5825^{82}=13M{}= 13M−1{}- 1 とおくと、5835^{83}=5(13M−1){}= 5(13M - 1)=13(5M−1){}= 13(5M - 1)+8{}+ 8 で、余りは 88 です。

自己採点：
記録を読み込み中…

問6　★

720267^{2026} の一の位の数字を求めなさい。

つまずいたときは：
答えを見る
答え

99

解説

一の位の数字は、1010 で割った余りです。727^2=49{}= 49≡−1(mod10){}\equiv -1 \pmod{10} なので、20262026=2×1013{}= 2 \times 1013 より

72026\displaystyle 7^{2026}=(72)1013\displaystyle {}= (7^2)^{1013}≡(−1)1013\displaystyle {}\equiv (-1)^{1013}=−1\displaystyle {}= -1≡9(mod10)\displaystyle {}\equiv 9 \pmod{10}

よって、一の位の数字は 9‾\underline{9} です。

（別解）一の位だけを追うと、71,7^1, 72,\ 7^2, 73,\ 7^3, 74,\ 7^4, …\ \ldots の一の位は 7,7, 9,\ 9, 3,\ 3, 1,\ 1, 7,\ 7, 9,\ 9, …\ \ldots と 44 個ずつくり返します。20262026=4×506{}= 4 \times 506+2{}+ 2 なので、22 番目と同じ 99 です。

自己採点：
記録を読み込み中…

問7　★

合同式 5x5x≡3(mod8){}\equiv 3 \pmod{8} を満たす整数 xx を、88 を法として求めなさい。

つまずいたときは：
答えを見る
答え

xx≡7(mod8){}\equiv 7 \pmod{8}

解説

55 と 88 は互いに素なので、解は 88 を法としてただ1つです。5×55 \times 5=25{}= 25=24{}= 24+1{}+ 1≡1(mod8){}\equiv 1 \pmod{8} なので、両辺に 55 を掛けます。

25x\displaystyle 25x≡15(mod8),\displaystyle {}\equiv 15 \pmod{8},x\displaystyle x≡7(mod8)\displaystyle {}\equiv 7 \pmod{8}

よって x≡7(mod8)‾\underline{x \equiv 7 \pmod{8}} です。（確かめ）5×75 \times 7=35{}= 35=32{}= 32+3{}+ 3 です。

（別解）xx=0,{}= 0, 1,\ 1, …,\ \ldots, 7\ 7 を順に代入すると、5x5x を 88 で割った余りは 0,0, 5,\ 5, 2,\ 2, 7,\ 7, 4,\ 4, 1,\ 1, 6,\ 6, 3\ 3 で、余りが 33 になるのは xx=7{}= 7 だけです。一次不定方程式 5x5x−8y{}- 8y=3{}= 3（xx=7{}= 7，yy=4{}= 4）として解くこともできます。

自己採点：
記録を読み込み中…

問8　★

55 けたの整数 3□9723\square 972 が 1111 の倍数になるように、□\square に入る数字を定めなさい。

つまずいたときは：
答えを見る
答え

77

解説

□\square に入る数字を xx（00≦x{}\leqq x≦9{}\leqq 9）とします。1010≡−1(mod11){}\equiv -1 \pmod{11} なので、10i10^i≡(−1)i{}\equiv (-1)^i です。一の位から順に符号を交互につけて

3□972\displaystyle 3\square 972≡2\displaystyle {}\equiv 2−7\displaystyle {}- 7+9\displaystyle {}+ 9−x\displaystyle {}- x+3\displaystyle {}+ 3=7\displaystyle {}= 7−x(mod11)\displaystyle {}- x \pmod{11}

です。1111 の倍数になるのは 77−x{}- x≡0(mod11){}\equiv 0 \pmod{11} のときです。00≦x{}\leqq x≦9{}\leqq 9 より −2-2≦7{}\leqq 7−x{}- x≦7{}\leqq 7 で、この範囲にある 1111 の倍数は 00 だけなので、77−x{}- x=0{}= 0 です。よって

7‾\underline{7}

です。（確かめ）3797237972=11×3452{}= 11 \times 3452 です。

合同式を使わない場合は、1000010000=9999{}= 9999+1{}+ 1，10001000=1001{}= 1001−1{}- 1，100100=99{}= 99+1{}+ 1，1010=11{}= 11−1{}- 1 と分けて、99999999，10011001，9999，1111 がすべて 1111 の倍数であることから同じ式が得られます（第1章 実践問題 j10 の考え方）。

自己採点：
記録を読み込み中…

問9　★★

nn を整数とするとき、n(n+1)(2n+1)n(n + 1)(2n + 1) は 66 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

n(n+1)n(n+1) は偶数。nn≡0{}\equiv 0 なら nn、nn≡1{}\equiv 1 なら 2n2n+1{}+ 1、nn≡2{}\equiv 2 なら nn+1{}+ 1 が 33 の倍数（法 33）。22 と 33 は互いに素なので 66 の倍数。

解説

PP=n(n+1)(2n+1){}= n(n + 1)(2n + 1) とおきます。

22 の倍数であること　nn と nn+1{}+ 1 は連続する整数なので、どちらかが偶数です。よって PP は偶数です。

33 の倍数であること　33 を法として場合分けします。

  • nn≡0{}\equiv 0 のとき、nn が 33 の倍数です。
  • nn≡1{}\equiv 1 のとき、2n2n+1{}+ 1≡2{}\equiv 2+1{}+ 1=3{}= 3≡0{}\equiv 0 なので、2n2n+1{}+ 1 が 33 の倍数です。
  • nn≡2{}\equiv 2 のとき、nn+1{}+ 1≡3{}\equiv 3≡0{}\equiv 0 なので、nn+1{}+ 1 が 33 の倍数です。

どの場合も PP は 33 の倍数です。22 と 33 は互いに素なので、PP は 66 の倍数です。（証明終）

（別解）2n2n+1{}+ 1=(n+2){}= (n + 2)+(n−1){}+ (n - 1) と分けると

P\displaystyle P=n(n+1)(n+2)\displaystyle {}= n(n + 1)(n + 2)+(n−1)n(n+1)\displaystyle {}+ (n - 1)n(n + 1)

です。どちらの項も連続する3つの整数の積なので、実践問題 j02 より 66 の倍数です。よって PP も 66 の倍数です。

なお、n(n+1)(2n+1)6\dfrac{n(n + 1)(2n + 1)}{6} は 121^2+22{}+ 2^2+⋯{}+ \cdots+n2{}+ n^2 に等しい式で（数列の分野で学びます）、この問題はその値が整数になる理由にもなっています。

自己採点：
記録を読み込み中…

問10　★★

2n2^n+1{}+ 1 が 33 の倍数となるような自然数 nn の条件を求めなさい。

つまずいたときは：
答えを見る
答え

nn が奇数

解説

22≡−1(mod3){}\equiv -1 \pmod{3} なので

2n\displaystyle 2^n+1\displaystyle {}+ 1≡(−1)n\displaystyle {}\equiv (-1)^n+1(mod3)\displaystyle {}+ 1 \pmod{3}

です。

  • nn が奇数のとき、(−1)n(-1)^n+1{}+ 1=−1{}= -1+1{}+ 1=0{}= 0 なので、2n2^n+1{}+ 1 は 33 の倍数です。
  • nn が偶数のとき、(−1)n(-1)^n+1{}+ 1=1{}= 1+1{}+ 1=2{}= 2 なので、33 で割ると 22 余り、33 の倍数ではありません。

よって、求める条件は n が奇数‾\underline{n \ \text{が奇数}} です。

（別解）2n2^n を 33 で割った余りを並べると、2,2, 1,\ 1, 2,\ 2, 1,\ 1, …\ \ldots です（前の余りに 22 を掛けて 33 で割った余りが次の余り）。2n2^n+1{}+ 1 が 33 の倍数になるのは余りが 22 のとき、つまり nn が奇数のときです。

自己採点：
記録を読み込み中…

問11　★★

すべての自然数 nn について、32n3^{2n}−2n{}- 2^n は 77 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

32n3^{2n}=9n{}= 9^n で、99≡2(mod7){}\equiv 2 \pmod{7} より 9n9^n≡2n{}\equiv 2^n。よって 32n3^{2n}−2n{}- 2^n≡0(mod7){}\equiv 0 \pmod{7}。

解説

32n3^{2n}=(32)n{}= (3^2)^n=9n{}= 9^n です。99=7{}= 7+2{}+ 2 より 99≡2(mod7){}\equiv 2 \pmod{7} なので、公式4 により

9n\displaystyle 9^n≡2n(mod7)\displaystyle {}\equiv 2^n \pmod{7}

です。よって

32n\displaystyle 3^{2n}−2n\displaystyle {}- 2^n=9n\displaystyle {}= 9^n−2n\displaystyle {}- 2^n≡2n\displaystyle {}\equiv 2^n−2n\displaystyle {}- 2^n=0(mod7)\displaystyle {}= 0 \pmod{7}

となり、32n3^{2n}−2n{}- 2^n は 77 の倍数です。（証明終）

（別解）xnx^n−yn{}- y^n は、xx−y{}- y と xn−1x^{n-1}+xn−2y{}+ x^{n-2}y+⋯{}+ \cdots+yn−1{}+ y^{n-1} の積に因数分解できます。この等式に xx=9{}= 9，yy=2{}= 2 を代入すると

9n\displaystyle 9^n−2n\displaystyle {}- 2^n=7(9n−1+9n−2⋅2\displaystyle {}= 7(9^{n-1} + 9^{n-2} \cdot 2+⋯+2n−1)\displaystyle {}\qquad + \cdots + 2^{n-1})

で、括弧の中は整数なので 77 の倍数です。

自己採点：
記録を読み込み中…

問12　★★

合同式 9x9x≡6(mod15){}\equiv 6 \pmod{15} を満たす整数 xx を、1515 を法として求めなさい。

つまずいたときは：
答えを見る
答え

xx≡4,{}\equiv 4, 9,\ 9, 14(mod15)\ 14 \pmod{15}

解説

99 と 1515 の最大公約数は 33 で、右辺の 66 は 33 の倍数なので、解があります。

9x9x−6{}- 6=15y{}= 15y となる整数 yy があるので、両辺を 33 で割ると 3x3x−2{}- 2=5y{}= 5y、すなわち

3x\displaystyle 3x≡2(mod5)\displaystyle {}\equiv 2 \pmod{5}

です。法も 1515 から 55 に変わることに注意します。3×23 \times 2=6{}= 6≡1(mod5){}\equiv 1 \pmod{5} なので、両辺に 22 を掛けて

x\displaystyle x≡4(mod5)\displaystyle {}\equiv 4 \pmod{5}

です。xx=5t{}= 5t+4{}+ 4 のうち、1515 で割った余りが異なるのは tt=0,{}= 0, 1,\ 1, 2\ 2 の 4,4, 9,\ 9, 14\ 14 なので

x≡4,‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}x \equiv 4,} 9,‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ 9,} 14(mod15)‾\displaystyle \underline{\rule[-0.25em]{0em}{1.0000em}\ 14 \pmod{15}}

です。（確かめ）9×49 \times 4=36{}= 36，9×99 \times 9=81{}= 81，9×149 \times 14=126{}= 126 は、どれも 1515 で割ると 66 余ります。

両辺を 33 で割って 3x3x≡2(mod15){}\equiv 2 \pmod{15} としてしまうと、xx≡14(mod15){}\equiv 14 \pmod{15} しか出てこず、解を 22 つ落とします。法も一緒に割ることが大切です。

自己採点：
記録を読み込み中…

問13　★★

44 で割ると 33 余り、99 で割ると 55 余る整数のうち、100100 以上 200200 以下のものをすべて求めなさい。

つまずいたときは：
答えを見る
答え

131,131, 167\ 167

解説

99 で割ると 55 余るので、xx=9k{}= 9k+5{}+ 5（kk は整数）とおけます。44 で割ると 33 余るので

9k\displaystyle 9k+5\displaystyle {}+ 5≡3(mod4)\displaystyle {}\equiv 3 \pmod{4}

です。99≡1{}\equiv 1，55≡1{}\equiv 1 より kk+1{}+ 1≡3{}\equiv 3、すなわち kk≡2(mod4){}\equiv 2 \pmod{4} です。kk=4t{}= 4t+2{}+ 2 とおくと

x\displaystyle x=9(4t+2)\displaystyle {}= 9(4t + 2)+5\displaystyle {}+ 5=36t\displaystyle {}= 36t+23\displaystyle {}+ 23

です。100100≦36t{}\leqq 36t+23{}+ 23≦200{}\leqq 200 より 7777≦36t{}\leqq 36t≦177{}\leqq 177 で、これを満たす整数は tt=3,{}= 3, 4\ 4 です。よって

x\displaystyle x=131,‾\displaystyle {}= \underline{\rule[-0.1944em]{0em}{0.8389em}131,} 167‾\displaystyle \underline{\rule[-0.1944em]{0em}{0.8389em}\ 167}

です。（確かめ）131131=4×32{}= 4 \times 32+3{}+ 3=9×14{}= 9 \times 14+5{}+ 5，167167=4×41{}= 4 \times 41+3{}+ 3=9×18{}= 9 \times 18+5{}+ 5 です。

（別解）xx=4a{}= 4a+3{}+ 3=9b{}= 9b+5{}+ 5 とおくと、一次不定方程式 4a4a−9b{}- 9b=2{}= 2 になります。aa=5{}= 5，bb=2{}= 2 が1つの解で、一般解は aa=9t{}= 9t+5{}+ 5 なので xx=4(9t+5){}= 4(9t + 5)+3{}+ 3=36t{}= 36t+23{}+ 23 です（第3章の方法）。

自己採点：
記録を読み込み中…

問14　★★

方程式 x2x^2−3y2{}- 3y^2=2{}= 2 を満たす整数 xx，yy は存在しないことを示しなさい。

つまずいたときは：
答えを見る
答え

33 を法とすると x2x^2≡2{}\equiv 2 となるが、平方数を 33 で割った余りは 00 か 11 なので矛盾する。

解説

整数 xx，yy が x2x^2−3y2{}- 3y^2=2{}= 2 を満たすと仮定します。3y23y^2 は 33 の倍数なので、33 を法として

x2\displaystyle x^2≡2(mod3)\displaystyle {}\equiv 2 \pmod{3}

となります。つまり x2x^2 を 33 で割った余りが 22 です。

ところが、例題1(1) で示したとおり、平方数を 33 で割った余りは 00 か 11 で、22 になることはありません。これは矛盾です。

よって、方程式を満たす整数 xx，yy は存在しません。（証明終）

このように、方程式の両辺を適当な数で割った余りを比べると、「整数解がない」ことを短く示せることがあります。どの数を法に選ぶかがポイントで、ここでは 3y23y^2 を消すために 33 を選びました。

自己採点：
記録を読み込み中…

問15　★★

33+32{}+ 3^2+33{}+ 3^3+⋯{}+ \cdots+32026{}+ 3^{2026} の一の位の数字を求めなさい。

つまずいたときは：
答えを見る
答え

22

解説

一の位の数字は 1010 で割った余りなので、1010 を法として考えます。343^4=81{}= 81≡1(mod10){}\equiv 1 \pmod{10} なので、3k3^k の余りは

3,\displaystyle 3, 9,\displaystyle \ 9, 7,\displaystyle \ 7, 1,\displaystyle \ 1, 3,\displaystyle \ 3, 9,\displaystyle \ 9, 7,\displaystyle \ 7, 1,\displaystyle \ 1, …\displaystyle \ \ldots

と 44 個ずつくり返します。連続する 44 項 34j+13^{4j+1}+34j+2{}+ 3^{4j+2}+34j+3{}+ 3^{4j+3}+34j+4{}+ 3^{4j+4} は

34j+1\displaystyle 3^{4j+1}+34j+2\displaystyle {}+ 3^{4j+2}+34j+3\displaystyle {}+ 3^{4j+3}+34j+4\displaystyle {}+ 3^{4j+4}≡3\displaystyle {}\equiv 3+9\displaystyle {}+ 9+7\displaystyle {}+ 7+1\displaystyle {}+ 1=20\displaystyle {}= 20≡0(mod10)\displaystyle {}\equiv 0 \pmod{10}

です。20262026=4×506{}= 4 \times 506+2{}+ 2 なので、和は「44 項ずつの組が 506506 組」と、残りの 320253^{2025}+32026{}+ 3^{2026} に分けられます。残りの2項は 320253^{2025}≡3{}\equiv 3，320263^{2026}≡9{}\equiv 9 なので

3\displaystyle 3+32\displaystyle {}+ 3^2+⋯\displaystyle {}+ \cdots+32026\displaystyle {}+ 3^{2026}≡506×0\displaystyle {}\equiv 506 \times 0+3\displaystyle {}+ 3+9\displaystyle {}+ 9=12\displaystyle {}= 12≡2(mod10)\displaystyle {}\equiv 2 \pmod{10}

よって、一の位の数字は 2‾\underline{2} です。

自己採点：
記録を読み込み中…

問16　★★

71237^{123} を 100100 で割った余りを求めなさい。

つまずいたときは：
答えを見る
答え

4343

解説

100100 で割った余りは、下2けたの数です。727^2=49{}= 49，747^4=492{}= 49^2=2401{}= 2401 なので

74\displaystyle 7^4≡1(mod100)\displaystyle {}\equiv 1 \pmod{100}

です。123123=4×30{}= 4 \times 30+3{}+ 3 より

7123\displaystyle 7^{123}=(74)30⋅73\displaystyle {}= (7^4)^{30} \cdot 7^3≡130⋅343\displaystyle {}\equiv 1^{30} \cdot 343≡43(mod100)\displaystyle {}\equiv 43 \pmod{100}

よって、余りは 43‾\underline{43} です。

（別解）747^4=2401{}= 2401=2400{}= 2400+1{}+ 1 なので、(74)30(7^4)^{30}=(2400+1)30{}= (2400 + 1)^{30} を二項定理で展開すると、最後の項 11 以外は 24002400 の倍数、したがって 100100 の倍数です。(74)30(7^4)^{30}=100M{}= 100M+1{}+ 1 とおくと、71237^{123}=343(100M+1){}= 343(100M + 1)=100⋅343M{}= 100 \cdot 343M+343{}+ 343 で、343343=100×3{}= 100 \times 3+43{}+ 43 より余りは 4343 です。

自己採点：
記録を読み込み中…

問17　★★★

nn を整数とするとき、n5n^5−n{}- n は 3030 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

n5n^5−n{}- n を因数分解すると (n−1)n(n+1)(n2+1)(n - 1)n(n + 1)(n^2 + 1)。連続3整数の積で 66 の倍数。nn≡0,{}\equiv 0, ±1(mod5){}\ \pm 1 \pmod{5} なら nn か nn∓1{}\mp 1 が、nn≡±2{}\equiv \pm 2 なら n2n^2+1{}+ 1 が 55 の倍数。66 と 55 は互いに素なので 3030 の倍数。

解説

まず因数分解します。

n5\displaystyle n^5−n\displaystyle {}- n=n(n4−1)\displaystyle {}= n(n^4 - 1)=n(n2−1)(n2+1)\displaystyle {}= n(n^2 - 1)(n^2 + 1)=(n−1)n(n+1)(n2+1)\displaystyle {}= (n - 1)n(n + 1)(n^2 + 1)

66 の倍数であること　(n−1)n(n+1)(n - 1)n(n + 1) は連続する3つの整数の積なので、実践問題 j02 より 66 の倍数です。したがって n5n^5−n{}- n も 66 の倍数です。

55 の倍数であること　55 を法として場合分けします。

  • nn≡0{}\equiv 0 のとき、nn が 55 の倍数です。
  • nn≡1{}\equiv 1 のとき nn−1{}- 1 が、nn≡−1{}\equiv -1 のとき nn+1{}+ 1 が 55 の倍数です。
  • nn≡±2{}\equiv \pm 2 のとき、n2n^2+1{}+ 1≡4{}\equiv 4+1{}+ 1=5{}= 5≡0{}\equiv 0 なので、n2n^2+1{}+ 1 が 55 の倍数です。

どの場合も n5n^5−n{}- n は 55 の倍数です。

n5n^5−n{}- n は 66 の倍数かつ 55 の倍数で、66 と 55 は互いに素なので、3030 の倍数です。（証明終）

55 の倍数であることは、「n5n^5≡n(mod5){}\equiv n \pmod{5}」とも書けます。これは厳密定義で扱うフェルマーの小定理の pp=5{}= 5 の場合です。

自己採点：
記録を読み込み中…

問18　★★★

自然数 aa，bb，cc が a2a^2+b2{}+ b^2=c2{}= c^2 を満たしている。

(1) aa，bb の少なくとも一方は 33 の倍数であることを示しなさい。

(2) aa，bb，cc の少なくとも1つは 55 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

(1) どちらも 33 の倍数でないと a2a^2+b2{}+ b^2≡2(mod3){}\equiv 2 \pmod{3} だが、c2c^2≡0,{}\equiv 0, 1\ 1 で矛盾。　(2) どれも 55 の倍数でないと a2,a^2, b2,\ b^2, c2\ c^2≡1{}\equiv 1 か 4(mod5)4 \pmod{5} で、a2a^2+b2{}+ b^2≡2,{}\equiv 2, 0,\ 0, 3\ 3 となり c2c^2 と一致しない。

解説

背理法で示します。

(1) aa，bb がどちらも 33 の倍数でないと仮定します。33 の倍数でない数の平方を 33 で割った余りは 11 です（例題1(1) の nn=3k{}= 3k±1{}\pm 1 の場合）。よって

c2\displaystyle c^2=a2\displaystyle {}= a^2+b2\displaystyle {}+ b^2≡1\displaystyle {}\equiv 1+1\displaystyle {}+ 1=2(mod3)\displaystyle {}= 2 \pmod{3}

となります。ところが平方数を 33 で割った余りは 00 か 11 なので、これは矛盾です。よって、aa，bb の少なくとも一方は 33 の倍数です。（証明終）

(2) aa，bb，cc のどれも 55 の倍数でないと仮定します。実践問題 j01 より、55 の倍数でない数の平方を 55 で割った余りは 11 か 44 です。a2a^2+b2{}+ b^2 を 55 で割った余りは、a2a^2，b2b^2 の余りの組み合わせで

1\displaystyle 1+1\displaystyle {}+ 1=2,\displaystyle {}= 2,1\displaystyle 1+4\displaystyle {}+ 4=5\displaystyle {}= 5≡0,\displaystyle {}\equiv 0,4\displaystyle 4+4\displaystyle {}+ 4=8\displaystyle {}= 8≡3\displaystyle {}\equiv 3

のどれかで、22，00，33 のいずれかです。一方、c2c^2 を 55 で割った余りは 11 か 44 なので、a2a^2+b2{}+ b^2=c2{}= c^2 に矛盾します。よって、aa，bb，cc の少なくとも1つは 55 の倍数です。（証明終）

実際、(3, 4, 5)(3,\ 4,\ 5)，(5, 12, 13)(5,\ 12,\ 13)，(8, 15, 17)(8,\ 15,\ 17)，(7, 24, 25)(7,\ 24,\ 25) などで確かめられます。(8, 15, 17)(8,\ 15,\ 17) では、33 の倍数も 55 の倍数も 1515 が引き受けています。

自己採点：
記録を読み込み中…

問19　★★★

すべての自然数 nn について、11n+111^{n+1}+122n−1{}+ 12^{2n-1} は 133133 の倍数であることを示しなさい。

つまずいたときは：
答えを見る
答え

12212^2=144{}= 144≡11(mod133){}\equiv 11 \pmod{133} より 122n−112^{2n-1}=12⋅144n−1{}= 12 \cdot 144^{n-1}≡12⋅11n−1{}\equiv 12 \cdot 11^{n-1}。11n+111^{n+1}=121⋅11n−1{}= 121 \cdot 11^{n-1} なので、和 ≡133⋅11n−1\equiv 133 \cdot 11^{n-1}≡0{}\equiv 0。

解説

133133 を法として考えます。12212^2=144{}= 144=133{}= 133+11{}+ 11 なので

122\displaystyle 12^2≡11(mod133)\displaystyle {}\equiv 11 \pmod{133}

です。これを使って、2つの項を 11n−111^{n-1} でそろえます。

122n−1\displaystyle 12^{2n-1}=12⋅(122)n−1\displaystyle {}= 12 \cdot (12^2)^{n-1}≡12⋅11n−1(mod133)\displaystyle {}\equiv 12 \cdot 11^{n-1} \pmod{133} 11n+1\displaystyle 11^{n+1}=112⋅11n−1\displaystyle {}= 11^2 \cdot 11^{n-1}=121⋅11n−1\displaystyle {}= 121 \cdot 11^{n-1}

よって

11n+1\displaystyle 11^{n+1}+122n−1\displaystyle {}+ 12^{2n-1}≡(121+12)⋅11n−1\displaystyle {}\equiv (121 + 12) \cdot 11^{n-1}=133⋅11n−1\displaystyle {}= 133 \cdot 11^{n-1}≡0(mod133)\displaystyle {}\equiv 0 \pmod{133}

となり、133133 の倍数です。（証明終）

（別解）AnA_n=11n+1{}= 11^{n+1}+122n−1{}+ 12^{2n-1} とおきます。A1A_1=121{}= 121+12{}+ 12=133{}= 133 です。また

An+1\displaystyle A_{n+1}=11⋅11n+1\displaystyle {}= 11 \cdot 11^{n+1}+144⋅122n−1\displaystyle {}+ 144 \cdot 12^{2n-1}=11An\displaystyle {}= 11A_n+(144−11)⋅122n−1\displaystyle {}+ (144 - 11) \cdot 12^{2n-1}=11An\displaystyle {}= 11A_n+133⋅122n−1\displaystyle {}+ 133 \cdot 12^{2n-1}

なので、AnA_n が 133133 の倍数なら An+1A_{n+1} も 133133 の倍数です。A1A_1 から順にたどれば、すべての AnA_n が 133133 の倍数だと分かります（この論法は、数列の分野で数学的帰納法として整理されます）。

どちらの解き方でも、144144−11{}- 11=133{}= 133 という関係が鍵になっています。

自己採点：
記録を読み込み中…

問20　★★★

nn を自然数とする。

(1) n2n^2+n{}+ n+1{}+ 1 が 77 の倍数となるような nn を 77 で割った余りを、すべて求めなさい。

(2) n2n^2+n{}+ n+1{}+ 1 が 4949 の倍数となるような最小の nn を求めなさい。

つまずいたときは：
答えを見る
答え

(1) 2,2, 4\ 4　(2) nn=18{}= 18

解説

(1) nn≡0,{}\equiv 0, 1,\ 1, …,\ \ldots, 6(mod7)\ 6 \pmod{7} のそれぞれについて、n2n^2+n{}+ n+1{}+ 1 を 77 を法として計算します。

nnn2+n+1n^2 + n + 177 で割った余り
001111
113333
227700
33131366
44212100
55313133
66434311

余りが 00 になるのは nn≡2,{}\equiv 2, 4\ 4 のときなので、求める余りは 2,‾\underline{\rule[-0.1944em]{0em}{0.8389em}2,} 4‾\underline{\rule[-0.1944em]{0em}{0.8389em}\ 4} です。

(2) 4949 の倍数なら 77 の倍数でもあるので、(1) より nn=7k{}= 7k+2{}+ 2 または nn=7k{}= 7k+4{}+ 4（kk は 00 以上の整数）です。

nn=7k{}= 7k+2{}+ 2 のとき

n2\displaystyle n^2+n\displaystyle {}+ n+1\displaystyle {}+ 1=49k2\displaystyle {}= 49k^2+28k\displaystyle {}+ 28k+4\displaystyle {}+ 4+7k\displaystyle {}+ 7k+2\displaystyle {}+ 2+1\displaystyle {}+ 1=7(7k2+5k+1)\displaystyle {}= 7(7k^2 + 5k + 1)

4949 の倍数になるのは 7k27k^2+5k{}+ 5k+1{}+ 1 が 77 の倍数のとき、つまり 5k5k+1{}+ 1≡0(mod7){}\equiv 0 \pmod{7} のときです。5k5k≡−1{}\equiv -1≡6{}\equiv 6 で、5×35 \times 3=15{}= 15≡1{}\equiv 1 なので両辺に 33 を掛けて kk≡18{}\equiv 18≡4(mod7){}\equiv 4 \pmod{7} です。最小の kk は 44 で、nn=30{}= 30 です。

nn=7k{}= 7k+4{}+ 4 のとき

n2\displaystyle n^2+n\displaystyle {}+ n+1\displaystyle {}+ 1=49k2\displaystyle {}= 49k^2+56k\displaystyle {}+ 56k+16\displaystyle {}+ 16+7k\displaystyle {}+ 7k+4\displaystyle {}+ 4+1\displaystyle {}+ 1=7(7k2+9k+3)\displaystyle {}= 7(7k^2 + 9k + 3)

9k9k+3{}+ 3≡0(mod7){}\equiv 0 \pmod{7}、すなわち 2k2k+3{}+ 3≡0{}\equiv 0 で、2k2k≡−3{}\equiv -3≡4{}\equiv 4 です。22 と 77 は互いに素なので両辺を 22 で割って kk≡2(mod7){}\equiv 2 \pmod{7} です。最小の kk は 22 で、nn=18{}= 18 です。

両方の場合を比べて、最小の nn は 18‾\underline{18} です。（確かめ）18218^2+18{}+ 18+1{}+ 1=343{}= 343=73{}= 7^3 で、確かに 4949 の倍数です。

nn=7k{}= 7k+2{}+ 2 の場合の kk についての条件は、一次不定方程式 5k5k−7l{}- 7l=−1{}= -1 として解くこともできます。

自己採点：
記録を読み込み中…

数学小話コーナー

本の裏の最後の数字——ISBN のチェックディジット

本の裏表紙には「ISBN」で始まる番号が印刷されています。世界中の本を1冊ずつ区別するための番号ですが、その最後の1けただけは、本を区別するためのものではありません。前のけたの打ち間違いを見つけるために、計算で付け足された数字で、チェックディジット（検査用数字）と呼ばれます。

20062006 年まで使われていた 1010 けたの ISBN では、次の約束で最後のけたを決めていました。1010 けたの数字を左から d1,d_1, d2,\ d_2, …,\ \ldots, d10\ d_{10} として

10d1\displaystyle 10d_1+9d2\displaystyle {}+ 9d_2+8d3\displaystyle {}+ 8d_3+⋯\displaystyle {}+ \cdots+2d9\displaystyle {}+ 2d_9+d10\displaystyle {}+ d_{10}≡0(mod11)\displaystyle {}\equiv 0 \pmod{11}

となるように d10d_{10} を選びます。たとえば架空の番号 4 8 1 0 2 3 5 7 64\ 8\ 1\ 0\ 2\ 3\ 5\ 7\ 6 なら、重みをつけた和は 4040+72{}+ 72+8{}+ 8+0{}+ 0+12{}+ 12+15{}+ 15+20{}+ 20+21{}+ 21+12{}+ 12=200{}= 200 で、200200≡2(mod11){}\equiv 2 \pmod{11} ですから、d10d_{10}=9{}= 9 を足せばちょうど 1111 の倍数になります。d10d_{10} が 1010 になってしまうときは、1けたで書けないのでローマ数字の X\mathrm{X} を使います。ISBN の末尾に X\mathrm{X} が付いた本があるのは、このためです。

法に 1111 という素数を選んだことには理由があります。1けただけ打ち間違えると、和は「重み × 数字のずれ」だけ変わります。重みは 11 から 1010、ずれは −9-9 から 99（00 以外）なので、どちらも 1111 の倍数ではなく、1111 は素数ですから、その積も 1111 の倍数になりません。だから和が 1111 の倍数でなくなり、間違いが必ず見つかります。となり合う2つの数字を入れかえた場合も、和の変化は「数字の差」そのものになるので、やはり必ず見つかります。

20072007 年からは 1313 けたの ISBN に切りかわり、重みを 1,1, 3,\ 3, 1,\ 1, 3,\ 3, …\ \ldots として和が 1010 の倍数になるように決める方式になりました。こちらも1けたの間違いは必ず見つかります。33 と 1010 が互いに素なので、「3×3 \times ずれ」が 1010 の倍数になるのは、ずれ自体が 1010 の倍数のときだけだからです（本文 公式4 のあとの「割り算は互いに素なら可能」と同じ理屈です）。ところが、となり合う数字の入れかえでは、和の変化が「2×2 \times 数字の差」になります。差が 55 のとき、たとえば 11 と 66 を入れかえると、変化は 1010 で見のがされてしまいます。法が素数でないと、こうした抜け穴ができるのです。

豆知識

クレジットカードの番号にも、最後の1けたにチェックディジットがあります。1950年代に IBM の研究者ハンス・ピーター・ルーンが考えた方式で、右から数えて偶数番目の数字を 22 倍し（1010 以上になったら 99 を引き）、全部を足した和が 1010 の倍数になるように決めます。インターネットの買い物で番号を1けた打ち間違えたとき、送信する前に「番号が正しくありません」と表示されるのは、この合同式の検査が手元で行われているからです。

8 回シャッフルするとトランプが元に戻る

5252 枚のトランプをちょうど 2626 枚ずつに分け、左右の山から1枚ずつ、完全に交互にかみ合わせるシャッフルを考えます。手品師の世界でファロー・シャッフルと呼ばれる技です。いちばん上のカードが上に残るようにかみ合わせるやり方（アウト・シャッフル）を 88 回くり返すと、なんとトランプは最初の並びに完全に戻ります。

合同式で理由を見てみましょう。カードの位置を上から 0,0, 1,\ 1, 2,\ 2, …,\ \ldots, 51\ 51 と番号づけします。上の山の ii 番のカードは、シャッフル後に 2i2i 番へ移ります。下の山の ii 番（2626≦i{}\leqq i≦51{}\leqq 51）のカードは 2i2i−51{}- 51 番へ移ります。どちらの場合も、移った先は

2i(mod51)2i \pmod{51}

で表せます（いちばん上の 00 番といちばん下の 5151 番は動きません）。つまり、11 回のシャッフルは「位置を 22 倍して 5151 で割った余りをとる」操作です。kk 回くり返せば位置は 2ki2^k i の余りになるので、全部のカードが元に戻るのは

2k\displaystyle 2^k≡1(mod51)\displaystyle {}\equiv 1 \pmod{51}

となるときです。282^8=256{}= 256=51×5{}= 51 \times 5+1{}+ 1 なので、kk=8{}= 8 で初めてこれが成り立ちます。本文の公式5 で見た「累乗の余りの周期」が、そのままシャッフルの回数になっているわけです。

いちばん上のカードが2枚目に入るようにかみ合わせるやり方（イン・シャッフル）では、位置を 11 から 5252 で番号づけすると「22 倍して 5353 で割った余り」になります。2k2^k≡1(mod53){}\equiv 1 \pmod{53} となる最小の kk は 5252 なので、元に戻るまでに 5252 回もかかります。わずかなかみ合わせ方の違いで、88 回が 5252 回に変わるのです。

こうしたシャッフルの数学は、10代で家を出て手品師のもとで腕を磨き、のちに数学者になったパーシ・ダイアコニスらによって詳しく調べられました。ふつうのリフル・シャッフルで 5252 枚を十分に混ぜるには約 77 回必要だ、という彼らの研究結果もよく知られています（※「十分に混ざる」の基準の取り方によって回数は変わります）。

豆知識

ファロー・シャッフルには、第4章の 22 進法を使った技もあります。いちばん上のカードを上から nn 番目（いちばん上を 00 番と数える）に移したいとき、nn を 22 進法で書き、上の位から順に「11 ならイン、00 ならアウト」とシャッフルすればよいのです。イン・シャッフルは位置 xx を 2x2x+1{}+ 1 に、アウト・シャッフルは 2x2x に移すので、これは第4章 公式2 の「22 倍して次の位の数字を足す」計算そのものです。考案者の名をとって「エルムズリーの技法」と呼ばれています（※）。

素数の検査にひそむにせもの——341 と 561

1717 世紀のフランスの数学者フェルマーは、16401640 年の手紙の中で、次の性質を書き送りました。

pp が素数で、aa が pp の倍数でないとき、ap−1a^{p-1}≡1(modp){}\equiv 1 \pmod{p}

いまではフェルマーの小定理と呼ばれる定理です（この章の厳密定義で証明します）。フェルマー自身は証明を書き残しておらず、最初に証明を発表したのはオイラーで、17361736 年のことだとされています（※ライプニッツがそれより前に証明を書いていたともいわれます）。

この定理を逆向きに使えば、素数かどうかの検査ができそうです。2n−12^{n-1} を nn で割った余りが 11 でなければ、nn は素数ではありません。何百けたもある数の素因数分解は非常に難しいのですが、累乗の余りなら公式5 の考え方で速く計算できるので、これは実用的な検査になります。

では、余りが 11 になれば素数だといえるでしょうか。残念ながら、にせものがいます。341341=11×31{}= 11 \times 31 は素数ではありませんが

210\displaystyle 2^{10}=1024\displaystyle {}= 1024=3×341\displaystyle {}= 3 \times 341+1\displaystyle {}+ 1≡1(mod341)\displaystyle {}\equiv 1 \pmod{341}

なので、23402^{340}=(210)34{}= (2^{10})^{34}≡1(mod341){}\equiv 1 \pmod{341} となり、検査をすり抜けてしまいます。この例は 18191819 年にサリュが指摘したとされます（※）。このように底 22 の検査を通過してしまう合成数を、22 を底とする擬素数といいます。

底を 33 や 55 に変えれば、341341 のにせものはすぐばれます。ところが、nn と互いに素などんな底 aa に対しても an−1a^{n-1}≡1(modn){}\equiv 1 \pmod{n} となる、たちの悪い合成数も存在します。最小のものが 561561=3×11×17{}= 3 \times 11 \times 17 で、19101910 年にアメリカの数学者カーマイケルが示したことからカーマイケル数と呼ばれます（※それ以前にチェコのシメルカが見つけていたともいわれます）。からくりは、560560 が 33−1{}- 1，1111−1{}- 1，1717−1{}- 1 のどれでも割り切れることにあります。フェルマーの小定理から a560a^{560} は 33 を法としても、1111 を法としても、1717 を法としても 11 と合同になり、この3つが互いに素なので、561561 を法としても 11 と合同になるのです。

カーマイケル数が無限に存在することは、19941994 年に証明されました。現在、暗号で使う大きな素数を作るときには、こうしたにせものも見破れるように改良された「ミラー・ラビン法」などの検査が使われています。

豆知識

素数を完全に見分ける合同式もあります。「pp が素数であることと、(p−1)!(p - 1)!≡−1(modp){}\equiv -1 \pmod{p} は同値」というウィルソンの定理で、たとえば 6!6!=720{}= 720=7×103{}= 7 \times 103−1{}- 1 です。1818 世紀にウォーリングが著書で紹介し、ラグランジュが証明を与えたとされます（※）。ただ、階乗はあっという間に巨大になるので、実際の素数判定には使われていません。

厳密定義（発展）

※ここは発展ページです。本文では、合同式を「余りが等しいことの略記」として導入し、計算の規則を具体的な数で確かめながら使いました。ここでは合同を整除の言葉で定義しなおし、計算の規則、割り算ができる条件、一次合同式の解の構造を証明します。そのうえで、合同式の代表的な定理であるフェルマーの小定理を証明し、第3章の中国の剰余定理を合同式の言葉で言いかえます。

このページでは、とくに断らないかぎり文字は整数を表し、mm，nn は自然数とします。第1章・第2章の厳密定義で導入した整除の記号 b∣ab \mid a、第2章 定理1（除法の定理）と定理4（最大公約数は axax+by{}+ by の形に書ける）を使います。また、第1章 定理5 は自然数についての定理ですが、整数についても絶対値をとれば同じことが成り立つので、そのまま引用します（00 はすべての自然数で割り切れることに注意します）。

合同の定義

定義1：合同

mm を自然数とする。整数 aa，bb が m∣am \mid a−b{}- b を満たすとき、aa と bb は mm を法として合同であるといい

a\displaystyle a≡b(modm)\displaystyle {}\equiv b \pmod{m}

と書く。m∣am \mid a−b{}- b でないときは aa≢b(modm){}\not\equiv b \pmod{m} と書く。

定理1：合同の基本性質

mm を自然数とする。

(1) aa≡b(modm){}\equiv b \pmod{m} であることと、aa と bb を mm で割った余りが等しいことは同値である。

(2) すべての整数 aa，bb，cc について、次が成り立つ。

  • （反射律）aa≡a(modm){}\equiv a \pmod{m}
  • （対称律）aa≡b{}\equiv b ならば bb≡a(modm){}\equiv a \pmod{m}
  • （推移律）aa≡b{}\equiv b かつ bb≡c{}\equiv c ならば aa≡c(modm){}\equiv c \pmod{m}

証明　(1) 第2章 定理1 により aa=mp{}= mp+r{}+ r，bb=mq{}= mq+s{}+ s（00≦r,{}\leqq r,ss≦m{}\leqq m−1{}- 1）と書ける。aa−b{}- b=m(p−q){}= m(p - q)+(r−s){}+ (r - s) なので、第1章 定理1(2) より、m∣am \mid a−b{}- b と m∣rm \mid r−s{}- s は同値である。∣r−s∣|r - s|≦m{}\leqq m−1{}- 1<m{}< m だから、m∣rm \mid r−s{}- s となるのは rr−s{}- s=0{}= 0 のときに限る。よって m∣am \mid a−b{}- b と rr=s{}= s は同値である。

(2) aa−a{}- a=0{}= 0=m⋅0{}= m \cdot 0 から反射律が従う。aa−b{}- b=mk{}= mk なら bb−a{}- a=m(−k){}= m(-k) なので対称律が従う。aa−b{}- b=mk{}= mk，bb−c{}- c=ml{}= ml なら aa−c{}- c=m(k+l){}= m(k + l) なので推移律が従う。（証明終）

反射律・対称律・推移律の3つを満たす関係を同値関係といいます。等号 == もその1つで、合同が「ゆるい等号」として使えるのは、この3つの性質をもつからです。

mm を法として aa と合同な整数全体の集まりを、aa を含む剰余類といいます。定理1(1) より、剰余類は「mm で割った余りが rr である整数全体」（rr=0,{}= 0, 1,\ 1, …,\ \ldots, m\ m−1{}- 1）の mm 個で、どの整数もちょうど1つの剰余類に属します。本文 公式1 の分類は、この mm 個の剰余類への分割のことです。

合同式の演算

定理2：合同式の演算

aa≡b(modm){}\equiv b \pmod{m}，cc≡d(modm){}\equiv d \pmod{m} とする。このとき

(1) aa+c{}+ c≡b{}\equiv b+d{}+ d，aa−c{}- c≡b{}\equiv b−d(modm){}- d \pmod{m}

(2) acac≡bd(modm){}\equiv bd \pmod{m}

(3) すべての自然数 nn について ana^n≡bn(modm){}\equiv b^n \pmod{m}

(4) f(x)f(x) を整数を係数とする多項式とすると、f(a)f(a)≡f(b)(modm){}\equiv f(b) \pmod{m}

が成り立つ。

証明　aa−b{}- b=mk{}= mk，cc−d{}- d=ml{}= ml とおく。

(1) (a+c)(a + c)−(b+d){}- (b + d)=m(k+l){}= m(k + l)，(a−c)(a - c)−(b−d){}- (b - d)=m(k−l){}= m(k - l) である。

(2) acac−bd{}- bd=a(c−d){}= a(c - d)+d(a−b){}+ d(a - b)=m(al+dk){}= m(al + dk) である。

(3) (2) で cc=a{}= a，dd=b{}= b とすると a2a^2≡b2{}\equiv b^2 である。ana^n≡bn{}\equiv b^n が成り立つとき、これと aa≡b{}\equiv b に (2) を使えば an+1a^{n+1}≡bn+1{}\equiv b^{n+1} である。nn=1{}= 1 から順にたどれば、すべての自然数 nn で成り立つ。

(4) f(x)f(x)=ckxk{}= c_k x^k+⋯{}+ \cdots+c1x{}+ c_1 x+c0{}+ c_0 とする。(3) と、cic_i≡ci{}\equiv c_i（反射律）に (2) を使って ciaic_i a^i≡cibi{}\equiv c_i b^i である。これらを (1) で足し合わせればよい。（証明終）

(4) により、整数係数の多項式の値の余りは、xx の剰余類ごとに1回計算すれば済みます。実践問題 j20 で n2n^2+n{}+ n+1{}+ 1 を nn≡0,{}\equiv 0, 1,\ 1, …,\ \ldots, 6(mod7)\ 6 \pmod{7} の 77 通りだけ調べたのは、この性質によるものです。

割り算ができる条件

定理3：合同式の両辺を割る

(1) cc と mm が互いに素ならば、acac≡bc(modm){}\equiv bc \pmod{m} から aa≡b(modm){}\equiv b \pmod{m} が従う。

(2) 一般に、cc≠0{}\neq 0 として cc と mm の最大公約数を gg とすると

ac\displaystyle ac≡bc(modm)\displaystyle {}\equiv bc \pmod{m}  ⟺  a\displaystyle {}\iff a≡b(modmg)\displaystyle {}\equiv b \pmod{\tfrac{m}{g}}

が成り立つ。

証明　(2) を示せば、gg=1{}= 1 の場合として (1) が得られる。cc=gc′{}= gc'，mm=gm′{}= gm' とおくと、c′c' と m′m' は互いに素である（第1章 公式6 と同じ理由）。

m∣(a−b)c\displaystyle m \mid (a - b)c  ⟺  gm′∣gc′(a−b)\displaystyle {}\iff gm' \mid gc'(a - b)  ⟺  m′∣c′(a−b)\displaystyle {}\iff m' \mid c'(a - b)

である。c′c' と m′m' は互いに素なので、第1章 定理5(2) より、m′∣c′(a−b)m' \mid c'(a - b) と m′∣am' \mid a−b{}- b は同値である（逆向きは明らか）。よって acac≡bc(modm){}\equiv bc \pmod{m} と aa≡b(modm′){}\equiv b \pmod{m'} は同値である。（証明終）

本文の例 2×32 \times 3≡2×8(mod10){}\equiv 2 \times 8 \pmod{10} では、cc=2{}= 2，gg=2{}= 2 なので、正しく割ると 33≡8(mod5){}\equiv 8 \pmod{5} になります。これは確かに成り立っています。「割るなら法も最大公約数で割る」という本文 公式6 と例題6(2) の約束は、この定理の (2) にもとづいています。

一次合同式

定理4：一次合同式の解

aa≠0{}\neq 0 とし、aa と mm の最大公約数を gg とする。一次合同式

ax\displaystyle ax≡b(modm)\displaystyle {}\equiv b \pmod{m}

について、次が成り立つ。

(1) 解をもつための必要十分条件は g∣bg \mid b である。

(2) gg=1{}= 1 のとき、解は mm を法としてただ1つである。すなわち、解の1つを x0x_0 とすると、解の全体は xx≡x0(modm){}\equiv x_0 \pmod{m} である。

(3) g∣bg \mid b のとき、m′m'=mg{}= \dfrac{m}{g} とおくと、解の全体は mm を法としてちょうど gg 個の剰余類

x\displaystyle x≡x0,\displaystyle {}\equiv x_0, x0\displaystyle \ x_0+m′,\displaystyle {}+ m', x0\displaystyle \ x_0+2m′,\displaystyle {}+ 2m', …,\displaystyle \ \ldots, x0\displaystyle \ x_0+(g−1)m′(modm)\displaystyle {}+ (g - 1)m' \pmod{m}

からなる。ここで x0x_0 は解の1つである。

証明　(1) axax≡b(modm){}\equiv b \pmod{m} となる xx があることは、axax−my{}- my=b{}= b を満たす整数 xx，yy があることと同じである。第3章 定理1 より、これは aa と −m-m の最大公約数 gg について g∣bg \mid b であることと同値である。

(2) gg=1{}= 1 のとき、第2章 定理4 より auau+mv{}+ mv=1{}= 1 となる整数 uu，vv がある（aa<0{}< 0 なら uu の符号を変える）。すると auau≡1(modm){}\equiv 1 \pmod{m} で、x0x_0=ub{}= ub とおけば ax0ax_0=(au)b{}= (au)b≡b{}\equiv b なので x0x_0 は解である。xx も解なら axax≡ax0(modm){}\equiv ax_0 \pmod{m} で、aa と mm は互いに素なので定理3(1) より xx≡x0(modm){}\equiv x_0 \pmod{m} である。逆に xx≡x0{}\equiv x_0 なら定理2(2) より axax≡ax0{}\equiv ax_0≡b{}\equiv b である。

(3) aa=ga′{}= ga'，bb=gb′{}= gb' とおくと、m∣axm \mid ax−b{}- b  ⟺  gm′∣g(a′x−b′){}\iff gm' \mid g(a'x - b')  ⟺  m′∣a′x{}\iff m' \mid a'x−b′{}- b' なので、もとの合同式は a′xa'x≡b′(modm′){}\equiv b' \pmod{m'} と同値である。a′a' と m′m' は互いに素なので、(2) より解の全体は xx≡x0(modm′){}\equiv x_0 \pmod{m'}、つまり xx=x0{}= x_0+m′t{}+ m't（tt は整数）である。

tt を gg で割って tt=gq{}= gq+j{}+ j（00≦j{}\leqq j≦g{}\leqq g−1{}- 1）とすると、xx=x0{}= x_0+jm′{}+ jm'+mq{}+ mq≡x0{}\equiv x_0+jm′(modm){}+ jm' \pmod{m} である。また 00≦j{}\leqq j<j′{}< j'≦g{}\leqq g−1{}- 1 なら、差 (j′−j)m′(j' - j)m' は 00<(j′−j)m′{}< (j' - j)m'<gm′{}< gm'=m{}= m を満たすので mm の倍数でなく、x0x_0+jm′{}+ jm' と x0x_0+j′m′{}+ j'm' は mm を法として合同でない。よって、解はちょうど gg 個の剰余類からなる。（証明終）

(2) の uu のように、auau≡1(modm){}\equiv 1 \pmod{m} を満たす数を、mm を法とする aa の逆元といいます。本文で「合鍵」と呼んだものです。とくに mm が素数 pp のときは、pp の倍数でないどの aa も pp と互いに素なので、逆元をもちます。pp を法とする世界では、00 以外の数でなら自由に割り算ができるのです。このように四則演算が自由にできる数の集まりは体と呼ばれ、pp を法とする剰余類の体は、大学で学ぶ代数学や、暗号・誤り訂正符号の理論で重要な役割を果たします。

フェルマーの小定理

定理5：フェルマーの小定理

pp を素数とする。

(1) aa が pp の倍数でないならば、ap−1a^{p-1}≡1(modp){}\equiv 1 \pmod{p} である。

(2) すべての整数 aa について、apa^p≡a(modp){}\equiv a \pmod{p} である。

証明　(1) pp−1{}- 1 個の整数

a,\displaystyle a, 2a,\displaystyle \ 2a, 3a,\displaystyle \ 3a, …,\displaystyle \ \ldots, (p−1)a\displaystyle \ (p - 1)a

を考える。

まず、どれも pp の倍数でない。実際、11≦k{}\leqq k≦p{}\leqq p−1{}- 1 なら p∤kp \nmid k で、p∤ap \nmid a だから、第1章 定理5(1) より p∤kap \nmid ka である。

次に、どの2つも pp を法として合同でない。iaia≡ja(modp){}\equiv ja \pmod{p}（11≦i,{}\leqq i,jj≦p{}\leqq p−1{}- 1）とすると、pp は素数で p∤ap \nmid a なので aa と pp は互いに素であり、定理3(1) より ii≡j(modp){}\equiv j \pmod{p} である。∣i−j∣|i - j|≦p{}\leqq p−2{}- 2<p{}< p なので ii=j{}= j である。

したがって、a,a, 2a,\ 2a, …,\ \ldots, (p−1)a\ (p - 1)a を pp で割った余りは、11 から pp−1{}- 1 までの pp−1{}- 1 個の値をたがいに重複なくとる。つまり、並べる順序を除いて 1,1, 2,\ 2, …,\ \ldots, p\ p−1{}- 1 と一致する。そこで、すべてを掛け合わせると、定理2(2) より

a⋅2a⋅3a⋯(p−1)a\displaystyle a \cdot 2a \cdot 3a \cdots (p - 1)a≡1⋅2⋅3⋯(p−1)(modp)\displaystyle {}\equiv 1 \cdot 2 \cdot 3 \cdots (p - 1) \pmod{p}

すなわち

ap−1⋅(p−1)!\displaystyle a^{p-1} \cdot (p - 1)!≡(p−1)!(modp)\displaystyle {}\equiv (p - 1)! \pmod{p}

である。(p−1)!(p - 1)! の因数 1,1, 2,\ 2, …,\ \ldots, p\ p−1{}- 1 はどれも pp で割り切れないので、第1章 定理5(1) をくり返し使えば p∤(p−1)!p \nmid (p - 1)! であり、(p−1)!(p - 1)! と pp は互いに素である。定理3(1) により両辺を (p−1)!(p - 1)! で割って、ap−1a^{p-1}≡1(modp){}\equiv 1 \pmod{p} を得る。

(2) p∤ap \nmid a なら、(1) の両辺に aa を掛ければよい。p∣ap \mid a なら、両辺とも pp を法として 00 と合同である。（証明終）

証明の中心は「aa 倍しても余りの顔ぶれが変わらない」という観察で、第3章 実践問題 j19 や本文 公式6 の「33 倍すると 00 から 66 が1回ずつ現れる」と同じ考え方です。

この定理を使うと、本文 例題5(1) は 363^6≡1(mod7){}\equiv 1 \pmod{7} から 31003^{100}=(36)16⋅34{}= (3^6)^{16} \cdot 3^4≡81{}\equiv 81≡4{}\equiv 4 と、周期を探さずに求められます。実践問題 j17 の「n5n^5−n{}- n が 55 の倍数」は、(2) の pp=5{}= 5 の場合です。

pp が素数でないと、(1) は一般には成り立ちません。たとえば mm=6{}= 6，aa=5{}= 5 とすると、55≡−1{}\equiv -1 より 555^5≡−1{}\equiv -1≡5(mod6){}\equiv 5 \pmod{6} で、11 になりません。mm が素数でないときは、pp−1{}- 1 を「11 から mm までのうち mm と互いに素な数の個数」φ(m)\varphi(m) に取りかえた

aφ(m)\displaystyle a^{\varphi(m)}≡1(modm)\displaystyle {}\equiv 1 \pmod{m}(a と m は互いに素)\displaystyle (a \ \text{と} \ m \ \text{は互いに素})

が成り立ちます。これをオイラーの定理といい、φ\varphi をオイラー関数といいます。証明は定理5 と同じで、11 から mm までのうち mm と互いに素な数だけを aa 倍して並べればよいのです。たとえば φ(10)\varphi(10)=4{}= 4（1,1, 3,\ 3, 7,\ 7, 9\ 9）なので、1010 と互いに素な aa について a4a^4≡1(mod10){}\equiv 1 \pmod{10} で、本文 例題5(2) の 343^4≡1{}\equiv 1 はその一例です。ただし φ(100)\varphi(100)=40{}= 40 ですが、実践問題 j16 のように 747^4≡1(mod100){}\equiv 1 \pmod{100} と、もっと短い周期で 11 に戻ることもあります。オイラーの定理は「11 に戻る指数の1つ」を保証するだけで、最小の指数を与えるとは限りません。

中国の剰余定理（合同式による言いかえ）

定理6：中国の剰余定理

mm，nn を互いに素な自然数とする。どんな整数 rr，ss に対しても、連立合同式

x\displaystyle x≡r(modm),\displaystyle {}\equiv r \pmod{m},x\displaystyle x≡s(modn)\displaystyle {}\equiv s \pmod{n}

は解をもち、その解の全体は mnmn を法としてただ1つの剰余類をなす。

証明　これは第3章 定理4 を合同式で書き直したものであるが、定理4 を使った証明を与える。

（存在）第1の式を満たす整数は xx=r{}= r+mk{}+ mk（kk は整数）と書ける。これが第2の式を満たす条件は

mk\displaystyle mk≡s\displaystyle {}\equiv s−r(modn)\displaystyle {}- r \pmod{n}

である。mm と nn は互いに素なので、定理4(2) よりこの一次合同式は解 k0k_0 をもつ。x0x_0=r{}= r+mk0{}+ mk_0 が連立合同式の解である。

（一意性）xx，x′x' がともに解なら、m∣xm \mid x−x′{}- x' かつ n∣xn \mid x−x′{}- x' である。mm と nn は互いに素なので、第1章 定理5(3) より mn∣xmn \mid x−x′{}- x'、すなわち xx≡x′(modmn){}\equiv x' \pmod{mn} である。逆に xx≡x0(modmn){}\equiv x_0 \pmod{mn} なら、xx−x0{}- x_0 は mm の倍数でも nn の倍数でもあるので、xx も解である。（証明終）

本文 例題6(3) と実践問題 j13 は、この証明の「存在」の部分を具体的な数でたどったものです。法が3つ以上あっても、どの2つも互いに素であれば、2つずつまとめる操作をくり返して同じ結論が得られます。

こうして、合同式は「mm 個の剰余類の上での足し算・引き算・掛け算」として整理され、法が素数なら割り算まで自由にできることが分かりました。次の第6章では、1010 の累乗を割った余りの周期（10610^6≡1(mod7){}\equiv 1 \pmod{7} など）が、分数を小数に直したときの循環節の長さとして現れることを見ていきます。

この章の学習が終わったら

学習完了テストを受ける