ユークリッド分割

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

単変数多項式の場合、主な違いは不等式が${\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}$定義域から自然数への特定の関数を表すもので、「ユークリッド関数」と呼ばれる。

商と剰余の一意性は多項式においては依然として成り立つが、一般には成り立たない。

ユークリッド除法の存在を証明するために、次のように仮定することができる。${\displaystyle b>0,}$なぜなら、もし${\displaystyle b<0,}$平等 ${\displaystyle a=bq+r}$書き換え可能${\displaystyle a=(-b)(-q)+r.}$したがって、後者の等式がユークリッド除法である場合、${\displaystyle -b>0,}$前者もまたユークリッド分割である。

与えられた${\displaystyle b>0}$そして${\displaystyle a,}$整数が存在する$q_1$そして$\displaystyle r_{1}\geq 0$そのため${\displaystyle a=bq_{1}+r_{1};}$例えば、$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,}$1つは${\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}$

整数のペア${\displaystyle r}$そして${\displaystyle q}$そのため${\displaystyle a=bq+r}$これは、ユークリッド除法の定理において同じ条件を満たす整数のペアが他に存在しないという意味で、唯一無二です。言い換えれば、別の除法があれば、${\displaystyle a}$による${\displaystyle b}$、 言う${\displaystyle a=bq'+r'}$と${\displaystyle 0\leq r'<|b|}$それならば、私たちはそれを持っていなければならない

${\displaystyle q'=q{\text{ および }}r'=r}$。

この主張を証明するために、まず以下の仮定から始めます。

${\displaystyle 0\leq r<|b|}$

${\displaystyle 0\leq r'<|b|}$

${\displaystyle a=bq+r}$

${\displaystyle a=bq'+r'}$

2つの式を引くと

${\displaystyle b(qq')=r'-r}$。

それで${\displaystyle b}$はの約数です${\displaystyle r'-r}$。 として

${\displaystyle |r'-r|<|b|}$

上記の不等式により、

${\displaystyle r'-r=0}$、

そして

${\displaystyle b(qq')=0}$。

以来${\displaystyle b\neq 0}$私たちはそれを理解しています${\displaystyle r=r'}$そして${\displaystyle q=q'}$これは、ユークリッド除法の定理の一意性の部分を証明するものである。

除数を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}$これは中心化された剰余または最小絶対剰余と呼ばれます。

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

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

価値${\displaystyle r}$はモンゴメリー還元で定義されるN残基である。

• ジョン B. フレイリー (1993)、抽象代数の第一コース(第 5 版)、アディソン・ウェスリー、ISBN 978-0-201-53467-2
• ロトマン、ジョセフ・J. (2006)、『応用を伴う抽象代数学入門』（第3 版）、プレンティス・ホール、ISBN 978-0-13-186267-8