查看“欧几里得引理”的源代码

在数论中，'''欧几里得引理'''是在[[欧几里得]]《[[几何原本]]》第七卷的命题30中提出的定理。這個引理說明：

:如果一个正[[整数]]整除另外两个正整数的乘[[积]]，第一个整数与第二个整数[[互质]]，那么第一个整数整除第三个整数。

可以这样表达这个引理：
:如果''a''|''bc'' ，[[最大公因數|gcd]](''a'',''b'')=1 那么 ''a''|''c''。

命题30是这样说的：

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

:如果 ''p''|''bc'' 那么 ''p''|''b'' 或者 ''p''|''c''。

== 命题30的证明 ==
设p|ab，但''p''不是''a''的因子。于是，可设<math>rp = ab\!</math>，其中r|ab。由于''p''是質数，且不是''a''的因子，[[最大公因數|gcd]](''a'',''p'')=1。这就是说，可以找到两个整数''x''和''y''，使得<math>1 = px + ay\!</math>（[[貝祖定理]]）。两边乘以''b''，可得：

:<math>b = b(px + ay)\!</math>

:<math>b = bpx + bay\!</math>.

前面已经说了<math>rp = ab\!</math>，因此：

:<math>b = bpx + rpy\!</math>

:<math>b = p(bx + ry)\!</math>.

所以，p|b。这就是说，''p''要么整除''a''，要么整除''b''，要么都能整除。证毕。

==参考==
{{reflist}}

[[Category:数论]]
[[Category:引理]]