欧拉-雅可比伪素数

Wikipedia · 2025-12-07 维基百科 👁 0 阅读

欧拉－雅可比伪素数（）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果
: a^{(n-1)/2} \equiv \left(\frac{a}{n}\right)\pmod{n}
成立（其中\left(\frac{a}{n}\right)为雅可比符号），则称n为以a為底的欧拉－雅可比伪素数，或简称为欧拉伪素数。

欧拉－雅可比伪素数是欧拉伪素数的推广，所有欧拉－雅可比伪素数同时也是费马伪素数与欧拉伪素数。由于上式对所有素数都成立，因而可以用其进行概率素性检验，其可靠性是费马素性检验的两倍多。此外，与绝对费马伪素数（卡迈克尔数）与绝对欧拉伪素数不同的是，不存在绝对欧拉－雅可比伪素数，即不存在以所有与n互素的a為底都是欧拉－雅可比伪素数的n。可以证明，对于n，至少存在n/2个小于n的a，n不是欧拉－雅可比伪素数。