欧拉伪素数

欧拉伪素数（英语：Euler pseudoprime）是伪素数的一种。对于奇合数n以及与其互素的自然数a，如果

${\displaystyle a^{(n-1)/2}\equiv \pm 1{\pmod {n}}}$

成立，则称n为关于a的欧拉伪素数。欧拉伪素数是费马伪素数的推广，所有欧拉伪素数同时也是费马伪素数。

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

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