この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。
出典を追加して記事の信頼性向上にご協力ください。（2012年5月）

数学の特に算術において、自然数や整数に対する通常の剰余付き除法（じょうよつきじょほう、英: division with remainder; 余りのある割り算）は、ユークリッド除法（ユークリッドじょほう、英: Euclidean division）または整除法（せいじょほう、英: entire division）とも呼ばれ、「被除数と除数と呼ばれる二つの自然数に対して、商と剰余と呼ばれる二つの自然数が、与えられた性質を満たして一意的に存在する」ことを主張する定理として明確に規定することができる。このような定理を「除法の原理」（じょほうのげんり、division algorithm; 除法の算法）という。即ち、その主張は「二つの自然数 n および m ≠ 0 に対してある自然数 a および b が存在して n = am + b (0 ≤ b < m) が成立する」というもので、自然数 a および b 自身は上記の除法を通じて決定される。

そのような商と剰余を効果的に導く手続きを指して除法の原理あるいは「除法の算法」（除法アルゴリズム）と呼ぶこともある。整数を十進記数法（あるいは任意の位取り記数法）で表せば、長除法はよく知られた効果的な除法の算法であり、ほかにも同様の算法が知られている。整数に対する除法の原理は、初等算術における定理の基盤であり、二整数の最大公約数を求めるユークリッドの互除法のような他の算法や整数の間のある種の合同関係を定める合同算術などに対する重要な要件になっている。

ユークリッド式の除法（余りのある割り算）は多項式などに対しても定義することができる。適当な意味において「被除数と非零除数が与えられたとき商と剰余が存在して剰余は除数よりも小さくできる」という「除法の原理」は、抽象代数学においても余り付き割り算の定義されるもっとも一般の数学的構造としてのユークリッド環に定義要件として明示的に要請される条件である。
目次

1 自然数に対する除法の原理

2 整数に対する除法の原理

3 算術における応用

3.1 互除法

3.2 合同式

3.3 剰余演算

3.4 展開


4 多項式に対する除法の原理

5 ユークリッド環

6 関連項目

7 外部リンク

自然数に対する除法の原理
主張
与えられた二つの自然数 n および m ≠ 0 に対して、n = am + b (b < m) が成立するような自然数 a および b が一意的に存在する
存在性

一意性

整数に対する除法の原理
主張1
与えられた二つの整数 n および m ≠ 0 に対して、n = am + b (0 ≤ b < |m|) が成立するような整数 a および b が一意的に存在する
存在性

一意性

主張2
与えられた二つの整数 n および m ≠ 0 に対して、n = am + b (|b。< |m|) が成立するような整数 a および b が存在する
剰余の取り方に関する注意
一般に、剰余の一意性には注意が必要である。一意性が保障されない簡単な例として、a = 7, b = ?3 とすると7 = (?2)(?3) + 17 = (?3)(?3) ? 2と 2 通りに分解することができて、確かに |1。< |?3。も |?2。< |?3。も成り立っている。一意性を与える付帯条件のつけ方は一通りではない。たとえば、「被除数が負であるときは、被除数と絶対値が等しい自然数をとり、そちらを割算してから改めて符号を付け替える」 というような流儀も存在して、これも広く用いられている。計算機においては、負の数の表現方法にも因る話であるので、プログラムに剰余計算をさせるときなどは注意が必要である。自然数の場合にはこのような混乱は生じない。
算術における応用
互除法詳細は「ユークリッドの互除法」を参照
合同式詳細は「合同式」を参照

二つの整数 a, b に対し a ? b が自然数 n の倍数であるとき、a, b は n を法として合同であるといい、このような整数の関係を合同関係という。合同関係は整数全体の集合 Z における同値関係である。これを「法 (modulus) を用いて」という意味のラテン語 "modulo" からしばしば a ≡ b (mod n) などのように表す。例えば 21 ≡ 11 (mod 5) である。

合同式は剰余に注目して計算をする場合に便利である。実際、整数 a に対して、0 ? m < n となる整数 m で a ≡ m (mod n) となるものは a を n で割った剰余そのものであり、Z を合同関係で類別した同値類は剰余としばしば同一視される。
剰余演算「剰余演算」も参照

自然数 n を固定して、整数 m を n で割ったとき、その剰余はただ一つに定まるから、剰余計算を二項演算の一種と見ることもできる。剰余を求める演算の演算子として "mod" が用いられ、次のように書く。

m mod n

mod(m, n)

一部のプログラミング言語（C言語など）では "%" を用いて、m % n と書く。n が正のとき、剰余演算の結果は、0 以上 n 未満である。例えば、7 mod 5 = 2 であり、-7 mod 5 = 3 である。

余りが等しいことを意味する等式

a mod n = b mod n

は、合同式 a ≡ b (mod n) と解釈することもできる。

剰余演算は、日常レベルからRSA暗号などの計算機科学までの幅広い分野で利用される。
展開

整数 n > 1 を一つ選び固定するとき、任意の整数 m は n の冪乗 nk (k ? 0) に関する剰余の列 (m mod nk)k=0,1,2,... によって一意的に特定することができる。具体的には、m に対して nk+1 を法とする剰余から nk を法とする剰余を引いたものは nk で割り切れるので、これを aknkとすれば、0 ? ak < n かつ、十分大きな k についてはすべて ak = 0 となる。つまり適当な自然数 M が存在して m = a 0 + a 1 n + a 2 n 2 + ⋯ + a M n M {\displaystyle m=a_{0}+a_{1}n+a_{2}n^{2}+\cdots +a_{M}n^{M}}