歐幾里得引理

歐幾里得引理是一個在數論中根據歐幾里得的《幾何原本》第七卷的命題30推出的數學定理。

歐幾里得引理

在數論中，歐幾里得引理是根據歐幾里得的《幾何原本》第七卷的命題30推出的一個定理。這個引理說明：
如果一個正整數整除另外兩個正整數的乘積，第一個整數與第二個整數互質，那么第一個整數整除第三個整數。
可以這樣表達這個引理：
如果a|bc ，gcd(a,b)=1 那么 a|c。
命題30是這樣說的：
如果一個素數整除兩個正整數的乘積，那么這個素數可以至少整除這兩個正整數中的一個。
如果 p|bc 那么 p|b 或者 p|c。

命題30的證明

設p為ab的一個素因子，但不是a的因子。於是，可設rp=ab，其中r是ab的另外一個因子。由於p是素數，且不是a的因子，a和p一定是互素的。這就是說，可以找到兩個整數x和y，使得1=px+ay（裴蜀定理）。兩邊乘以b，可得：
b=b(px+ay)
b=bpx+bay
前面已經說了:rp=ab
so,b=bpx+rpy
b=p(bx+ry）
所以，p是b的因子。這就是說，p要么整除a，要么整除b，要么都能整除。證畢。