除法の原理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

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

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

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

自然数に対する除法の原理[編集]

主張
与えられた二つの自然数 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) + 1
7 = (−3)(−3) − 2
と 2 通りに分解することができて、確かに |1| < |−3| も |−2| < |−3| も成り立っている。
一意性を与える付帯条件のつけ方は一通りではない。たとえば、「被除数が負であるときは、被除数と絶対値が等しい自然数をとり、そちらを割算してから改めて符号を付け替える」 というような流儀も存在して、これも広く用いられている。計算機においては、負の数の表現方法にも因る話であるので、プログラムに剰余計算をさせるときなどは注意が必要である。自然数の場合にはこのような混乱は生じない。

算術における応用[編集]

互除法[編集]

合同式[編集]

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

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

剰余演算[編集]

自然数 n を固定して、整数 mn で割ったとき、その剰余は唯一つに定まるのだから、剰余計算を二項演算の一種と見ることもできる。このような剰余を求める演算の演算子として "mod" や "%" (C言語などで使用)などがしばしば用いられ、

  • m mod n
  • mod(m, n)

などと書かれる。例えば 7 mod 5 = 2 である。余りが等しいことを意味する等式

  • a mod n = b mod n

を作ると、これを合同式と解釈することもできる。剰余演算は日常レベルからRSA暗号などコンピュータサイエンス分野までの幅広いレベルで多用される。

展開[編集]

整数 n > 1 を一つ選び固定するとき、任意の整数 mn冪乗 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 + \cdots + a_M n^M

と書くことができて、しかもこのような表示は一意的であるということである。これを、整数 mn を法とする展開、あるいは n-進展開と呼び、はじめに固定した n を展開の基数と呼ぶ。この展開は位取り記数法などの記法の原理的な根拠となる。

十分大きな k についてはすべて ak = 0 となるという制限は、基数が素数 p であるときには p-進距離に関する収束の概念を用いて除くことができて、 p-進整数p-進展開を与える。また、絶対値の導く距離を入れ、基数 n の負の冪をも同時に考えるならば有理数や実数n-進展開(小数展開)を考えることができる。

多項式に対する除法の原理[編集]

主張
与えられた二つの多項式 P(x) および M(x) ≠ 0 に対して、P(x) = Q(x)M(x) + R(x) (deg R < deg M(x)) が成立するような多項式 Q(x) および R(x) が一意的に存在する
存在性
一意性

ユークリッド環[編集]

整数全体の成す環 Z、体 K 上の一変数多項式環 K[x] やガウスの整数環 Z[√−1] などで次の除法の原理が成り立つ。

整域 R において、ある整列集合 W と写像 N: RW で、次の性質を満たすものが存在する。
  1. W の最小元 m に対し、N(a) = ma = 0。
  2. a, bRb ≠ 0 ならば a = qb + r かつ N(r) < N(b) を満たす q, rR が存在する。

例えば、整数環 Z の場合に、 W = N(0 を含む自然数全体の集合), N(a) = |a| (絶対値)ととればユークリッド整域の条件が満たされる。このような性質を持つ整域 R を一般にユークリッド整域という。剰余はユークリッド整域において定義される概念である。

関連項目[編集]

外部リンク[編集]