欧几里得引理

维基百科,自由的百科全书
跳转至: 导航搜索

在数论中,欧几里得引理是根据欧几里得的《几何原本》第七卷的命题30推出的一个定理。這個引理說明:

如果一个正整数整除另外两个正整数的乘,第一个整数与第二个整数互质,那么第一个整数整除第三个整数。

可以这样表达这个引理:

如果a|bcgcd(a,b)=1 那么 a|c

命题30是这样说的:

如果一个素数整除两个正整数的乘积,那么这个素数可以至少整除这两个正整数中的一个。

如果 p|bc 那么 p|b 或者 p|c

命题30的证明[编辑]

pab的一个素因子,但不是a的因子。于是,可设rp = ab\!,其中rab的另外一个因子。由于p是素数,且不是a的因子,ap一定是互素的。这就是说,可以找到两个整数xy,使得1 = px + ay\!裴蜀定理)。两边乘以b,可得:

b = b(px + ay)\!
b = bpx + bay\!.

前面已经说了rp = ab\!,因此:

b = bpx + rpy\!
b = p(bx + ry)\!.

所以,pb的因子。这就是说,p要么整除a,要么整除b,要么都能整除。证毕。