数学、特に初等代数的整数論における合同算術（ごうどうさんじゅつ、英: modular arithmetic; モジュラ計算）は、（剰余を持つ除法の意味で））自然数あるいは整数をある特定の自然数で割ったときの剰余に注目して、自然数あるいは整数に関する問題を解決する一連の方法の総称である。合同算術の起源は、一般にはガウスが著作『Disquisitiones Arithmeticae』を出版する1801年にまで遡れるものとされる。ガウスによる合同を用いたこの新しい手法は、有名な平方剰余の相互法則を明らかにし、より抽象的な観点からウィルソンの定理などの定理の記述の簡素化に一役を買った[注釈 1]。ガウスの研究は自然数を扱う整数論のみならず、代数学や幾何学といった数学のほかの主要な分野にまで影響を与えるものであった。 かんたんな時刻の計算は「時間」については 12 あるいは 24 を法とする、「分・秒」については 60 を法とする合同算術になっている。合同算術はあたかも法 n を「周期」として循環あるいは回転しているかのようである。

この手法の基本は、「数それ自体」ではなくそれを別な数で割った（商がいくらになるかということは無視して）「剰余だけ」を考えるということにある。こういった考え方は何か特殊で高尚なものというようなものではなく、実際に日常生活においても時刻や角度といったものの計算や単位の換算などで、ちょっとした合同算術が特別な知識無くあるいは無意識に行われているのである。

20世紀には、合同算術にまつわる状況は大きく様変わりをしている。計算機やウェブの普及に伴って情報セキュリティの観点からの暗号化アルゴリズムの開発や取り扱いといったような場面で古典的な合同算術に関する理論の工業的・商業的応用が頻繁に見られるようになった。
目次

1 歴史

1.1 ヨーロッパの怪物

1.2 18世紀の数学

1.3 ガウスの貢献

1.4 20世紀の合同算術

1.4.1 暗号理論

1.4.2 情報理論



2 合同算術の道具立て

2.1 整数の合同

2.2 多項式の割り算

2.3 代数的整数

2.4 ディリクレ指標


3 理論の展開

3.1 商構造

3.2 多項式の割り算とガロワ理論

3.3 代数的整数と代数的整数論

3.4 ディリクレ指標と解析数論


4 暗号理論

4.1 非対称暗号

4.2 対称暗号

4.3 素数判定

4.4 積の素因数分解

4.5 有限体

4.6 有限アーベル群上の調和解析


5 誤り訂正符号

5.1 チェックサム

5.2 巡回符号

5.3 マクウィリアムス恒等式


6 注

6.1 注釈

6.2 出典


7 参考文献

8 関連項目

9 外部リンク

歴史
ヨーロッパの怪物 ピエール・ド・フェルマーは算術を発展させた。合同算術の基礎となる剰余をもつ除法は、フェルマーによって既に用いられていた。

1621年、クロード＝ガスパール・バシェ・ド・メジリアク (1581 - 1638) はディオファントスの本『算術』をラテン語に翻訳し、そこに書かれていた問題について当時の（特にフランスの）数学者が興味を持つこととなる。ピエール・ド・フェルマー (1607 - 1665) は多数の定理を残したが、中でも有名なものは大定理、二平方和定理、小定理の3つであろう。科学コミュニティがこの話題にこぞって取り組むなか、フェルマーは「平方数の和で立方数となるものを求めよ」という問いを発し、≪ j'attends la solution de ces questions; si elle n'est fournie ni par l'Angleterre, ni par la Gaule Belgique ou Celtique, elle le sera par la Narbonnaise ≫（“この問いが解決されることを望む。それがイングランド人でもガリア・ベルギー人でもケルト民でもなく、フランス・ナルボンヌの人の手で為されることを。”）と結んでいる[1]。

マラン・メルセンヌ (1588 - 1648) は今日メルセンヌ素数と呼ばれる素数について研究した。フェルマーはメルセンヌに ≪ Si je puis une fois tenir la raison fondamentale que 3, 5, 7, 17, 257, 65537, …, sont nombres premiers, il me semble que je trouverai de tres belles choses en cette matiere, car j'ai deja trouve des choses merveilleuses dont je vous ferai part ≫（“3, 5, 7, 17, 65537, ... が素数であるというのは基本的に正しいと思うのだが、だとするとそれはあなたの結果を含む驚異的なことなので、実に素晴らしい発見であるように思われる。”）と言っている[2]が、これらの数は今ではフェルマー数と呼ばれ、フェルマーの言っていたこれらが全て素数となるだろうという予想は偽であることが知られている。ルネ・デカルト (1596 - 1650) はそれらとは独立に研究を進め、素数の 8 を法とする剰余が 1 または 3 ならば、その素数は x2 + 2y2 の形に書けるということを示した

この手の問題については興味深い要素がふたつあった。人々がディオファントス方程式にいかに心奪われたかということは、バシェ・ド・メジリアクの本の一つの表題が "Problemes plaisants et delectables qui se font par les nombres"（『数それ自身の成す喜ばしくもほほえましい問題』）であるということや、フェルマーが大定理について ≪ J'ai trouve une solution merveilleuse ... ≫（“驚くべき証明を発見した……”）と書き残している[3]ことなどにも顕れている。簡単そうな問題が意外に難しい。おそらくバシェ・ド・メジリアクの手によってベズーの等式のいくつかはうまく解かれたけれども、問題の本質的な部分に答えるようなものではなかったし、フェルマーの二平方和定理にしても答えをほとんど誰も理解できないもので、フェルマーの最終定理にしてもフェルマー自身が ≪ ... mais la place me manque ici pour la developper ≫（“……しかしこの余白はそれを記すには狭すぎる”）という書き込みを残したのみであった（はじめてきちんとした証明が現れるのは1994年と1995年である[4])）。フェルマーはしばしば自身の失敗を自白するコメント ≪ Je vous avoue tout net (car par avance je vous avertis que je ne suis pas capable de m'attribuer plus que je ne sais, je dis avec la meme franchise ce que je ne sais pas) que je n'ai pu encore demontrer... cette belle proposition que je vous ai envoyee... ≫（“わたしは包み隠さず告白する（時代が進んで私の知らないよりたくさんのことが私に帰せられるに値する能力を私が有していないことを、同じく私が知らないということを脇において言う）私は再び証明することができなかったということを……この美しき命題をあなたに送る……”）で彼の定理を締めくくっている[5]。
18世紀の数学 18世紀の数論家レオンハルト・オイラーはいくつも整数問題を解いている。

フェルマー問題のいくつかは、続く18世紀に、大部分はオイラーの手で解かれていった。オイラーは二平方和問題の証明の過程で、いわゆるフェルマー数が常に素数となるわけではないことを示した[6]。そういった成功とともに、オイラーはいくつかの誤りも犯しており、フェルマーの大定理の n = 3 の場合の証明に失敗している（彼の最初の証明[7]は誤りである）。