欧拉伪素数

欧拉伪素数（）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果
 
成立，则称n为关于a的欧拉伪素数。欧拉伪素数是费马伪素数的推广，所有欧拉伪素数同时也是费马伪素数。

与费马伪素数类似，欧拉伪素数的定义也是源于费马小定理。该定理表明，对于素数p以及整数a，有 ap−1 =  1 (mod p)。对大于2的素数p，p可以表示为2q + 1 ，其中q为整数。于是a(2q+1) − 1 = 1 (mod p) 成立。再进一步化简为a2q − 1 = 0 (mod p)。通过因式分解，得到(aq − 1)(aq + 1) = 0 (mod p)，即a(p−1)/2 = ±1 (mod p)。

上式可以用作概率素性检验，其可靠性是费马素性检验的两倍。不过无法基于欧拉伪素数对素数进行确定性检验，因为存在绝对欧拉伪素数，即其关于所有与其互素的数都是欧拉伪素数。绝对欧拉伪素数是卡迈克尔数（即绝对费马伪素数）的子集。最小的绝对欧拉伪素数为1729 = 7×13×19。

示例

关于n的最小欧拉伪素数

参见 
 欧拉－雅可比伪素数
 费马伪素数
 強偽質數
 卡迈克尔数

参考文献 
M. Koblitz, "A Course in Number Theory and Cryptography", Springer-Verlag, 1987.
H. Riesel, "Prime numbers and computer methods of factorisation", Birkhäuser, Boston, Mass., 1985.

伪素数