Tranwiki:整除性および素数に関する初等的定理

定義 1.1. m, nを整数とする。m =anとなる整数aが存在する時、mnの倍数であり、 nmの約数であるといい、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|na, 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) 整数lm|l かつ n|l を満足する時 lmnの公倍数であるといい、整数ll|m かつ l|n を満足する時 lmnの公約数であるという。
  • b) mnの最小の公倍数を [m, n] と書き、mnの最大の公約数を (m, n) と書く。

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

定理 1.4. m, nを正の整数とする。このとき次の性質を満たす整数a, bが存在する:

  • ,

証明. とおく。このとき、a, bは整数である。 また、だから、である。よって である。(証明終)

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

証明. m, nは正の整数として差し支えない。max{m, n}に関する帰納法で証明する。

  • のときはとおけばよい。
  • max{m, n}≦kに対して定理が証明され、max{m, n}=k+1と仮定する。

このときと仮定しても差し支えない。

n|mならばとおけばよい。 n|mでなければ、定理 1.4よりを満たす整数a, bが存在する。 よりを満たす整数u, vが存在する。 定理 1.2 c)より(n, b)|mだから、(n, b)|(m, n)である。よって を満たす整数w, zが存在する。b=m-anより、 である。(証明終)