コンテンツへスキップ
Topos Uranos
日本語

合同式とモジュラ算術

要約

この課は、整数を余りによって分類することを一つの計算体系に変える。nn を法とする合同を定義し、合同であることが余りが等しいことと同値であること、合同が同値関係であること、そして加法、乗法、累乗と両立することを証明し、その類から余りの集合 Zn\mathbb{Z}_n を、加法と乗法の表とともに構成する。ベズーの等式によってどの余りが逆元をもつかを決定し、一次合同式を完全に解く。さらに中国剰余定理とフェルマーの小定理を証明し、倍数判定法を合同式として読み直し、これらすべてを検査数字、暦、そして RSA 暗号方式に応用して、その正しさを証明する。

学習目標

  1. nn を法とする合同が、加法、乗法、累乗と両立する同値関係であることを証明し、それを用いて大きな数の余りを計算する。
  2. Zn\mathbb{Z}_n における加法と乗法の表を作り、最大公約数によってどの余りが逆元をもつかを決定する。
  3. 一次合同式が解をもつかどうかを判定し、解が nn を法としていくつあるかを計算し、そのすべてを求める。
  4. 法が互いに素な合同式の連立を中国剰余定理によって解き、解を構成してその一意性を証明する。
  5. フェルマーの小定理を証明し、累乗の余り、すべての整数について成り立つ整除の性質、そして RSA 方式の正しさに応用する。
  6. 検査数字がどの誤りを検出するかを分析し、合同式によって曜日を計算する。

合同関係

今日が月曜日なら、1515 日後は火曜日、10001000 日後は日曜日である。これを知るために日を一日ずつ数える必要はなく、日数を 77 で割った余りだけで足りる。同様に、55 時間後には、99 時から数えて 22 時になる。これは 1212 時間の文字盤での話である。また積の一の位は因数の一の位だけで決まる。三つの場合のいずれでも、余りで計算し、商は忘れている。整除と余りのある割り算の課は、自然数で割った余りによって整数を類に分け、和、積、累乗の余りが元の数の余りだけで決まることを証明した。この課はこれらの観察に固有の言語、すなわち合同式の言語を与える。これはガウスが 1801 年に Disquisitiones Arithmeticae で導入したものであり、この課はそれを計算の道具にする。あの課と同じく、整数は前もって用いられ、その演算と順序の規則は整数の課で正当化されている。

定義（合同）。nn を自然数とする。二つの整数 aa と bb が nn を法として合同であるとは、nn がその差 a−ba - b を割り切ることをいう。a≡b(modn)a \equiv b \pmod{n} と書き、「aa と bb は nn を法として合同」と読む。自然数 nn をこの合同式の法という。
a≡b(modn)↔n∣a−ba \equiv b \pmod{n} \leftrightarrow n \mid a - b

たとえば 17≡2(mod5)17 \equiv 2 \pmod{5} である。なぜなら 17−2=1517 - 2 = 15 だからである。−3≡9(mod4)-3 \equiv 9 \pmod{4} である。なぜなら −3−9=−12-3 - 9 = -12 だからである。また整数が偶数であるのは、それが 00 と 22 を法として合同であるとき、かつそのときに限る。aa が nn の倍数であることは、いまや a≡0(modn)a \equiv 0 \pmod{n} と書かれる。11 を法とすると、すべての整数が互いに合同である。11 はどの整数も割り切るからである。この場合は面白みがないので、例では法は 22 以上とする。三本線の記号 ≡\equiv は等号を思わせるが、それは、後で見るように、合同がほとんどすべての点で等式のようにふるまうからである。例外である割り算は、逆元の節で扱う。

差による定義は証明にもっとも便利だが、最初の例の直観は余りに関わっている。次の命題は、二つの記述が同じことを言っていることを保証する。その内容は、整除の課で倍数判定法を正当化する際に別の形ですでに述べられていたが、ここではすべての手順を踏んで証明する。

命題合同と余り

二つの整数が nn を法として合同であるのは、それらを nn で割った余りが等しいとき、かつそのときに限る。a=nq+ra = nq + r と b=ns+tb = ns + t を、aa と bb を nn で割った余りのある割り算とし、0≤r<n0 \leq r < n かつ 0≤t<n0 \leq t < n とする。図は −10-10 から 2424 までの整数を 55 個ずつの行に並べ、各列が同じ余りをもつ数を集めるようにしている。

証明

  1. a−b=(nq+r)−(ns+r)=n(q−s)a - b = (nq + r) - (ns + r) = \resaltar{n(q - s)}

    余りが一致するなら、r=tr = t であり、二つの割り算を引くと余りが消えて、差は nn の倍数になる。

  2. a=b+nk=ns+t+nk=n(s+k)+ta = \resaltar{b} + nk = \resaltar{ns + t} + nk = \dato{d}{n(s + k) + t}

    逆に、nn が a−ba - b を割り切る、すなわち a=b+nka = b + nk となる整数 kk があると仮定する。bb の割り算を代入する。

  3. 0≤t<n→r=t0 \leq t < n \rightarrow \resaltar{r = t}

    0≤t<n0 \leq t < n であるから、この等式は aa を nn で割った余りのある割り算であり、余りは tt である。商と余りの一意性により、tt は aa の余りであり、すなわち t=rt = r である。

  4. 23≡8≡−2≡−7≡3(mod5)23 \equiv 8 \equiv -2 \equiv -7 \equiv 3 \pmod{5}

    図では、−7-7、−2-2、33、88、1313、1818、2323 が同じ列にある。いずれも余り 33 を残し、それらの差は 55 の倍数である。

特に、どの整数も nn を法としてその余りと合同であり、その余りは nn 個の整数 0,1,…,n−10, 1, \ldots, n - 1 のうちの一つである。しかもそのうちただ一つとだけ合同である。これらの二数はそれぞれ自分自身の余りであり、異なれば余りも異なるからである。nn を法として計算するとは、各数をその列の都合のよい代表で置き換えることである。代表としては余りを用い、ときには小さな負の数、たとえば −1-1 を n−1n - 1 の代わりに用いる。