合同式

合同式の最新ニュースをまとめて検索！

初等整数論において合同式（ごうどうしき、modular equality）とは整数を整除関係を用いて分類することによって定義される一種の等式である。ある自然数で割った余りが等しいかどうかを判定する。1801年にカール・フリードリヒ・ガウスが『整数論』で導入した。

[編集] 定義

2つの整数 a, b は、a − b が自然数 n で割り切れるとき、n を法として合同（n をほうとしてごうどう、congruent modulo n ）であるといい、a ≡ b (modulo n), a ≡ b (mod n) あるいは a ≡_n b などと表す。このように、合同関係を表す演算子で結ばれた式を、合同式と総称する^[1]。

a ≡ b (mod n) は、a, b それぞれを自然数 n で割ったときの剰余が等しいことと同値である。また同じことであるが、整数 k の n を法とする剰余はしばしば k mod n で表されるので、この記法に従えば、合同式 a ≡ b (mod n) は等式 a mod n = b mod n に書き直すことができる（この等式で k mod n を後述のように剰余類の意味にとっても同じことである）。

[編集] 性質

合同式は等式と同様に、以下のような関係を満足する。

（反射律） a ≡ a (mod n)
（対称律） a ≡ b ならば b ≡ a (mod n)
（推移律） a ≡ b かつ b ≡ c ならば a ≡ c (mod n)

a ≡ b (mod n) かつ k が整数、m が自然数であるとき、

（移項） a ± k ≡ b ± k (mod n),
（定数倍） ka ≡ kb (mod n)
（累乗） a^m ≡ b^m (mod n)

a ≡ b (mod n), c ≡ d (mod n) ならば、k を整数として、

（加法、減法） a ± c ≡ b ± d (mod n)
（乗法） ac ≡ bd (mod n)
（除法） k と n が互いに素のとき、ka ≡ kb (mod n) ならば a ≡ b (mod n)

[編集] 剰余類

反射律・対称律・推移律が成立するので、n を法として合同という関係は、整数全体の成す集合 Z における同値関係である。この同値関係による同値類のことを、n を法とする剰余類と呼ぶ。各剰余類は「n を法とする剰余」と一対一対応になるので、{0, 1, ..., n − 1} は完全代表系（各類から一つずつ代表元をとってきたもの）の一つになる。整数 k の属する法 n の剰余類を、しばしば k + (n) や k + nZ などで表す。また、剰余を表すのと同様に k mod n、k mod (n), または k mod nZ と書いたり、同値類の代表的な記法に従って k や [k]、または法 n を明示して [k]_n のようにも記す。剰余との対応から、これらの記法を剰余を表すことに流用することもある。多くの場合に、剰余類に関する式は、その代表元としての剰余の間の合同関係式と読み替えることができる。

整数全体 Z を n を法とする合同関係で類別した集合を、Z/(n) または Z/nZ と表す。上で見た合同式の性質から、Z/nZ には和と積が定義されて、環となる。これを n を法とする剰余環という。特に、p が素数であるときの剰余環 Z/pZ は p 個の元からなる体（有限体）であり、その標数は p である。

Z/nZ の乗法群、すなわち乗法における可逆元全体のなす群を (Z/nZ)^× と書くと、

(Z/nZ)^× = {[k] | 1 ≤ k ≤ n, GCD(k, n) = 1}

であり、その位数はオイラーのφ関数による φ(n) である。したがって、群の一般論から、オイラーの定理が導かれる。(Z/nZ)^× の元 a の位数を ord_n a などと表す。(Z/nZ)^× が巡回群であるのは、n が 2, 4, 奇素数の冪、奇素数の冪の2倍のいずれかのとき、またそのときに限る。その場合の生成元を原始根（原始元）と呼ぶ。

n が m を割り切るとき、x mod m から法を取り換えて x mod n を作る操作によって Z/mZ から Z/nZ への写像が定義可能 (well-defined) であって、全射な環凖同型となる。これを法の取り替えの定める自然な全射または標準射影という。特に、n が素数 p の自然数冪であるような剰余環 Z/nZ たち全体にそれらの間で考えうる自然な全射準同型たちを合わせて考えたものは射影系を成し、この射影系の射影極限は p-進整数環 Z_p となる。

[編集] 合同方程式

合同式の形で書かれた方程式を、合同方程式という。

[編集] 一次合同方程式

一次合同方程式の一般形は、ax ≡ b (mod n) となる。このとき、 a と n の最大公約数を d とする。b が d で割り切れるとき、d 個の解をもつ。特に d = 1 のときは、解は一つだけである。b が d で割り切れないとき、解をもたない。

[編集] 連立合同方程式

この節は執筆中です。加筆、訂正して下さる協力者を求めています。

[編集] エピソード

ガウスは、合同式の記号について、「この計算式を身につけた人ならまったく天才でさえ途方に暮れるようなこみ入った場合にも機械的に問題が解ける」と述べている^[1]。

[編集] 脚注

^ ^い ^ろ遠山啓『数学入門（下）』岩波書店〈岩波文庫〉（原著1960-10-20）、初版、pp. 6,12。2009-02-28閲覧。

最終更新 2009年7月15日 (水) 18:08 （日時は個人設定で未設定ならばUTC）。
【合同式】変更履歴

[nyuumon-0] い ^ろ遠山啓『数学入門（下）』岩波書店〈岩波文庫〉（原著1960-10-20）、初版、pp. 6,12。2009-02-28閲覧。

[1]

合同式

目次