数学、特に初等代数的整数論における合同算術（ごうどうさんじゅつ、; モジュラ計算）は、（剰余を持つ除法の意味で））自然数あるいは整数をある特定の自然数で割ったときの剰余に注目して、自然数あるいは整数に関する問題を解決する一連の方法の総称である。合同算術の起源は、一般にはガウスが著作『Disquisitiones Arithmeticae』を出版する1801年にまで遡れるものとされる。ガウスによる合同式（ごうどうしき、）を用いたこの新しい手法は、有名な平方剰余の相互法則を明らかにし、より抽象的な観点からウィルソンの定理などの定理の記述の簡素化に一役を買った。ガウスの研究は自然数を扱う整数論のみならず、代数学や幾何学といった数学のほかの主要な分野にまで影響を与えるものであった。この手法の基本は、「数それ自体」ではなくそれを別な数で割った（商がいくらになるかということは無視して）「剰余だけ」を考えるということにある。こういった考え方は何か特殊で高尚なものというようなものではなく、実際に日常生活においても時刻や角度といったものの計算や単位の換算などで、ちょっとした合同算術が特別な知識無くあるいは無意識に行われているのである。20世紀には、合同算術にまつわる状況は大きく様変わりをしている。計算機やウェブの普及に伴って情報セキュリティの観点からの暗号化アルゴリズムの開発や取り扱いといったような場面で古典的な合同算術に関する理論の工業的・商業的応用が頻繁に見られるようになった。1621年、クロード＝ガスパール・バシェ・ド・メジリアク はディオファントスの本『算術』をラテン語に翻訳し、そこに書かれていた問題について当時の（特にフランスの）数学者が興味を持つこととなる。ピエール・ド・フェルマー は多数の定理を残したが、中でも有名なものは大定理、二平方和定理、小定理の3つであろう。科学コミュニティがこの話題にこぞって取り組むなか、フェルマーは「平方数の和で立方数となるものを求めよ」という問いを発し、（“この問いが解決されることを望む。それがイングランド人でもガリア・ベルギー人でもケルト民でもなく、フランス・ナルボンヌの人の手で為されることを。”）と結んでいる。マラン・メルセンヌ は今日メルセンヌ素数と呼ばれる素数について研究した。フェルマーはメルセンヌに （“3, 5, 7, 17, 65537, ... が素数であるというのは基本的に正しいと思うのだが、だとするとそれはあなたの結果を含む驚異的なことなので、実に素晴らしい発見であるように思われる。”）と言っているが、これらの数は今ではフェルマー数と呼ばれ、フェルマーの言っていたこれらが全て素数となるだろうという予想は偽であることが知られている。ルネ・デカルト はそれらとは独立に研究を進め、素数の 8 を法とする剰余が 1 または 3 ならば、その素数は "x" + 2"y" の形に書けるということを示したこの手の問題については興味深い要素がふたつあった。フェルマー問題のいくつかは、続く18世紀に、大部分はオイラーの手で解かれていった。オイラーは二平方和問題の証明の過程で、いわゆるフェルマー数が常に素数となるわけではないことを示した。そういった成功とともに、オイラーはいくつかの誤りも犯しており、フェルマーの大定理の "n" = 3 の場合の証明に失敗している（彼の最初の証明は誤りである）。1782年には、新たな問題として平方剰余の相互法則が俎上に上がることになる。そして、アドリアン＝マリ・ルジャンドル により残りの問題も精力的に解かれていった。19世紀の初頭には、それまで数学者が用いていた大仕掛けな道具立て（手法や表記法）も、単純な原理を導入することによって徐々に必要なくなっていった。「二つの平方数の和で 4 を法とする剰余が 3 であるようなものは存在するか」という有名な 3 に対する二平方和問題を例に取ろう。証明の内容としては「"a" および "b" を二つの平方数とする。"a

出典:wikipedia