跳至內容

歐幾里得引理

維基百科,自由的百科全書

在數論中,歐幾里得引理是在歐幾里得幾何原本》第七卷的命題30中提出的定理。這個引理說明:

如果一個正整數整除另外兩個正整數的乘,第一個整數與第二個整數互質,那麼第一個整數整除第三個整數。

可以這樣表達這個引理:

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

命題30是這樣說的:

如果一個素數整除兩個正整數的乘積,那麼這個素數可以至少整除這兩個正整數中的一個。

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

命題30的證明

設p|ab,但p不是a的因子。於是,可設,其中r|ab。由於p是質數,且不是a的因子,gcd(a,p)=1。這就是說,可以找到兩個整數xy,使得貝祖定理)。兩邊乘以b,可得:

.

前面已經說了,因此:

.

所以,p|b。這就是說,p要麼整除a,要麼整除b,要麼都能整除。證畢。

參考