除法の原理

ウィキペディア

索引トップ用語の索引ランキングカテゴリー

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/02/21 14:15 UTC 版)

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

主張

与えられた二つの自然数 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 に対し a − b が自然数 n の倍数であるとき、「a と b は n を法として合同である」といい、このような整数の関係を合同関係という。合同関係は整数全体の集合 Z における同値関係である。

a と b が n を法として合同であることを、「法 (modulus) によって」という意味のラテン語 "modulo" を用いて、次の合同式で表す。

a ≡ b 　(modulo n)

さらに、単語を "mod" に縮めて、よく次式のように表される。

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 の冪乗 n^k (k ≥ 0) に関する剰余の列 (m mod n^k)_k=0,1,2,... によって一意的に特定することができる。具体的には、m に対して n^k+1 を法とする剰余から n^k を法とする剰余を引いたものは n^k で割り切れるので、これを a_kn^kとすれば、0 ≤ a_k < n かつ、十分大きな k についてはすべて a_k = 0 となる。つまり適当な自然数 M が存在して

m=a_{0}+a_{1}n+a_{2}n^{2}+\cdots +a_{M}n^{M}

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

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