[科普中国]-欧拉伪素数

欧拉伪素数（英语：Euler pseudoprime）是伪素数的一种。

定义对于奇合数n以及与其互素的自然数a1，如果

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

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

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

示例关于n的欧拉伪素数如图所示

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所