Tranwiki:整除性および素数に関する初等的定理のソースを表示

定義 1.1. ''m'', ''n''を整数とする。''m'' =''an''となる整数''a''が存在する時、''m''は''n''の倍数であり、
''n''は''m''の約数であるといい、''n''|''m''と記す。

定理 1.2. ''l'', ''m'', ''n''を整数とする。
:*a) ''l''|''m'', ''m''|''n'' ならば ''l''|''n''。
:*b) ''l''|''m'', ''l''|''n'' ならば ''l''|(''m''+''n'')。
:*c) ''l''|''m'', ''l''|''n'' で ''a'', ''b'' が整数ならば ''l''|(''am''+''bn'')。

証明
:*a) ''m''=''al'', ''n''=''bm'' を満たす整数''a'', ''b''が存在する。よって''n''=''abl''であるから ''l''|''n'' 。
:*b) ''m''=''al'', ''n''=''bl'' を満たす整数''a'', ''b''が存在する。よって''m''+''n''=(''a''+''b'')''l''であるから ''l''|(''m''+''n'') 。
:*c) a)より ''l''|(''am'') かつ ''l''|(''bn'') だから、b)より ''l''|(''am''+''bn'') 。（証明終）

定義 1.3. ''m'', ''n''を0と異なる整数とする。
:*a) 整数''l''が ''m''|''l'' かつ ''n''|''l'' を満足する時 ''l'' を''m''と''n''の公倍数であるといい、整数''l''が ''l''|''m'' かつ ''l''|''n'' を満足する時 ''l'' を''m''と''n''の公約数であるという。
:*b) ''m''と''n''の最小の公倍数を [''m'', ''n''] と書き、''m''と''n''の最大の公約数を (''m'', ''n'') と書く。

注意. [''m'', ''n''] および (''m'', ''n'') という記法は別の意味に用いることもある。

定理 1.4. ''m'', ''n''を正の整数とする。このとき次の性質を満たす整数''a'', ''b''が存在する:
:* <math>m=an+b</math>,
:* <math>0\le b < n</math>。

証明.
<math>a=\lfloor m/n\rfloor, b=m-an</math>とおく。このとき、''a'', ''b''は整数である。
また、<math>a\le m/n < a+1 </math>だから、<math>an\le m < an+n</math>である。よって
<math>0\le b < n</math>である。（証明終）

定理 1.5. ''m'', ''n''を0と異なる整数とし、''a''=(''m'', ''n'') とおく。このとき、
<math>mx+ny=a</math>を満たす整数''x'', ''y''が存在する。

証明.
''m'', ''n''は正の整数として差し支えない。max{''m'', ''n''}に関する帰納法で証明する。
* <math>m=n=1</math>のときは<math>x=1, y=0</math>とおけばよい。
* max{''m'', ''n''}≦''k''に対して定理が証明され、max{''m'', ''n''}=''k''+1と仮定する。
このとき<math>k+1=m\ge n</math>と仮定しても差し支えない。

''n''|''m''ならば<math>x=0, y=1</math>とおけばよい。
''n''|''m''でなければ、定理 1.4より<math>m=an+b, 0\le b < n</math>を満たす整数''a'', ''b''が存在する。
<math>b \le n-1 \le k</math>より<math>nu+bv=(n, b)</math>を満たす整数''u'', ''v''が存在する。
定理 1.2 c)より(''n'', ''b'')|''m''だから、(''n'', ''b'')|(''m'', ''n'')である。よって
<math>nw+bz=(m, n)</math>を満たす整数''w'', ''z''が存在する。''b''=''m''-''an''より、
<math>mb+n(w-ab)=(m, n)</math>である。（証明終）

[[Category:数学|せいしよせいおよひそすうにかんするしよとうてきていり]]