合同式

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

定義

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

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 やあるいは法 n を明示して [k_n などのようにも記す。剰余との対応から、これらの記法を剰余を表すことに流用することもあるし、多くの場合に剰余類に関する式は、その代表元としての剰余の間の合同関係式と読み替えることができる。

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

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 のときは解は1つだけである。b が d で割り切れないとき解を持たない。

定義

性質

剰余類

合同方程式

一次合同方程式

連立合同方程式

関連項目

Gourt Home::Gourt :: 合同式

定義

性質

剰余類

合同方程式

一次合同方程式

連立合同方程式

関連項目