合同式

ファイル:Disqvisitiones-800.jpg

ガウスの "Disquisitiones Arithmeticae"（『算術の研究/整数論』）

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

ファイル:Clock group.svg

かんたんな時刻の計算は「時間」については 12 あるいは 24 を法とする、「分・秒」については 60 を法とする合同算術になっている。合同算術は恰も法 n を「周期」として循環あるいは回転しているかのようである。

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

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

合同関係と合同式

整数全体の成す環 Z においては、任意の整数 m と「法」(modulus) と呼ばれる自然数 n に対して

<math>m = qn + r\quad (0 \le r < n)</math>

を満たす「商」(quotient) とよばれる整数 q と「剰余」(residue) と呼ばれる整数 r が一意的に存在するという意味で「除法の原理」が成り立つ（Z はユークリッド環である）。

2つの整数 a, b について、a − b が自然数 n で割り切れるとき、あるいはおなじことだが a, b それぞれを自然数 n で割ったときの剰余が等しいとき、すなわち

<math>a = q_1 n + r,\quad b = q_2 n + r\quad(0\le r < n) \iff a-b = qn</math>

となる整数 q, q₁, q₂, r が存在するとき、2つの整数 a, b は「n を法として」、「法 n に関して」あるいは「法 n に対して」合同 (congruent modulo n) であるなどといい、

<math>a \equiv b\quad (\text{modulo }n),\quad a \equiv b \pmod{n},\quad a \equiv_n b</math>

などで表す。法 n に関して合同であるというのは、整数全体の成す集合 Z における関係であり、合同関係 (congruent relation) とも呼ばれる。法 n に関する合同関係を表す演算子で結ばれた式を合同式と総称する。

法 n に関する合同関係は

• 反射律: a ≡ a (mod n)
• 対称律: a ≡ b ならば b ≡ a (mod n)
• 推移律: a ≡ b かつ b ≡ c ならば a ≡ c (mod n)

という重要な性質を満足する。すなわち、n を法とする合同関係は、整数全体の成す集合 Z における同値関係である。また、a ≡ b (mod n), c ≡ d (mod n) かつ k と n が互いに素であるとき、

• 加減法: a ± c ≡ b ± d (mod n)
• 乗法: ac ≡ bd (mod n)
• 除法: ka ≡ kb (mod n) ならば a ≡ b (mod n)
  • もう少し一般に、k と n との最大公約数 d := (k, n) = g.c.d(k, n) が 1 でないときも含めて
    ka ≡ kb (mod n) ⇔ a ≡ b (mod n/d)

が成立するという意味で整数についての四則演算と両立する。ここから特に a ≡ b (mod n) ならば、k を整数、m が自然数として、

• 移項: a ± k ≡ b (mod n) ⇔ a ≡ b ∓ k (mod n)
• 整数係数多項式 f(X) ∈ Z[X] に対して f(a) ≡ f(b) (mod n);
  • 定数倍: ka ≡ kb (mod n)
  • 冪: a^m ≡ b^m (mod n)

といったような関係が満足されることもわかる。一方、少し込み入った条件を要する

• b^e ≡ b^f (mod n)

の形の関係式は、e ≡ f (mod φ(n)) かつ b が法 n に関する原始根（後述）であるならば成り立つ（離散対数を参照）。一般に、原始根に限らず b を mod n で任意に取るとき、

• 指数・対数: b^e ≡ b^f (mod n) となるのは e ≡ f (mod ord_n(b)) であるとき、かつそのときに限る。

ここで ord_n(b) は b の法 n に関する乗法的位数（後述）である。

剰余類と合同式の算術

法 n に関する合同関係による同値類のことを、n を法とする合同類 (congruence class) あるいは剰余類 (residue class)と呼ぶ。各剰余類は「n を法とする剰余」と一対一対応になるので、{0, 1, ..., n − 1} は完全代表系（各類から一つずつ代表元をとってきたもの）の一つになる。整数 k の属する法 n の剰余類を、しばしば

<math>k + (n),\quad k + n\mathbb{Z},\quad k\,\bmod\,n,\quad k\,\bmod(n),\quad k\,\bmod\,n\mathbb{Z}</math>

などで表す。あるいは同値類の代表的な記法に従って

<math>\bar{k},\quad[k],\quad [k]_n</math>

のように記すこともある。剰余と剰余類との対応から、これらの記法で剰余自体を表すこともある。また多くの場合に、剰余類に関する式をその代表元としての剰余の間の合同関係式であるものと読んでも意味を成す。

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

Z/nZ の単数、すなわち乗法に関する可逆元は n と互いに素な整数の属する合同類であり、それらは一般に n を法とする既約剰余類と総称され、その全体は既約剰余類群と呼ばれる群を成す。すなわち、

(Z/nZ)^× = {[k] | 1 ≤ k ≤ n, GCD(k, n) = 1}

であり、その位数はオイラー数 φ(n) である。したがって、群の一般論から、オイラーの定理が導かれる。(Z/nZ)^× の元 a の位数を ord_{n</sup> a などと表す。(Z/nZ)^× が巡回群であるのは、n が 2, 4, 奇素数の冪、奇素数の冪の2倍のいずれかのとき、またそのときに限る。その場合の生成元を法 n に関する原始根（原始元）と呼ぶ。}

n が m を割り切るとき、x mod m から法を取り換えて x mod n を作る操作によって Z/mZ から Z/nZ への写像が定義可能で全射環凖同型を与える。これを法の取り替えの定める自然な全射または標準射影という。特に、n が素数 p の自然数冪であるような剰余環 Z/nZ たち全体にそれらの間で考えうる自然な全射準同型たちを合わせて考えたものは射影系を成し、この射影系の射影極限

<math>\varprojlim_e \mathbb{Z}/p^e\mathbb{Z}</math>

は p-進整数環 Z_p となる。

歴史

ヨーロッパの怪物

ファイル:Pierre de Fermat.jpg

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

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 »（“この問いが解決されることを望む。それがイングランド人でもガリア・ベルギー人でもケルト民でもなく、フランス・ナルボンヌの人の手で為されることを。”）と結んでいる。

マラン・メルセンヌ (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 très belles choses en cette matière, car j'ai déjà trouvé des choses merveilleuses dont je vous ferai part »（“3, 5, 7, 17, 65537, ... が素数であるというのは基本的に正しいと思うのだが、だとするとそれはあなたの結果を含む驚異的なことなので、実に素晴らしい発見であるように思われる。”）と言っているが、これらの数は今ではフェルマー数と呼ばれ、フェルマーの言っていたこれらが全て素数となるだろうという予想は偽であることが知られている。ルネ・デカルト (1596 - 1650) はそれらとは独立に研究を進め、素数の 8 を法とする剰余が 1 または 3 ならば、その素数は x² + 2y² の形に書けるということを示した

この手の問題については興味深い要素がふたつあった。

人々がディオファントス方程式にいかに心奪われたかということは、バシェ・ド・メジリアクの本の一つの表題が "Problèmes plaisants et délectables qui se font par les nombres"（『数それ自身の成す喜ばしくもほほえましい問題』）であるということや、フェルマーが大定理について « J'ai trouvé une solution merveilleuse ... »（“驚くべき証明を発見した……”）と書き残していることなどにも顕れている。

簡単そうな問題が意外に難しい。おそらくバシェ・ド・メジリアクの手によってテンプレート:仮リンクのいくつかはうまく解かれたけれども、問題の本質的な部分に答えるようなものではなかったし、フェルマーの二平方和定理にしても答えをほとんど誰も理解できないもので、フェルマーの最終定理にしてもフェルマー自身が « ... mais la place me manque ici pour la développer »（“……しかしこの余白はそれを記すには狭すぎる”）という書き込みを残したのみであった（はじめてきちんとした証明が現れるのは1994年と1995年である)）。フェルマーはしばしば自身の失敗を自白するコメント « 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 même franchise ce que je ne sais pas) que je n'ai pu encore démontrer... cette belle proposition que je vous ai envoyée... »（“わたしは包み隠さず告白する（時代が進んで私の知らないよりたくさんのことが私に帰せられるに値する能力を私が有していないことを、同じく私が知らないということを脇において言う）私は再び証明することができなかったということを……この美しき命題をあなたに送る……”）で彼の定理を締めくくっている。

18世紀の数学

ファイル:Leonhard Euler 2.jpg

18世紀の数論家レオンハルト・オイラーはいくつも整数問題を解いている。

フェルマー問題のいくつかは、続く18世紀に、大部分はオイラーの手で解かれていった。オイラーは二平方和問題の証明の過程で、いわゆるフェルマー数が常に素数となるわけではないことを示した。そういった成功とともに、オイラーはいくつかの誤りも犯しており、フェルマーの大定理の n = 3 の場合の証明に失敗している（彼の最初の証明は誤りである）。1782年には、新たな問題として平方剰余の相互法則が俎上に上がることになる。そして、アドリアン＝マリ・ルジャンドル (1752 - 1833) により残りの問題も精力的に解かれていった。

19世紀の初頭には、それまで数学者が用いていた大仕掛けな道具立て（手法や表記法）も、単純な原理を導入することによって徐々に必要なくなっていった。「二つの平方数の和で 4 を法とする剰余が 3 であるようなものは存在するか」という有名な 3 に対する二平方和問題を例に取ろう。証明の内容としては「a² および b² を二つの平方数とする。a, b ともに偶数であるかともに奇数であればそれらの和の 4 を法とする剰余は 0 か 2 である。a が偶数で b が奇数とすると、偶数 a の平方は 4 の倍数であり、奇数 b は b = 2c + 1 と表せて、その平方は 4c² + 4c + 1 となるので、b² の 4 を法とする剰余は 1 となり、したがって所期の平方和の 4 を法とする剰余は 1 であるとわかる」といった感じであるが、ここでいくつかの道具立てが用いられている。

• 一つ目の道具は、ちょうどふたつの因数を持つものとしての素数である。
• 二つ目は、b を 2c + 1 と表すような「文字の置換え」である。適切に置換える文字を選ぶことによって、数学者はいくつもの整数問題を解決することができた。
• 三つ目は「除法の原理」であり、これによって平方や平方和を 4 で割ることが機械的・系統的に行える。
• 四つ目は例示には表れていないが、二平方和定理のオイラーによる証明に用いられた無限降下法である。これは「自然数解が在れば必ずそれよりも小さな自然数解があることを示すことで、そのような自然数解の存在が繰り返し示され、自然数からなる無限降下列が構成されることになるが、このようなことは不可能である」というものである。これはフェルマーの大定理の n = 4 の場合を証明するのに利用されている。

オイラーによる二平方和定理の証明にしたところで、古い伝統的な道具立てでは証明は長く技巧的なものにならざるを得ず、そのような方法では1世紀以上の努力を費やしてもフェルマーの整数問題を解決することはできなかったのである。

ガウスの貢献

ファイル:Carl Friedrich Gauss.jpg

合同算術の祖ガウス

17歳のガウス (1777 - 1855) は平方剰余の相互法則を示した。翌1796年3月30日、ガウスは17次の円分方程式を解くというきわめて算術的な研究の過程で、古来から未解決の幾何学的問題であった定規とコンパスによる正十七角形の作図が可能であることに気付く。最終的に1801年、ガウスは "Disquisitiones Arithmeticae"（『算術の研究』）を著して数学王子と渾名された。

これら二つの大きな発見は共に、フェルマーやオイラーが用いたような道具よりもより抽象的で明確な道具を用いて、証明に掛かる大きな負担を軽減するという過程のなかで為されており、その過程は合同算術として結実する。

ガウスは整数係数多項式をつかって整数概念の拡張を行い、今日ではガウス整数と呼ばれる数の集合を得ている。ディリクレ (1805 - 1859) も類似の整数の集合を発見しており（それはディリクレ整数と呼ばれる）、それを足がかりとしてフェルマーの大定理の n = 5 の場合を証明した。その論文は1825年に科学アカデミーに提出され、ルジャンドルの数ヶ月に亘る査読を受けた後に受理されている

そのころフェルマーの整数問題は、最終定理を除くすべてが解決されていたが、新しい予想も現われていた。たとえば、a と b が互いに素ならば初項 a で公差が b の等差数列のなかに素数は存在するか、存在するとしたらどのくらい含まれるか、というものである。ガウスやルジャンドルらの数学者は無限に存在するだろうと考えたが、平方剰余の相互法則と同様の高次の冪剰余に対する相互法則が必要であり、証明はできなかった。

その後も合同算術は発展を続け、ディリクレはディリクレ指標の概念や解析的数論の基礎を固めることによって算術級数定理を証明した。その証明は合同算術の珠玉ともいえるもので、ヤコビ (1804 - 1851) は兄弟への手紙に テンプレート:Quoteと記している。今では有限可換群上の調和解析から得られる道具を用いて証明することができるが、ルジャンドルはそういった道具は用いておらず、今ではルジャンドル記号と呼ばれる概念を定式化することにより、平方剰余の相互法則と同様の計算を実数に対して行うことで証明した。ガウスは1801年の著書で最終的にこの方法を複素数にまで拡張した。この計算は ガウス和とガウス周期と呼ばれる。

19世紀にはこれらの数学は超越数論と呼ばれ、算術 (arithmetic) という呼称もより一般の数学を指す言葉として残ったが、1830年にルジャンドルは、この十分に発展を遂げた分野を表すため、数論 (theory of numbers) という呼称を考案した。ガウスのころの算術とは異なる新しい手法が用いられるようになり、代数的数論と解析的数論という分科が現れるようになると、超越数論という呼称は超越数と共に過去のものとなっていった。

外部リンク

• テンプレート:MathWorld
• テンプレート:MathWorld

関連項目

• 冪剰余
• ペル方程式
• 中国の剰余定理