ユークリッドの除算

算術において、ユークリッド除算（または余り付き除算）とは、ある整数（被除数）を別の整数（除数）で割り、除数の絶対値よりも確実に小さい整数の商と自然数の余りを生成する処理です。基本的な特性として、商と余りは、ある条件下では一意に存在します。この一意性のため、ユークリッド除算は、計算方法を参照せず、商と余りを明示的に計算せずに検討されることがよくあります。計算方法は整数除算アルゴリズムと呼ばれ、最もよく知られているのは長除算です。

ユークリッド除算とその計算アルゴリズムは、2つの整数の最大公約数を求めるユークリッドの互除法^[1]や、剰余のみを考慮するモジュラー演算^{[2]など、整数に関する多くの問題の基礎となる。剰余のみを計算する演算は}モジュロ演算^[3]と呼ばれ、数学とコンピュータサイエンスの両方で頻繁に使用される。

ユークリッドの除算は、ユークリッドの除算の補題 と呼ばれることもある次の結果に基づいています。

2つの整数aとb （b ≠ 0）が与えられたとき、次の式を 満たす一意の整数qとrが存在する。

a = bq + r

そして

0 ≤ r < | b |、

ここで| b |はbの絶対値を表す。^[4]

上記の定理では、4 つの整数それぞれに名前があります。aは被除数、bは除数、 qは商、 rは余りと呼ばれます。

被除数と除数から商と剰余を計算することを除算、またはあいまいな場合はユークリッド除算と呼びます。この定理は、除算アルゴリズムと呼ばれることがよくあります(定理であってアルゴリズムではありませんが)。これは、以下に示す証明が、 qとr を計算するための単純な除算アルゴリズムに役立つためです(詳細については、「証明」のセクションを参照してください)。

b = 0の場合、除算は定義されません。ゼロ除算を参照してください。

剰余とモジュロ演算については、 0 ≤ r < | b |以外の規則があります。§ 剰余のその他の間隔を参照してください。

ユークリッドの除算と除算定理は、もともと整数に限定されていましたが、体上の一変数多項式やユークリッド領域に一般化できます。

一変数多項式の場合、主な違いは不等式が次のように置き換えられる ことです。${\displaystyle 0\leq r<|b|}$

${\displaystyle r=0}$または${\displaystyle \deg r<\deg b,}$

ここで は多項式の次数を表します。 ${\displaystyle \deg}$

ユークリッド領域への一般化では、不等式は次のようになる。

${\displaystyle r=0}$または${\displaystyle f(r)<f(b),}$

ここで、定義域から自然数への特定の関数、つまり「ユークリッド関数」を表します。 ${\displaystyle f}$

商と剰余の一意性は多項式では真のままですが、一般には誤りです。

「ユークリッドの除算」はユークリッドにちなんで名付けられているが、ユークリッドは存在定理や一意性定理を知らず、唯一知っていた計算法は繰り返し減算による除算だったと思われる。^[要出典]

13 世紀にヨーロッパでフィボナッチによって導入されたヒンドゥー・アラビア数字システムが発見される前は、割り算は非常に難しく、最高の数学者しか実行できませんでした。現在、長除算を含むほとんどの除算アルゴリズムは、この表記法またはその変形 ( 2 進数表記など) に基づいています。注目すべき例外はニュートン・ラプソン除算で、これはどの記数システムにも依存しません。

「ユークリッド除算」という用語は、20 世紀に「ユークリッド環の除算」の省略形として導入されました。この除算を他の種類の数の除算と区別するために、数学者によって急速に採用されました。 ^{[引用が必要]}

パイが 9 切れあり、それを 4 人で均等に分けるとします。ユークリッドの除算を使用すると、9 を 4 で割ると 2 余り 1 になります。つまり、各人がパイを 2 切れ​​受け取り、1 切れが余ることになります。

これは、割り算の逆である掛け算を使って確認できます。4 人それぞれが 2 枚ずつ受け取った場合、合計で 4 × 2 = 8 枚のスライスが配られたことになります。残りの 1 枚を加えると、結果は 9 枚になります。まとめると、9 = 4 × 2 + 1 です。

一般に、スライスの数が で表され、人数が で表されている場合、各人がスライス（商）を受け取り、いくつかのスライスが残り（剰余）となるように、パイを人々の間で均等に分割することができます。その場合、式は成り立ちます。 ${\displaystyle a}$${\displaystyle b}$${\displaystyle q}$${\displaystyle r<b}$${\displaystyle a=bq+r}$

9 枚のスライスを 4 人ではなく 3 人で分けた場合、各人が 3 枚ずつ受け取り、余りのスライスはないため、余りは 0 となり、3 は9 を均等に割り切れる、または 3 は9 を割り切れるという結論に至ります。

ユークリッド除算は、同じ公式を使用して負の被除数（または負の除数）に拡張することもできます。たとえば、-9 = 4 × (-3) + 3 は、-9 を 4 で割ると -3 になり、余りは 3 になることを意味します。

• a = 7、b = 3の場合、 7 = 3 × 2 + 1 なので、 q = 2、r = 1 となります。
• a = 7、b = −3の場合、7 = −3 × (−2) + 1 なので、 q = −2、r = 1 となります。
• a = −7、b = 3の場合、−7 = 3 × (−3) + 2 なので、 q = −3、r = 2 となります。
• a = −7、b = −3の場合、 −7 = −3 × 3 + 2 なので、 q = 3、r = 2 となります。

除算定理の次の証明は、非負整数の減少する数列が最終的に停止するという事実に依存しています。これは、存在の証明と および の一意性の証明の 2 つの部分に分かれています。他の証明では、整列原理(つまり、非負整数の空でないすべての集合には最小の要素があるという主張) を使用して推論を簡素化していますが、除算を解くアルゴリズムを直接提供しないという欠点があります (詳細については § 有効性を参照)。^[5]${\displaystyle q}$${\displaystyle r}$

ユークリッド除算の存在を証明するには、等式 を書き直すことができるので、後者の等式がユークリッド除算であり、前者もユークリッド除算である場合、と仮定することができます。 ${\displaystyle b>0,}$${\displaystyle b<0,}$${\displaystyle a=bq+r}$${\displaystyle a=(-b)(-q)+r.}$${\displaystyle -b>0,}$

およびが存在する場合、たとえば、およびが存在する場合、およびそれ以外の場合、および${\displaystyle b>0}$${\displaystyle a,}$${\displaystyle q_{1}}$${\displaystyle r_{1}\geq 0}$${\displaystyle a=bq_{1}+r_{1};}$${\displaystyle q_{1}=0}$${\displaystyle r_{1}=a}$${\displaystyle a\geq 0,}$${\displaystyle q_{1}=a}$${\displaystyle r_{1}=a-ab.}$

とを、が非負かつ最小となるような数のペアとします。ユークリッドの除算が成り立つとします。したがって、であればは最小ではないことを証明する必要があります。実際、とが最小でない 場合、${\displaystyle q}$${\displaystyle r}$${\displaystyle r}$${\displaystyle r<b.}$${\displaystyle r\geq b,}$${\displaystyle r}$${\displaystyle r\geq b,}$${\displaystyle a=b(q+1)+(rb),}$${\displaystyle 0\leq rb<r,}$${\displaystyle r}$

これは、すべての場合において存在を証明します。これは、 （ の場合）から始めて、まで加算することで商と剰余を計算するアルゴリズムも提供します。ただし、このアルゴリズムは、ステップ数が次のオーダーであるため効率的ではありません。${\displaystyle q=0}$${\displaystyle a\geq 0}$${\displaystyle 1}$${\displaystyle a-bq<b.}$${\displaystyle a/b}$

a = bq + rとなる整数rとqのペアは、ユークリッドの除算定理において同じ条件を満たす他の整数のペアは存在しないという意味で、唯一である。言い換えれば、aをbで割る別の方法、例えばa = bq' + r'（0 ≤ r' < | b |）がある場合、次の式が成り立つ。

q' = qかつr' = rです。

この主張を証明するために、まずは次のような仮定から始める。

0 ≤ r < | b |

0 ≤ r' < | b |

a = bq + r

a = bq' + r'

2つの式を減算すると、

b ( q – q ′ ) = r ′ – rです。

つまり、bはr′- rの約数である。

| r ′ – r | < | b |

上記の不等式により、

r ′ – r = 0、

そして

b ( q – q ′ ) = 0 です。

b ≠ 0なので、 r = r ′およびq = q ′となり、ユークリッドの除算定理の一意性の部分が証明されます。

一般に、存在証明は存在する商と剰余を計算するアルゴリズムを提供しませんが、上記の証明は、商のサイズと同じ数のステップを必要とするためあまり効率的ではないものの、すぐにアルゴリズムを提供します（除算アルゴリズム#繰り返し減算による除算を参照）。これは、乗算や10進表記などの整数の特定の表現を含まず、整数の加算、減算、比較のみを使用するという事実に関連しています。

10進表記法では、長除算はユークリッド除算を解くためのはるかに効率的なアルゴリズムを提供します。これを2進表記法や16進表記法に一般化することで、コンピュータ実装の柔軟性と可能性がさらに高まります。ただし、入力が大きい場合は、ニュートン・ラプソン法などの除算を乗算に簡略化するアルゴリズムが通常好まれます。これは、使用する乗算アルゴリズムとは無関係に、結果を検証するために必要な乗算の時間に比例する時間しかかからないためです (詳細については、除算アルゴリズム#高速除算法を参照してください)。

ユークリッドの分割にはさまざまなバリエーションがあり、そのいくつかを以下に示します。

d を除数とするユークリッド除算では、剰余は長さ| d |の区間 [0, d )に属するものとされます。同じ長さの任意の他の区間を使用できます。より正確には、整数、、およびが与えられた場合、となる一意の整数およびが存在します。 ${\displaystyle m}$${\displaystyle a}$${\displaystyle d}$${\displaystyle m>0}$${\displaystyle q}$${\displaystyle r}$${\displaystyle d\leq r<m+d}$${\displaystyle a=mq+r}$

特に、の場合には となります。この除算は中心除算と呼ばれ、その余りは中心剰余または最小絶対剰余と呼ばれます。${\displaystyle d=-\left\lfloor {\frac {m}{2}}\right\rfloor }$${\displaystyle -\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor }$${\displaystyle r}$

これは実数を近似するために使用されます。ユークリッド除算は切り捨てを定義し、中心除算は丸めを定義します。

整数、およびが与えられ、が のモジュラー逆数（つまりがの倍数）であるとすると、となる一意の整数およびが存在する。この結果はヘンゼルの奇除法（1900）を一般化したものである。^[6]${\displaystyle a}$${\displaystyle m}$${\displaystyle R,}$${\displaystyle m>0}$${\displaystyle \gcd(R,m)=1,}$${\displaystyle R^{-1}}$${\displaystyle R}$${\displaystyle 0<R^{-1}$${\displaystyle R^{-1}R-1}$${\displaystyle m}$${\displaystyle q}$${\displaystyle r}$${\displaystyle 0\leq r<m}$${\displaystyle a=mq+R^{-1}\cdot r}$

この値は、モンゴメリ還元で定義されたN剰余です。 ${\displaystyle r}$

ユークリッド領域（ユークリッド環とも呼ばれる）^[7]は、ユークリッドの除算の次の一般化をサポートする 整域として定義されます。

ユークリッド関数d （ユークリッド評価^[8]または次数関数^[7]とも呼ばれる）を備えたユークリッド領域R内の元aと非ゼロ元bが与えられた場合、 Rにはa = bq + rかつr = 0またはd ( r )< d ( b )となるqとrが存在する。

qとrの一意性は要求されない。^[1]これは例外的な場合にのみ発生し、典型的には単変数多項式の場合、および整数の場合は、さらにr ≥ 0という条件が追加された場合にのみ発生する。

ユークリッド領域の例としては、体、体上の 1 変数の多項式環、ガウス整数などがあります。多項式のユークリッド分割は、特定の開発の対象となってきました。

• ユークリッドの補題
• ユークリッドの互除法

• ジョン B. フレイリー (1993)、抽象代数の第一コース(第 5 版)、Addison-Wesley、ISBN 978-0-201-53467-2
• ロットマン、ジョセフ・J.（2006）、応用付き抽象代数入門（第3版）、Prentice-Hall、ISBN 978-0-13-186267-8