初等整数論講義/第1章/合同式

1. 整数 $a,b$ の差が $m$ の倍数であるとき，$a$ と $b$ とは m を法(modulus)として互いに合同であるといい， それを次のように記す．

$a\equiv b{\pmod {m}}.$

これは ガウス の記法である．

合同とは congruent の訳語であって，それは幾何学でいう合同と同語である． $a\equiv b{\pmod {m}}$とは $m$の倍数なる差を無視すれば，$a$ も $b$ も同じである というふうに考えるのである．恰も二つの合同なる図形が，位置の差を無視すれば，全く合致するのと同様である．

合同ということは整数論に於いて基本的である．しかし日常生活に於いても，普通に応用されているとも言えよう． 朝は5時に起き，夜は10時にねるのは24時間を ${\bmod {}}$ として生活を律するのである． 暦は一年を ${\bmod {}}$ として季節を定める．また干支，七曜などは 10, 12, 7 などを ${\bmod {}}$ とする合同に基づく．

合同は相等，相似，対等などと同じ範疇に属する関係であって，それらに共通なる三つの規律に従うものである．即ち
反射的 $a\equiv a{\pmod {m}}$.
対称的 $a\equiv b$ ならば，$b\equiv a{\pmod {m}}$.
推移的 $a\equiv b,b\equiv c$ ならば，$a\equiv c{\pmod {m}}$.
要するに，合同なる数は互いに合同で，同じ数と合同なる数は互いに合同である．

この原則の為に，合同なる数を同類とし，不合同なる数を異類として，すべての整数を確定的に分類することが可能である．

即ち $m$ を法としての整数の一つの類とは，$m$ を法として互いに合同なるすべての整数の集合である．

例えば，$2$ を法とするならば，すべての整数は偶数と奇数との二類に分かれる．

整数を大きさの順に並べて，定理 1.2 に由って， $m$ を法（除数）としての最小剰余をもとめるならば， 剰余 $0,1,2,\ldots \ldots ,m-1$ が周期的に出て来る． その際相等しい剰余を出す数が即ち $m$ を法として互いに合同なる整数で， それらが整数の一類を組成するのである． ゆえに $m$ を法とすれば整数は $m$ 類に分かれる．

［例］

${\pmod {7}}$ に関して次の各縦列の数がそれぞれ一つの類を組み立てる．

     .     .     .     .     .    .    .
   -14   -13   -12   -11   -10   -9   -8
    -7    -6    -5    -4    -3   -2   -1
     0     1     2     3     4    5    6
     7     8     9    10    11   12   13
    14    15    16    17    18   19   20
     .     .     .     .     .    .    .

$m$ を法としての数の一類に属する唯一つの整数 $a$ を知れば，その類に属するすべての整数は確定する． それは $a+mt(t=0,\pm 1\pm 2\ldots \ldots )$ なる形の整数の全部である． 今 $m$ を法としての相異なる $m$ 類の各々から任意に一つずつの整数をその類の代表として取り出したとするとき， それらの $m$ 個の整数は $m$ を法としての各類の完全なる代表の一組（又は剰余系）を組成するという.

故に $m$ 個の整数が，$m$ を法としての完全なる代表の一組を形成するが為に必要且つ充分なる条件は， それらの $m$ 個の整数の中，どの二つもが $m$ を法として不合同なることである．

例えば上記の表の各縦列から一つずつの数を取れば ${\bmod {7}}$ に関する代表の一組が得られる．即ち

     0     1     2     3     4    5    6
     0     1     2     3    -3   -2   -1
     7    -6     9    -4   -10   -9   13  等，等．

「数の類」は Zahlklasse の訳語である．即ち類は class を意味する． ガウス が整数論に class, order, genus 等，分類に因む用語を採用した．上記 class もその系統に属する．

代表の一組（Repräsentantensystem) は読んで字の如しであるが，それを或るは剰余系（Restsystem, system of residues) ともいう． system は組であるが，それを系統又は略して系というのである．剰余系は語の短い所が宜しい．但し剰余（residue, Rest) は拡張された意味でいう．即ち $a\equiv b{\pmod {m}}$ なるとき, $b$ を $a$ の剰余と言って，それが法 $m$ よりも小なることを要求しないのである．法よりも小なる剰余に拘泥すれば，類の代表の趣意に反する．自由に代表を選ぶ所が最も大切である．

2. 同一の法を有する合同式は加法，減法，乗法に関する限り，等式と同様に取り扱うことを得るものである．

定理 1.11．

$a\equiv a'{\pmod {m}},b\equiv b'{\pmod {m}}$

ならば，

$a\pm b\equiv a'\pm b'(mod.\ m),$

$ab\equiv a'b'{\pmod {m}}$.

一般に $a\equiv a',b\equiv b'c\equiv c',\ldots \ldots {\pmod {m}}$ で， また$f(x,y,z,\ldots )$ が $x,y,z,\ldots$ に関する整係数の多項式ならば，

$f(a,b,c,\ldots \ldots )\equiv f(a',b',c',\ldots \ldots ){\pmod {m}}$.

［証］

仮定に由って

$a\equiv a'{\pmod {m}},$ 従って $a-a'$ は $m$ の倍数．

$b\equiv b'{\pmod {m}},$ 従って $b-b'$ は $m$ の倍数．

故に $(a+b)-(a'+b')=(a-a')+(b-b')$ は $m$ の倍数， 即ち

$a+b\equiv a'+b'{\pmod {m}}.$

加え合わされる数が二つより多くても同様である．

同様に

$a-b\equiv a'-b'{\pmod {m}}.$^[1]

又

$ab-a'b'=(a-a')b+a'(b-b')$ も $m$ の倍数，

即ち

$ab\equiv a'b'{\pmod {m}}$．

特に

$a\equiv a'{\pmod {m}}$．

ならば

$Na\equiv Na'{\pmod {m}}$．

又同様に因数の数に関せず，

$Na^{\alpha }b^{\beta }c^{\gamma }\ldots \ldots \equiv Na'^{\alpha }b'^{\beta }c'^{\gamma }\ldots \ldots {\pmod {m}}$．

由って加え合わされる数がいくつであっても

$\sum {Na^{\alpha }b^{\beta }c^{\gamma }\ldots \ldots }\equiv \sum {Na'^{\alpha }b'^{\beta }c'^{\gamma }\ldots \ldots }{\pmod {m}}$．

即ち

$f(a,b,c,\ldots \ldots )\equiv f(a',b',c',\ldots \ldots ){\pmod {m}}$．

除法に関しては合同式は等式のように単純には反応しない．

定理 1.12．

$ac\equiv bc{\pmod {m}}$

なるとき，(c, m)=1 なる条件の下に於いて

$a\equiv b{\pmod {m}}$

一般に $(c,m)=d$ ならば，$m=dm'$ と置くとき，

$a\equiv b{\pmod {m'}}$

［注意］ 

前の場合には $d=1$

［証］

仮定に由って

$ac\equiv bc{\pmod {m}}$．

即ち

$ac-bc=(a-b)c$ は $m$ の倍数．

故に

$(c,m)=1$ ならば $a-b$ は $m$ の倍数，(定理1.6)

即ち

$a\equiv b{\pmod {m}}$

一般に$(c,m)=d$ ならば，$m=dm',c=dc'$ と置くとき，$(c',m')=1$； 且つ

$(a-b)c'$ は $m'$ の倍数．

故に

$a-b$ は $m'$ の倍数．

即ち，$(c,m)=d$ のとき

$a\equiv b{\pmod {m'}}$

［注意］ 

このように合同式の両辺を共通の因数で割るときには，適当に法を変更せねばならない． 若しも法を変えないとすれば，共通の因数が法と互いに素なるときに限って割り算が許される． （これは等式 $ac=bc$ から $a=b$ を導くには $c\neq 0$ なる条件が必要であるのに類似する）．

命題 問題.1．

$a$ を十進法で表して

$a=a_{n}10^{n}+\ldots \ldots +a_{1}10+a_{0}$

とすれば，

$a\equiv a_{0}+a_{1}+\ldots \ldots +a_{n}{\pmod {9}}$

$a\equiv a_{0}-a_{1}+\ldots \ldots +(-1)^{n}a_{n}{\pmod {11}}$

［証］

$10\equiv 1{\pmod {9}},\therefore 10^{k}\equiv 1{\pmod {9}}$． 由って第一の合同式を得る．

又 $10\equiv -1{\pmod {11}},\therefore 10^{k}\equiv (-1)^{k}{\pmod {11}}$．由って第二の合同式を得る．

［例］

$26384\equiv 2+6+3+8+4=23\equiv 2+3\equiv 5{\pmod {9}}$．

$26384\equiv 4-8+3-6+2=\equiv -5{\pmod {11}}$．

即ち $26384$ は $9$ で割り切れない，$9$ で割れば剰余 $5$． また，$11$ でも割り切れない，剰余は $-5$ または $6$．

［注意］ 

$1001=7\cdot 11\cdot 13$ だから $1000\equiv -1{\pmod {7}}$

これを用いて，例えば

$25683941\equiv 941-683+25=283\equiv 3{\pmod {7}}$

同様に

$25683941\equiv 283\equiv 10{\pmod {13}}.$^[2]

このような数字の遊戯からでも，整数論に興味が生ずるならば，幸いである．

1. officious: $a-a'=m\alpha ,\therefore a=a'+m\alpha$，同様に $b=b'+m\beta$，辺々引いて $(a-b)=(a'-b')+m(\alpha -\beta ),\therefore (a-b)-(a'-b')=m(\alpha -\beta )$
2. officious: $7\cdot 11\cdot 13=1001$ ゆえに $1000\equiv -1{\pmod {13}}$

---