除法の原理

除法の原理（じょほうのげんり、）とは、「被除数と除数と呼ばれる二つの自然数に対して、商と剰余と呼ばれる二つの自然数が、与えられた性質を満たして一意に定まる」ことを示す算術における定理である。
たとえば、自然数 および 0 でない自然数 に対して、を満たす自然数 , の組がただ一つ存在することを示す。
除法の原理に基づき、自然数や整数に対する剰余付き除法（じょうよつきじょほう、）を定義できる。剰余付き除法はユークリッド除法（ユークリッドじょほう、）、整除法（せいじょほう、）とも呼ばれる。
剰余付き除法の商と剰余を求めるアルゴリズムが知られている。たとえば長除法は十進記数法（あるいは任意の位取り記数法）で表された整数に対するアルゴリズムである。
整数に対する除法の原理は、初等算術における定理の基盤であり、二整数の最大公約数を求めるユークリッドの互除法のような他の算法や整数の間のある種の合同関係を定める合同算術などに対する重要な要件になっている。
剰余付き除法は多項式などに対しても定義することができる。適当な意味において「被除数と非零除数が与えられたとき商と剰余が存在して剰余は除数よりも小さくできる」という「除法の原理」は、抽象代数学においても余り付き割り算の定義されるもっとも一般の数学的構造としてのユークリッド環に定義要件として明示的に要請される条件である。
算術における応用.
合同式.
二つの整数 "a", "b" に対し "a" − "b" が自然数 "n" の倍数であるとき、「"a" と "b" は "n" を法として合同である」といい、このような整数の関係を合同関係という。合同関係は整数全体の集合 Z における同値関係である。
"a" と "b" が "n" を法として合同であることを、「法 (modulus) によって」という意味のラテン語 "modulo" を用いて、次の合同式で表す。
さらに、単語を "mod" に縮めて、よく次式のように表される。
例えば 21 ≡ 11 (mod 5) である。
合同式は、剰余に注目して計算をする場合に便利である。実際、整数 "a" に対して、0 ≤ "m" < "n" となる整数 "m" であって "a" ≡ "m" (mod "n") となるものは "a" を "n" で割った剰余そのものであり、Z を合同関係で類別した同値類は、剰余としばしば同一視される。
剰余演算.
自然数 "n" を固定して、整数 "m" を "n" で割ったとき、その剰余はただ一つに定まるから、剰余計算を二項演算の一種と見ることもできる。剰余を求める演算の演算子として "mod" が用いられ、次のように書く。
一部のプログラミング言語（C言語など）では "%" を用いて、"m" % "n" と書く。"n" が正のとき、剰余演算の結果は、0 以上 "n" 未満である。例えば、7 mod 5 = 2 であり、−7 mod 5 = 3 である。
余りが等しいことを意味する等式
は、合同式 "a" ≡ "b" (mod "n") と解釈することもできる。
剰余演算は、日常レベルからRSA暗号などの計算機科学までの幅広い分野で利用される。
展開.
整数 "n" > 1 を一つ選び固定するとき、任意の整数 "m" は "n" の冪乗 "n""k" ("k" ≥ 0) に関する剰余の列 ("m" mod "n""k")"k"=0,1,2... によって一意的に特定することができる。具体的には、"m" に対して "n""k"+1 を法とする剰余から "n""k" を法とする剰余を引いたものは "n""k" で割り切れるので、これを "a""k""n""k"とすれば、0 ≤ "a""k" < "n" かつ、十分大きな "k" についてはすべて "a""k" = 0 となる。つまり適当な自然数 "M" が存在して
と書くことができて、しかもこのような表示は一意的であるということである。これを、整数 "m" の "n" を法とする展開、あるいは "n"-進展開と呼び、はじめに固定した "n" を展開の基数と呼ぶ。この展開は位取り記数法などの記法の原理的な根拠となる。
十分大きな "k" についてはすべて "a""k" = 0 となるという制限は、基数が素数 "p" であるときには "p"-進距離に関する収束の概念を用いて除くことができて、 "p"-進整数の "p"-進展開を与える。また、絶対値の導く距離を入れ、基数 "n" の負の冪をも同時に考えるならば有理数や実数の "n"-進展開（小数展開）を考えることができる。
ユークリッド環.
整数全体の成す環 Z、体 "K" 上の一変数多項式環 "K"["x"] やガウスの整数環 Z[√−1] などで次の除法の原理が成り立つ。
例えば、整数環 Z の場合に、 "W" = N（0 を含む自然数全体の集合）, "N"("a") = |"a"| （絶対値）ととればユークリッド整域の条件が満たされる。このような性質を持つ整域 "R" を一般にユークリッド整域という。剰余はユークリッド整域において定義される概念である。