数学、特に初等代数的整数論における合同算術（ごうどうさんじゅつ、英: 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]。