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が存在する:

• $m=an+b$,
• $0\leq b<n$。

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

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

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

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

このとき$k+1=m\geq n$と仮定しても差し支えない。

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