欧拉准则, 在数论中, 二次剩余的歐拉判別法, 又稱歐拉準則, 是用来判定给定的整数是否是一个质数的二次剩余, 目录, 叙述, 举例, 例子一, 对于给定数, 寻找其为二次剩余的模数, 例子二, 对指定的质数p, 寻找其二次剩余, 證明, 參考资料, 外部链接叙述, 编辑若p, displaystyle, 是奇質數且p, displaystyle, 不能整除d, displaystyle, displaystyle, 是模p, displaystyle, 的二次剩余当且仅当, displaystyle, frac,. 在数论中 二次剩余的歐拉判別法 又稱歐拉準則 是用来判定给定的整数是否是一个质数的二次剩余 目录 1 叙述 2 举例 2 1 例子一 对于给定数 寻找其为二次剩余的模数 2 2 例子二 对指定的质数p 寻找其二次剩余 3 證明 4 參考资料 5 外部链接叙述 编辑若p displaystyle p 是奇質數且p displaystyle p 不能整除d displaystyle d 則 d displaystyle d 是模p displaystyle p 的二次剩余当且仅当 d p 1 2 1 mod p displaystyle d frac p 1 2 equiv 1 pmod p dd d displaystyle d 是模p displaystyle p 的非二次剩余当且仅当 d p 1 2 1 mod p displaystyle d frac p 1 2 equiv 1 pmod p dd 以勒让德符号表示 即為 d p 1 2 d p mod p displaystyle d frac p 1 2 equiv left frac d p right pmod p 举例 编辑例子一 对于给定数 寻找其为二次剩余的模数 编辑 令a 17 displaystyle a 17 对于怎样的质数p displaystyle p 17是模p displaystyle p 的二次剩余呢 根据判别法里给出的准则 我们可以从小的质数开始检验 首先测试p 3 displaystyle p 3 我们有 17 3 1 2 17 1 2 mod 3 1 mod 3 displaystyle 17 frac 3 1 2 17 1 equiv 2 pmod 3 equiv 1 pmod 3 因此17不是模3的二次剩余 再来测试p 13 displaystyle p 13 我们有 17 13 1 2 17 6 1 mod 13 displaystyle 17 frac 13 1 2 17 6 equiv 1 pmod 13 因此17是模13的二次剩余 实际上我们有 17 4 mod 13 displaystyle 17 equiv 4 pmod 13 而2 2 4 displaystyle 2 2 4 运用同余性质和勒让德符号可以加快检验速度 继续算下去 可以得到 对于质数p 13 19 17 p 1 displaystyle p 13 19 cdots frac 17 p 1 也就是说17是模这些质数的二次剩余 对于质数p 3 5 7 11 23 17 p 1 displaystyle p 3 5 7 11 23 cdots frac 17 p 1 也就是说17是模这些质数的二次非剩余 例子二 对指定的质数p 寻找其二次剩余 编辑 哪些数是模17的二次剩余 我们可以手工计算 1 2 1 displaystyle 1 2 1 2 2 4 displaystyle 2 2 4 3 2 9 displaystyle 3 2 9 4 2 16 displaystyle 4 2 16 5 2 25 8 mod 17 displaystyle 5 2 25 equiv 8 pmod 17 6 2 36 2 mod 17 displaystyle 6 2 36 equiv 2 pmod 17 7 2 49 15 mod 17 displaystyle 7 2 49 equiv 15 pmod 17 8 2 64 13 mod 17 displaystyle 8 2 64 equiv 13 pmod 17 于是得到 所有模17的二次剩余的集合是 1 2 4 8 9 13 15 16 displaystyle 1 2 4 8 9 13 15 16 要注意的是我们只需要算到8 因为9 17 8 displaystyle 9 17 8 9的平方与8的平方模17是同余的 9 2 8 2 8 2 13 mod 17 displaystyle 9 2 8 2 8 2 equiv 13 pmod 17 同理不需计算比9大的数 但是对于验证一个数是不是模17的二次剩余 就不必将所有模17的二次剩余全部算出 比如说要检验数字3是否是模17的二次剩余 只需要计算3 17 1 2 3 8 81 2 4 2 1 mod 17 displaystyle 3 frac 17 1 2 3 8 equiv 81 2 equiv 4 2 equiv 1 pmod 17 然后由欧拉准则判定3不是模17的二次剩余 欧拉准则与高斯引理以及二次互反律有关 并且在定义欧拉 雅可比伪素数 见伪素数 时会用到 證明 编辑首先 由于p displaystyle p 是一个奇素数 由费马小定理 d p 1 1 mod p displaystyle d p 1 equiv 1 pmod p 但是p 1 displaystyle p 1 是一个偶数 所以有 d p 1 2 1 d p 1 2 1 0 mod p displaystyle d frac p 1 2 1 cdot d frac p 1 2 1 equiv 0 pmod p p displaystyle p 是一个素数 所以d p 1 2 1 displaystyle d frac p 1 2 1 和d p 1 2 1 displaystyle d frac p 1 2 1 中必有一个是p displaystyle p 的倍数 因此d p 1 2 displaystyle d frac p 1 2 模p displaystyle p 的余数必然是1或 1 證明若d displaystyle d 是模p displaystyle p 的二次剩餘 則d p 1 2 1 mod p displaystyle d frac p 1 2 equiv 1 pmod p 若d displaystyle d 是模p displaystyle p 的二次剩餘 則存在x 2 d mod p displaystyle x 2 equiv d pmod p p displaystyle p 跟d x displaystyle d x 互質 根據費馬小定理得 d p 1 2 x p 1 1 mod p displaystyle d frac p 1 2 equiv x p 1 equiv 1 pmod p 證明若d p 1 2 1 mod p displaystyle d frac p 1 2 equiv 1 pmod p 則d displaystyle d 是模p displaystyle p 的二次剩餘p displaystyle p 是一个奇素数 所以关于p displaystyle p 的原根存在 设a displaystyle a 是p displaystyle p 的一个原根 则存在1 j p 1 displaystyle 1 leq j leq p 1 使得d a j displaystyle d a j 于是 a j p 1 2 1 mod p displaystyle a j frac p 1 2 equiv 1 pmod p a displaystyle a 是p displaystyle p 的一个原根 因此a displaystyle a 模p displaystyle p 的指数是p 1 displaystyle p 1 于是p 1 displaystyle p 1 整除j p 1 2 displaystyle frac j p 1 2 这说明j displaystyle j 是一个偶数 令i j 2 displaystyle i frac j 2 就有 a i 2 a 2 i d displaystyle a i 2 a 2i d d displaystyle d 是模p displaystyle p 的二次剩余 參考资料 编辑Legendre Symbol 永久失效連結 二次互反律 永久失效連結 潘承洞 潘承彪 初等数论 北京大学出版社 外部链接 编辑参考证明 中文 永久失效連結 取自 https zh wikipedia org w index php title 欧拉准则 amp oldid 75763660, 维基百科,wiki,书籍,书籍,图书馆,