欧几里得引理
在数论中,欧几里得引理是在欧几里得《几何原本》第七卷的命题30中提出的定理。這個引理說明:
可以这样表达这个引理:
- 如果a|bc ,gcd(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。这就是说,可以找到两个整数x和y,使得 (貝祖定理)。两边乘以b,可得:
- .
前面已经说了 ,因此:
- .
所以,p|b。这就是说,p要么整除a,要么整除b,要么都能整除。证毕。