整数の合同の理論は，暗号の理論などに良く使われるもので，計算機について詳しく知ろうとする人にとって基本的な常識の１つです。勿論，詳しい正確な説明はかなりの量の説明が必要です 。それは初等整数論の教科書に譲ることにして，ここでは，合同の定義と１次合同式について説明します。 整数，或いは自然数の研究は古くピタゴラスまで遡ります。そしてそれらの成果はユークリッド「原論」の中に見ることが出来ます。そこでは，ユークリッドの互除法を始めとして，素数の無限性や，完全数などが扱われています。 近代的な整数論は，フェルマー（１６０１－１６６５）に始まると言われています。フェルマーは整数について多くの結果・事実を指摘しています。フェルマーに続いて多くの数学者が整数論の研究に携わりました。その中でもオイラー（１７０７－１７８３）やラグランジェ（１７３６－１８１３）は有名です。そこでの基本的問題として，ある数をある数で割ったときの余りの性質を調べることがありました。例えばオイラーらは４で割って余りが１となる素数は２つの平方数の和として表されること示しています。例えば ５＝１２＋２２ １３＝２２＋３２ です。この定理はフェルマーによって直角３角形の基本定理と呼ばれたものです。フェルマーはこの事実を指摘していましたが，証明されたのはそれから１００年も経ってのことでした。 整数の合同は或る数で割ったときの余りに注目してその性質を調べるもので，その研究は古くからのものです。しかし，ガウス（１７７７－１８５５）が「数論研究」（Disquitiones arithmeticae)で整数の合同について新しい記法を考え出してから，合同の理論の新たな進展が始まりました。 ガウスは a-b が m で割り切られるとき， a ≡b (mod m) と表しました。これは単なる言い換えとも見られますが， これは，整数の合同と数の相等との類似性への深い洞察の成果であり，この記法によって合同の理論のより深化が可能になりました。 数学における記法は進化は対応する概念の進化を伴います。ですから優れた記法の発明は，１つの理論の発見にも匹敵します。 勿論，ガウスの数学に対する膨大な貢献の中では，これはほんのささやかなものです。 以下この≡の基本的性質をまとめてみましょう。
例えば， 13 ≡ 5 (mod 8) です。 このように，a ≡ b (mod m) を定義すると，≡ と ＝が良く似た性質を持つことが分かります。まず，次が成立します。
このことは，≡の関係が＝と同様に，代入などが可能であること示しています。例えば，13 ≡ 5 (mod 8) かつ13 ≡ 21 (mod 8)から， 21 ≡13 ≡ 5 (mod 8)，すなわち 21 ≡ 5 (mod 8) を結論できます。
この≡は加減乗について次の性質も持ちます。
ここで，* は乗法を表します。この性質の証明は簡単で，結果も自然なものですが，かなりのパワーのある性質です。例えば，
といった問題を考えて見ましょう。7100は85桁の数です。現在の計算機の能力からすれば，この数を実際に計算することは簡単です。実際 7100= 203198904625400933895331391691459636928060001 ですから，この数を実際に6で割って余りはを求めることは可能です。しかし，この計算を手で行うと言う人は少ないでしょう。実はこの余りは上の性質を使うことで瞬時に求められます。実際，
このように≡は加減乗については，良い性質を持ち，扱いも簡単です。
m を法とする合同を考えるとき，実際に扱う数の代表を考えると都合が良い場合があります。
例えば，次のような問題を考えて見ます。
この問題は，7を法とする合同の理論を使うと次のように証明できます。
よく使われる代表系として，別の代表系もあります。
こちらの代表系は，最小非負剰余代表系に比べて，技術的に感じるかもしれませんが，実際はそうでもありません。 例えば，7 を法とする絶対値最小剰余代表系は {-3, -2, -1, 0, 1, 2, 3} となります。こちらの代表系を使って上の例の証明をもう一度くりかえします。
こちらの方が，むしろ自然と言えるかもしれません。 m=28 の場合の，絶対値最小剰余系は， {-128, -127, ・・・, -2, -1, 0, 1, 2, ・・・ , 126, 127 } になります。これは計算機での，８ビット整数の２の補数を用いて表現できる整数全体に他なりません。このことは一般に言えることです。即ち，
となります。２の補数表示は m = 2nを法とする合同の理論と密接な関係があります。これについては，コンピュータでの整数の計算で更に詳しい説明があります。
合同≡は加減乗については，良い性質を持ち，扱いも簡単ですした。しかし，除（割り算）についてはそうではありません。そもそも合同は整数の範囲での記法です。そして整数を整数で割った場合，整数にならないこともありますから，≡で割り算を考え ときは 少し注意が必要なのです。 例えば， a*b ≡ a*c (mod m) でも，両辺 aで割って b ≡ c (mod m) とすることが出来るとは限りません。実際，
この場合 3*5≡ 3*3 (mod 6) から 5 ≡ 3 (mod 6) を得ようとする推論には，見かけ上はありませんが，実は商が整数にならない割り算が含まれています。 しかし，割り算を注意深く，上手に解釈すると，割り算が出来る場合もあります。そのために，合同の一次方程式（１次合同式）を考えましょう。
すぐ分かることですが，合同式の解はm を法として決ります。すなわち，x が解で x ≡ x' (mod m) ならば，x' も解になります。実際，ax ≡ ax' (mod m) ですから，ax ≡ b (mod m) なら ax' ≡ b (mod m) にもなります。 例えば，3x ≡ 2 (mod 7) の解は， x ≡ 3 (mod 7) で与えられます。 一次合同式が解を持たないこともあります。 例えば， 3x ≡ 1 (mod 6) は解を持ちません。実際今の場合，x が解であったとすると，≡の定義から， 3x-1 が 6 で割り切れることになります。特に，3x-1 は3で割り切れます。しかし，3x は3で割り切られますから，1が3で割り切れることになり矛盾です。 解の存在については，次が成立します。
この証明から，解 x は拡張ユークリッドの互除法から計算できることが分かります。 上の性質で b=1 の場合が特に重要です。この場合 gcd(a, m) が 1 を割り切るとは gcd(a, m) = 1 に他なりませんから，次が成立します。
この場合，解 x は m を法にして唯１つしかないことも分かります。即ち， x と x' が共にax ≡ 1 (mod m)の解だとすると， x' ≡ x (mod m) となります。実際，ax ≡ 1 (mod m)，ax' ≡ 1 (mod m) とすると，axx' ≡ x' (mod m) となります。従って， x'≡ axx' ≡ ax'x ≡1*x ≡x (mod m) となります。 このことから m を法とする逆元を定義することが出来ます。
m を法にする a の逆元は gcd(a, m) = 1 となる a に対してのみ定義されていることに注意して下さい。また m を法にする a の逆元は整数としては唯１つではありませんが，m を法にした場合は唯１つなので，合同関係 ≡ で計算をしている場合はどれを取るという混乱はありません。 このm を法とする a の逆元xは整数ですから，他の数に掛けることが出来ます。ここで，ax ≡ 1 (mod m)ですから，x を掛けることは m を法として考えている限りは a で割ることを意味しています。 このことから次が成立します。
実際，m を法とする c の逆元を d として，ca ≡ cb (mod m) の両辺に掛けると，dca ≡ dcb (mod m) となりますが，dc ≡ 1 (mod m) より， a ≡ b (mod m) となります。 拡張ユークリッドの互除法を使うと，m を法とする a の逆元を計算するプログラムは簡単に掛けます。 次のプログラムは，a と m を入力したとき，その逆元を返します。中で拡張ユークリッドの互除法ExGCD のルーチンを使っています。
ここで説明した，整数の合同の理論はまだまだほんの入り口です。コンピュータと関係の深い部分を中心に更に項を改めて追加します。 |
|||||||||||||||||||||||||||