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