合同式とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > デジタル大辞泉 > 合同式の意味・解説 

ごうどう‐しき〔ガフドウ‐〕【合同式】

読み方:ごうどうしき

整数abの差が整数m割り切れるとき、この二つ整数mを法として合同であるといい、その関係を表す式。abmod m)と表す。


整数の合同

(合同式 から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/04/08 21:53 UTC 版)

1801年に出版されたガウスの『Disquisitiones Arithmeticae(整数論)』のタイトルページ。

整数合同(ごうどう、: congruence)は、数学において二つの整数の間に定められる関係である。初めてこれを構造として研究したのはドイツの数学者ガウスで、1801年に発表された著書『Disquisitiones Arithmeticae』でも扱われている。今日では整数の合同は、数論や一般代数学あるいは暗号理論などに広く用いられる。

整数の合同に基づく数学の分野は合同算術 (modular arithmetic) と呼ばれる。これは整数そのものを直接的に扱うのではなく、(modulus)と呼ばれる整数(以下本項では n で表す)で割った剰余を代表元として扱う算術である。合同算術の歴史や道具立てあるいはその応用については合同算術の項を参照。また、より包括的で堅苦しくない説明は剰余類環 (Z/nZ) の項へ譲る。

直観的な例

合同算術は整数の算術体系を、特定の値に決められた「法(ほう)」を用いて修正したものである。

カレンダー

1行が7日(1週間)のカレンダーは法7で合同な日が縦の列に並び、その月では同じ曜日になる。毎月22日のショートケーキの日は上に15日(語呂合わせでイチゴ)が乗っているという意味で宣伝に利用されている。15と22は法7において合同である。

時計算

法 12 で計算される時計の針

アナログ時計の針の指し示す時刻の「足し算」を記述する「時計算」を挙げる。具体的に、9時をスタートとして4時間を加えると、普通にいえば13時になるはずだが、実際には1時とも言う。同様に、0時をスタートとして7時間の3倍経つと21時であるが、9時とも言う。

基本的に 12 に到達するごとに 0 に戻るのであって、これは法 12 で考えているということになる。先の例では 921 は法 12 に関して合同[注釈 1]であると言う。より一般に 9, 21, 33, 45, …etc. は法 12 のもとで等しいものと考える。

文字盤に任意個数の整数の書かれた時計を想像すれば、一般化は容易であり、計算もできる。

n に関する合同

定義

n2 以上の整数として、「二つの整数 a, bn に関して合同である」とは、以下の同値な条件のいずれか(したがってすべて)を満足する場合を指す:

  1. それらの差が n で整除される(つまり、適当な整数 k が存在して ab = kn);
  2. an割った剰余 rbn で割った剰余 s と等しい;
  3. a – bnZ(つまり、 a – bn の倍数全体の成すイデアル nZ の要素になる)

記法

二つの整数が合同であることを表すのに が記号として用いられる。

ab とが法 n に関して合同であることを表すのに、以下のような表記がある。

ab (modulo n)
ab (mod. n)
ab (mod n)
ab mod n
ab (n)
ab [n]
an b
ab

どれも同様に「ab とは法 n に関して合同である」などと読む。法が n であることは「n を法として」「法 n のもとで」「法 n で」「mod n で」などと適宜表現される。前後関係から法 n が明らかな場合は法の表記を省略して単に ab と表記されることがある。

性質

同値律

n に関する合同という関係は以下の性質を満たす:

  • 反射律: 任意の整数 a に関して aa (mod n);
  • 対称律: 任意の整数の対 a, b に関して ab (mod n) ⇔ ba (mod n);
  • 推移律: 任意の整数の組 a, b, c に関して ab (mod n) かつ bc (mod n) ならば ac (mod n).

即ち法 n に関する合同という関係は同値関係である。

代数学的性質

特に踏まえておくべき代数学的性質は、a1b1 (mod n) かつ a2b2 (mod n) ならば

a1 + a2b1 + b2 (mod n),
a1a2b1b2 (mod n)

が成り立つことである。ここから ab (mod n) ならば任意の整数 c に対して a ± cb ± c (mod n) および acbc (mod n) であること、および正整数 q > 0 に対して aq ≡ bq (mod n) であることが容易に導ける。

これは法 n に関する合同関係がある意味で整数の加法および乗法と「両立する」ことを示すものであり、「法 n に関する合同は有理整数環 (Z, +, ・) の構造と両立する」と言い表す。これにより商集合 Z/nZ に合同算術の環を定義することができるようになる。

合同類環 Z/nZ

構成

先述の代数的性質は、法 n に関する加法と乗法において、加えたり掛けたりする数を法 n で合同な別の数に置き換えてもよいことを示している。これはつまり、法 n で合同な数すべてを一つのあつまり(同値類、合同類、剰余類)として扱えば、法 n に関する加法と乗法がこの類の代表元の取り方に依らずに定まるということになる。同じ類に属する整数は法 n で割った剰余がみな同じであるようなものたちであり、法 n で割った剰余のみに注目するのが自然である。つまり、集合 Zn あるいは Z/nZ を法 n で割った余りからなる n-元集合 { 1, 2, …, n − 1 } (あるいは単に 1, 2, …, n − 1} とも書く)として、加法と乗法をこの集合上で考えるのがよい。この集合を法 n に関する合同類環、剰余環[注釈 2]あるいは商環[注釈 3]と呼ぶ。

この集合上での加法と乗法は、整数に関する加法と乗法と同様に定義される:

  • 加法: 二つの剰余類 a, b に対して剰余類 a + b modulo n を割り当てる。理論的には整数の加法と異なる和であるから別の記号で表すべきであるかもしれないが、簡便さを保つために整数の和と同じ記号 "+" をそのまま使うことも多い。
    • 例えば法 6 に関する合同類環では 3 + 2 = 5 が整数の加法同様に成り立つが、4 + 26 で割った剰余が 0 に等しいから 4 + 2 = 0 が成り立つ。
  • 乗法: 二つの剰余類 a, b に対し、剰余類 a × b modulo n を割り当てる。これも同様に整数の乗算記号"×"をそのまま流用する。
    • 法 6 に関する合同類環では、整数の乗法同様に 2 × 2 = 4 が成り立つが、2 × 5 = 42 × 56 で割った剰余は 4 に等しい)や 2 × 3 = 0 などが成り立つ。

6 に関する加法と乗法を以下のような表にまとめることができる:

Z/6Z の加法表
+ 0 1 2 3 4 5
0 0 1 2 3 4 5
1 1 2 3 4 5 0
2 2 3 4 5 0 1
3 3 4 5 0 1 2
4 4 5 0 1 2 3
5 5 0 1 2 3 4
Z/6Z の乗法表
× 0 1 2 3 4 5
0 0 0 0 0 0 0
1 0 1 2 3 4 5
2 0 2 4 0 2 4
3 0 3 0 3 0 3
4 0 4 2 0 4 2
5 0 5 4 3 2 1

これら加法と乗法は、整数の集合 Z における加法と乗法に良く似た性質を持つ:

  • 加法は可換(足す順番を入れ替えられる)、結合的(三項の和は前二項を先に足してもあと二項を先に対しても結果は変わらない)で、単位元を持つ(0 を加えても変わらない)、各元が反数を持つ。
    • Z の加法と比べて異なる点もある。Z の加法では a の逆元 aa + (–a) = 0 を満たす元だが、法 n の合同類環では a + (n – a) = 0ana の和を n で割った剰余は 0)だから a の逆元は n – a である。ただし、法 n に関する合同において ana は同じ類に入る。a でなく na を選ぶのは、合同類の代表元を 0 から n − 1 の間の整数から常に選ぶことができるという利点があるからである。
  • 乗法も可換、結合的で、単位元を持つ(1 を掛けても変わらない)。また剰余類の加法に関して分配的である。

これらの性質を満足する集合は(単位的)環と呼ばれる。

簡約と合同方程式

Z では常に正当であるにも拘らず、合同類環 Z/nZ では必ずしも正当化されない操作の一つに、簡約(消約)がある。

  • 実際、等式 2a = 4Z で考えれば明らかに両辺を 2 で簡約して a = 2 が得られるが、法 6 で考えれば 2a = 42a6 で割った剰余が 4 であるということだから、a3 で割った剰余が 2 に等しいような類である。そのような a6 で割った剰余類の中では類 2 または類 5 が満たす。従って、2×2 ≡ 2×5 だがそれを簡約した 2 ≡ 5 は成立しない。

同様に、整数の演算では常に成り立っているのに Z/nZ 上では必ずしも成り立たない性質として、零積性質英語版「積が 0 に等しいならばいずれかの数が 0 に等しい」というものがある。

  • 実際、法 62 × 3 ≡ 0 だが 230 でない。つまり、環 Z/6Z整域でない。

こういった理由により、乗法を含む方程式を解くのは少々厄介である。

  • 方程式 x + 2 = 1Z/6Z 上で考えるなら、両辺に同じ量 4 を加えて x = 5 とすればよい (2 + 4 ≡ 0 [6] に注意);
  • 方程式 3x = 2Z/10Z 上で考えるとき、7 × 3 ≡ 1 に注意すれば 3x = 2x = 7 × 2 が同値であることが分かる(一方から他方へはそれぞれ両辺に 7 あるいは 3 を掛ければ変形できる)。故に方程式の解は 47 × 210 で割った剰余は 4)である。;
  • 方程式 2x = 3Z/10Z 上で解を持たない。また方程式 2x = 6 は二つの解 (38) を持つ。

未知数フランス語版 x の方程式 ax = bZ/nZ 上で一意な解を持つための必要十分条件は、an とが互いに素であることである。

x2a (mod n) の形の方程式の解は a および n の値に依存して 0 個、1 個、2 個の何れかになる。さらに詳細な結果が平方剰余の研究によって得られており、平方剰余の相互法則として知られている。

合同類環 Z/nZ の構成は環のイデアルによる商構成である。環 Z/nZ の代数的性質に関しては合同類環の項へ譲る。

冪とフェルマーの小定理

Z/nZ に乗法が定まるから、反復乗法としての冪を考察するのはまた自然である。剰余は n − 1 種類しかないのだから、自然数冪 ak の値もその n − 1 種類以外に取り得ず、何度も同じ値を取らねばならない。つまり、自然数 k および mak および am が法 n に関して同じ値となるようなものが存在する。冪 ak は再帰的に定められるから、剰余の値が既知のものとなれば直ちに、それ以降の値は循環的に同じ値をとるものと分かり、それ以上調べる必要は無くなる。

Z/7Z の冪 ak
1 2 3 4 5 6
k = 0 1 1 1 1 1 1
k = 1 1 2 3 4 5 6
k = 2 4 2 2 4 1
k = 3 1 6 1 6
k = 4 4 2
k = 5 5 3
k = 6 1 1 1 1 1 1
Z/15Z の冪
1 2 3 4 5 6 7 8 9 10 11 12 13 14
k = 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
k = 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14
k = 2 4 9 1 10 6 4 4 6 10 1 9 4 1
k = 3 8 12 5 13 2 9 3 7
k = 4 1 6 1 1 6 1
k = 5 3 12
k = 8 1 1 1 1 1 1 1 1

上記のように Z/7Z および Z/15Z での冪を書きならべてみると、前者に関してどの a に対しても7番目の a6 で全てが法 7 に関して 1 に合同となることが分かる。後者に関しては冪の値が 1 となることが 15 と互いに素であることに関係してくる。整数 815 と互いに素であり、15 と互いに素な a に対して a8 が法 15 に関して 1 と合同であることに注目せよ。

これら二つの例はそれぞれ以下の二つの定理に対応する:

  • フェルマーの小定理: 任意の素数 p と、 p と互いに素な整数 a に対し、ap−1 ≡ 1 (mod p);
  • オイラーの定理: フェルマーの小定理の拡張。2 以上の整数 nn と互いに素な整数 a に対して、aφ(n) ≡ 1 (mod n) が成り立つ。ただし、φ(n)オイラーの φ-函数1 から n までの整数のうち n と互いに素なものの数)である。

脚注

注釈

  1. ^ 「法に関して」を意味する modulo はラテン語で「測り」を意味する名詞 modulus奪格である。"modulo 12" と書けば、法 12 に準じて考えるという意味になる。ガウスは: secundum modulum という語を用いた。また、: Congru は一致するという意味の動詞 congruere の過去分詞形である。
  2. ^ 修飾語「剰余」(residual) は「余りの」という意味である
  3. ^ 「商」(quotient) は同値関係による商集合を指して用いられている

関連項目

外部リンク


合同式

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2021/12/31 08:29 UTC 版)

除法の原理」の記事における「合同式」の解説

詳細は「合同式」を参照 二つ整数 a, b に対し a − b が自然数 n の倍数であるとき、「a と b は n を法として合同である」といい、このような整数の関係を合同関係という。合同関係整数全体集合 Z における同値関係である。 a と b が n を法として合同であることを、「法 (modulus) によって」という意味のラテン語 "modulo" を用いて次の合同式で表す。 a ≡ b (modulo n) さらに、単語を "mod" に縮めて、よく次式のように表される。 a ≡ b (mod n) 例え2111 (mod 5) である。 合同式は、剰余注目して計算をする場合に便利である。実際整数 a に対して、0 ≤ m < n となる整数 m であって a ≡ m (mod n) となるものは a を n で割った剰余そのものであり、Z を合同関係類別した同値類は、剰余としばしば同一視される

※この「合同式」の解説は、「除法の原理」の解説の一部です。
「合同式」を含む「除法の原理」の記事については、「除法の原理」の概要を参照ください。

ウィキペディア小見出し辞書の「合同式」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ

「合同式」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「合同式」の関連用語

合同式のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



合同式のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
デジタル大辞泉デジタル大辞泉
(C)Shogakukan Inc.
株式会社 小学館
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの整数の合同 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaの除法の原理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS