欧几里得引理, 在数论中, 是在欧几里得, 几何原本, 第七卷的命题30中提出的定理, 這個引理說明, 如果一个正整数整除另外两个正整数的乘积, 第一个整数与第二个整数互质, 那么第一个整数整除第三个整数, 可以这样表达这个引理, 如果a, 那么, 命题30是这样说的, 如果一个素数整除两个正整数的乘积, 那么这个素数可以至少整除这两个正整数中的一个, 如果, 那么, 或者, 命题30的证明, 编辑设p, 但p不是a的因子, 于是, 可设r, displaystyle, 其中r, 由于p是質数, 且不是a的因子, . 在数论中 欧几里得引理是在欧几里得 几何原本 第七卷的命题30中提出的定理 這個引理說明 如果一个正整数整除另外两个正整数的乘积 第一个整数与第二个整数互质 那么第一个整数整除第三个整数 可以这样表达这个引理 如果a bc gcd a b 1 那么 a c 命题30是这样说的 如果一个素数整除两个正整数的乘积 那么这个素数可以至少整除这两个正整数中的一个 如果 p bc 那么 p b 或者 p c 命题30的证明 编辑设p ab 但p不是a的因子 于是 可设r p a b displaystyle rp ab 其中r ab 由于p是質数 且不是a的因子 gcd a p 1 这就是说 可以找到两个整数x和y 使得1 p x a y displaystyle 1 px ay 貝祖定理 两边乘以b 可得 b b p x a y displaystyle b b px ay b b p x b a y displaystyle b bpx bay 前面已经说了r p a b displaystyle rp ab 因此 b b p x r p y displaystyle b bpx rpy b p b x r y displaystyle b p bx ry 所以 p b 这就是说 p要么整除a 要么整除b 要么都能整除 证毕 参考 编辑 取自 https zh wikipedia org w index php title 欧几里得引理 amp oldid 68571035, 维基百科,wiki,书籍,书籍,图书馆,