除法の原理のソースを表示

{{出典の明記|date=2012年5月}}
'''除法の原理'''（じょほうのげんり、{{lang-en-short|division theorem}}）とは、「'''被除数'''と'''除数'''と呼ばれる二つの自然数に対して、'''商'''と'''剰余'''と呼ばれる二つの自然数が、与えられた性質を満たして一意に定まる」ことを示す[[算術]]における[[定理]]である。
たとえば、自然数 {{mvar|n}} および 0 でない自然数 {{mvar|m}} に対して、{{math|''n'' {{=}} ''am'' + ''b'' (0 &le; ''b'' &lt; ''m'')}}を満たす自然数 {{mvar|a}}, {{mvar|b}} の組がただ一つ存在することを示す。

除法の原理に基づき、[[自然数]]や[[整数]]に対する'''剰余付き除法'''（じょうよつきじょほう、{{lang-en-short|division with remainder}}）を[[定義]]できる。剰余付き除法は'''ユークリッド除法'''（ユークリッドじょほう、{{lang-en-short|Euclidean division}}）、'''整除法'''（せいじょほう、{{lang-en-short|entire division}}）とも呼ばれる。

剰余付き除法の商と剰余を求める[[アルゴリズム]]が知られている。たとえば[[長除法]]は[[十進記数法]]（あるいは任意の[[位取り記数法]]）で表された整数に対するアルゴリズムである。

整数に対する除法の原理は、[[初等算術]]における定理の基盤であり、二整数の[[最大公約数]]を求める[[ユークリッドの互除法]]のような他の算法や整数の間のある種の合同関係を定める[[合同算術]]などに対する重要な要件になっている。

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

== 自然数に対する除法の原理 ==
; 主張: 与えられた二つの自然数 ''n'' および ''m'' &ne; 0 に対して、''n'' = ''am'' + ''b'' (''b'' &lt; ''m'') が成立するような自然数 ''a'' および ''b'' が一意的に存在する
; 証明
:; 存在性
:: 証明略
:; 一意性
:: 証明略

== 整数に対する除法の原理 ==
; 主張1: 与えられた二つの整数 ''n'' および ''m'' &ne; 0 に対して、''n'' = ''am'' + ''b'' (0 &le; ''b'' &lt; |''m''|) が成立するような整数 ''a'' および ''b'' が一意的に存在する
; 証明
:; 存在性
:: 証明略
:; 一意性
:: 証明略
; 主張2: 与えられた二つの整数 ''n'' および ''m'' &ne; 0 に対して、''n'' = ''am'' + ''b'' (|''b''| &lt; |''m''|) が成立するような整数 ''a'' および ''b'' が存在する
; 剰余の取り方に関する注意
:一般に、剰余の一意性には注意が必要である。一意性が保障されない簡単な例として、''a'' = 7, ''b'' = −3 とすると
:* 7 = (−2)(−3) + 1
:* 7 = (−3)(−3) − 2
:と 2 通りに分解することができて、確かに |1| &lt; |−3| も |−2| &lt; |−3| も成り立っている。
: 一意性を与える付帯条件のつけ方は一通りではない。たとえば、「被除数が負であるときは、被除数と絶対値が等しい自然数をとり、そちらを割算してから改めて符号を付け替える」 というような流儀も存在して、これも広く用いられている。計算機においては、負の数の表現方法にも因る話であるので、プログラムに剰余計算をさせるときなどは注意が必要である。自然数の場合にはこのような混乱は生じない。

== 算術における応用 ==

=== 互除法 ===
{{main|ユークリッドの互除法}}

=== 合同式 ===
{{main|合同式}}
二つの整数 ''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 &le; ''m'' &lt; ''n'' となる整数 ''m'' であって ''a'' ≡ ''m'' (mod ''n'') となるものは ''a'' を ''n'' で割った剰余そのものであり、'''Z''' を合同関係で類別した同値類は、剰余としばしば同一視される。

=== 剰余演算 ===
{{see also|剰余演算}}
自然数 ''n'' を固定して、整数 ''m'' を ''n'' で割ったとき、その剰余はただ一つに定まるから、剰余計算を[[二項演算]]の一種と見ることもできる。剰余を求める演算の[[演算 (数学)|演算子]]として "mod" が用いられ、次のように書く。
* ''m'' mod ''n''
* mod(''m'', ''n'')
一部の[[プログラミング言語]]（[[C言語]]など）では "%" を用いて、''m'' % ''n'' と書く。''n'' が正のとき、剰余演算の結果は、0 以上 ''n'' 未満である。例えば、7 mod 5 = 2 であり、&minus;7 mod 5 = 3 である。

余りが等しいことを意味する等式
* ''a'' mod ''n'' = ''b'' mod ''n''
は、合同式 ''a'' ≡ ''b'' (mod ''n'') と解釈することもできる。

剰余演算は、日常レベルから[[RSA暗号]]などの[[計算機科学]]までの幅広い分野で利用される。

=== 展開 ===
整数 ''n'' &gt; 1 を一つ選び固定するとき、任意の整数 ''m'' は ''n'' の[[冪乗]] ''n''<sup>''k''</sup> (''k'' ≥ 0) に関する剰余の[[列 (数学)|列]] (''m'' mod ''n''<sup>''k''</sup>)<sub>''k''=0,1,2,...</sub> によって一意的に特定することができる。具体的には、''m'' に対して ''n''<sup>''k''+1</sup> を法とする剰余から ''n''<sup>''k''</sup> を法とする剰余を引いたものは ''n''<sup>''k''</sup> で割り切れるので、これを ''a''<sub>''k''</sub>''n''<sup>''k''</sup>とすれば、0 ≤ ''a''<sub>''k''</sub> &lt; ''n'' かつ、十分大きな ''k'' についてはすべて ''a''<sub>''k''</sub> = 0 となる。つまり適当な自然数 ''M'' が存在して
:<math>m = a_0 + a_1 n + a_2 n^2 + \cdots + a_M n^M</math>
と書くことができて、しかもこのような表示は一意的であるということである。これを、整数 ''m'' の ''n'' を法とする展開、あるいは ''n''-'''進展開'''と呼び、はじめに固定した ''n'' を展開の基数と呼ぶ。この展開は[[位取り記数法]]などの記法の原理的な根拠となる。
	
十分大きな ''k'' についてはすべて ''a''<sub>''k''</sub> = 0 となるという制限は、基数が素数 ''p'' であるときには [[p進付値|''p''-進距離]]に関する収束の概念を用いて除くことができて、 [[p進数|''p''-進整数]]の ''p''-進展開を与える。また、[[絶対値]]の導く[[距離空間|距離]]を入れ、基数 ''n'' の負の冪をも同時に考えるならば有理数や[[実数]]の ''n''-進展開（[[小数|小数展開]]）を考えることができる。

== 多項式に対する除法の原理 ==
; 主張: 与えられた二つの多項式 ''P''(''x'') および ''M''(''x'') &ne; 0 に対して、''P''(''x'') = ''Q''(''x'')''M''(''x'') + ''R''(''x'') (deg ''R'' &lt; deg ''M''(''x'')) が成立するような多項式 ''Q''(''x'') および ''R''(''x'') が一意的に存在する
; 証明
:; 存在性
:: 証明略
:; 一意性
:: 証明略

== ユークリッド環 ==
{{main|ユークリッド環}}
[[有理整数環|整数全体の成す環]] '''Z'''、体 ''K'' 上の一変数[[多項式環]] ''K''[''x''] や[[ガウス整数|ガウスの整数環]] '''Z'''[√−1] などで次の'''除法の原理'''が成り立つ。

:[[整域]] ''R'' において、ある[[整列集合]] ''W'' と写像 ''N'': ''R'' → ''W'' で、次の性質を満たすものが存在する。
:# ''W'' の最小元 ''m'' に対し、''N''(''a'') = ''m'' ⇔ ''a'' = 0。
:# ''a'', ''b'' ∈ ''R''、''b'' ≠ 0 ならば ''a'' = ''qb'' + ''r'' かつ ''N''(''r'') &lt; ''N''(''b'') を満たす ''q'', ''r'' ∈ ''R'' が存在する。

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

== 関連項目 ==
*[[中国の剰余定理]]

== 外部リンク ==
* {{citation|author=雪本義人|title=数論入門|url=http://www.osaka-kyoiku.ac.jp/~ybaba/suhron_nyumon.pdf|format=PDF|publisher=大阪教育大学 数学教育講座
|year=2011}}（第三項 整除法）

{{二項演算}}

{{DEFAULTSORT:しよほうのけんり}}
[[Category:除法]]
[[Category:算術]]
[[Category:数論の定理]]
[[Category:数学に関する記事]]