歐幾里德引理

這個引理説明：

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

可以這樣表達這個引理：

如果a|bc ，gcd(a,b)=1 那麼 a|c。

命題30是這樣説的：

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

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

設p|ab，但p不是a的因子。於是，可設rp=ab，其中r|ab。由於p是質數，且不是a的因子，gcd(a,p)=1。這就是説，可以找到兩個整數x和y，使得1=px+ay（裴蜀定理）。兩邊乘以b，可得：

b=b(px+ay)

b=bpx+bay

前面已經説了:rp=ab，因此：

b=bpx+rpy

b=p（bx+ry）

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