前のページ 1/1 次のページ

初等整数論において合同式(ごうどうしき、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 などと表す。このように、合同関係を表す演算子で結ばれた式を、合同式と総称する。

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 を法とする剰余」と一対一対応になるので、 は完全代表系(各類から一つずつ代表元をとってきたもの)の一つになる。整数 k の属する法 n の剰余類を、しばしば k + (n) や k + nZ などで表す。また、剰余を表すのと同様に k mod n、k mod (n), または k mod nZ と書いたり、同値類の代表的な記法に従って k や [外部リンク] style="color:#8888ff;">k、または法 n を明示して [外部リンク] style="color:#8888ff;">k_n のようにも記す。剰余との対応から、これらの記法を剰余を表すことに流用することもある。多くの場合に、剰余類に関する式は、その代表元としての剰余の間の合同関係式と読み替えることができる。

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

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

: (Z/nZ)^× =

であり、その位数はオイラーのφ関数による φ(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 で割り切れないとき、解をもたない。

◇ 連立合同方程式

◆ エピソード

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

◆ 脚注

◆ 関連項目

・ 除法

・ ウィルソンの定理

・ フェルマーの小定理

・ 指数 (初等整数論)(インデックス)

・ 平方剰余の相互法則(平方剰余・冪剰余)

・ ペル方程式

・ p進数

・ 中国の剰余定理

前のページ 1/1 次のページ

・合同式 page1