[科普中國]-歐拉－雅可比偽素數(shù)

在數(shù)論中，奇數(shù)整數(shù)n被稱為歐拉－雅可比偽素數(shù)（Euler–Jacobi可比偽素數(shù)）（或者更常見的是歐拉可能素數(shù)）。

介紹如果a和n是互質的，那么

mod

其中是雅可比符號。
如果是滿足上述同余的奇數(shù)復合整數(shù)，那么被稱為Euler-Jacobi pseudoprime（或者更常見的是Euler pseudoprime）以基于。

屬性這個定義的動機是所有素數(shù)n滿足上述等式的事實，如Legendre符號文章中所述。 可以相當快速地測試該等式，其可以用于概率素性測試。 這些測試的強度是基于費馬小定理的測試的兩倍1。

每個歐拉－雅可比偽素數(shù)也是Fermat pseudoprime和Euler pseudoprime。 正如卡邁克爾數(shù)字那樣，沒有任何數(shù)字是Euler-Jacobi偽像到所有基數(shù)。 Solovay和Strassen表明，對于每個復合物n，對于小于n的至少n / 2個堿基，n不是歐拉－雅可比偽素數(shù).

最小的歐拉－雅可比偽素數(shù)2是561.有11347個歐拉－雅可比偽素數(shù)2小于25·109。

如上定義的歐拉－雅可比偽素數(shù)通常簡稱為Euler pseudoprime。

例子下表給出了基數(shù)n≤30的所有Euler-Jacobi假性小于100000。

|| ||

本詞條內容貢獻者為:

王沛 - 副教授、副研究員 - 中國科學院工程熱物理研究所