導入
数学、より正確には算術において、ユークリッド除算または整数除算は、被除数と除数と呼ばれる 2 つの自然整数に、商と剰余と呼ばれる 2 つの整数を関連付ける演算です。最初は 2 つの非ゼロの自然整数に対して定義されましたが、たとえば相対的な整数や多項式に一般化されます。
この除算は、整数の合同式を生成するモジュラー算術の定理など、 初等算術の定理の基礎となっています。
定義
正の整数でのユークリッド除算
正の整数に対するユークリッドの除算定理は次のように述べられています。すべての正の整数aおよびb (bが 0 ではない) に対して、関係a=bq+rが検証されるような整数qおよびrの一意のペアが存在します。 r は広義には0とb-1の間です。整数q はaをbで割った商と呼ばれ、この除算で得られる整数rが残ります。
aとb を2 つの正の整数とし、 bはゼロではありません。
- 存在
次のように定義される集合E を考えてみましょう。
- $$ {E = \left\{ x \in \mathbb{N}\quad | \quad \exist z \in \mathbb{N}\, x = a – bz\right\}} $$
Eには が含まれるため、空ではありません。 E はNの空でない部分であるため、公理によりEの最小値が存在します。 r がこの最小値であり、 qがそれを定義する整数、つまりa – bが等しいことを検証する整数であることに注意してください。 q = r 、構造上、 r は自然数です。整数r – b はEの要素になることができないため、厳密に負の値になります。これは、 rが厳密にbより小さいことを示します。そこで存在が証明される。
- 独自性
相対整数でのユークリッド除算
ユークリッド除算は、2 つの整数aとb ( b はゼロではありません) に対して、商qと剰余r (どちらも整数) を関連付け、次のことを検証します。
- $$ {a = b.q+r\,} $$
- $$ {|r| < |b|\;} $$
剰余と商が存在するという主張は、整数のユークリッドの除算定理と呼ばれます。
商と余りの一意性が保証されるような割り算を定義できたとしても、それはユークリッド環における一般的な割り算の場合とは互換性がありません。
自然数に対するユークリッド除算の定義により、次のような 2 つの自然数q 1とr 1の存在を証明することができます。
- | | = | b | q 1 + r 1 ( r 1 < |) b |
aとbのそれぞれの符号について少し研究すると、a による b のユークリッド除算が得られます。
- 負のaおよびb の場合、商q 1および剰余 – r 1
- 負のaと正のbの場合、商 – q 1および剰余 – r 1
- 正のaと負のbの場合、商 – q 1および剰余r 1
- a と b が正の場合、商q 1 、余りr 1
多項式の集合におけるユークリッド除算
リングが物体上に定義されている場合、べき乗の減少に従ったユークリッド除算が存在します。
フィールドKと非ゼロB の係数を持つ 2 つの多項式AおよびBに対して、ユークリッド除算により一意の商Qと一意の剰余Rが関連付けられ、両方の多項式が検証されます。
- $$ {A=B.Q+R\,} $$
- $$ {\operatorname{deg}(R) < \operatorname{deg}(B)} $$
ここでは一意性が保証されていますが、 K が本体である必要があります。それ以外の場合、たとえばBの支配的な単項式の係数が 1 に等しい場合、またはより一般的には B の支配的な単項式の係数が可逆的である場合には、除算が可能な場合もあります。
リング上のユークリッド除算
特定のタイプの整数ユニタリ可換環では、次のようにユークリッド除算を定義できます。
- a = bq + r 、 r = 0 ここで、 v(r) < v(b) vは、次のA – { 0 } のマップです。 $$ {\mathbb N} $$ユークリッド眼球と呼ばれます。
環 A 上にユークリッド スタスムが存在する場合、次の性質を満たすものが存在します。 aとb がaを割るようなAの 2 つの要素である場合、 v (b)