引子
在《從費馬小定理談起》一文中，為大家介紹了偽素數 (Pseudoprime) 的由來。其實偽素數何止一種，自費馬偽素數 (Fermat Pseudoprime) 出現以後，數學家漸漸喜歡把符合一些素數性質的逆命題的合數 (Composite Number) 稱為偽素數 (Pseudoprime)，我們便出現了很多不同的偽素數。
歐拉 - 雅可比偽素數
歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime) 或簡稱歐拉偽素數 (Euler Pseudoprime) 簡記 ejpsp(a)。這是由歐拉判別式 (Euler's Criterion) 開始，對任何奇素數 (Odd Prime) ，我們有：
其中上式中的 (a/p) 為勒讓德符號 (Legendre Symbol) 。所謂勒讓德符號，可看《勒讓德符號》。
例：取 a = 4，p = 23，我們得知 411 = 1 (mod 23)，另一方面 (4/23) = (2*2/23) = 1，故成立。當然這一例不算得什麼證明。
若有一合數 a，使 (a,n) = 1 ，即 a 與 n 互素，且符合下式，式中的 (a/n) 為雅可比符號 (Jacobi Sumbol)：
對此我們稱 n 為以 a 為底的歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime to Base a) ，簡記 ejpsp(a)。
那雅可比符號又是什麼？
若 m 可分解成 m = p1a1 * p2a2 * ...... * pkak，則有 (n/m) = (n/p1)a1 * (n/p2)a2 * ...... * (n/pk)ak，式中右方的括號為勒讓德符號。
若考慮所有與 n 互素的底 a，我們發現沒有一個奇合數可使之成為以所有 a 為底的歐拉 - 雅可比偽素數。
以 2 為底的歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime to Base 2，簡記 ejpsp(2)) 有：561, 1105, 1729, 1905, 2047, 2465, ...... (OEIS A047713)
以 3 為底的歐拉 - 雅可比偽素數 (Euler - Jacobi Pseudoprime to Base 3，簡記 ejpsp(3)) 有：121, 703, 1729, 1891, 2821, 3281, 7381, ...... (OEIS A048950)
強偽素數
強偽素數 (Strong Pseudoprime) ，我們簡記 spsp(a)。
以 a 為底的強偽素數 (Strong Pseudoprime to Base a) 是指一奇合數 n，其中 n-1 = d*2s (d 為奇數 Odd Number)，滿足：
或 
，r = 0,1,2,
...... , s-1
以 2 為底的強偽素數 (Strong Pseudoprime to Base 2) 有：2047, 3277, 4033, 4681, ...... (OEIS A001262)
強偽素數亦是一些素數判別方法，如魯賓 - 米勒強偽素數測試 (Rabin - Miller Strong Pseudoprime Test) 、 巴利爾 - PSW 素性測試 (Baillie - PSW Primality Test) 等。
參考文獻及網址：
Guy, R. K. "Pseudoprimes. Euler Pseudoprimes. Strong Pseudoprimes." §A12 in Unsolved Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 27-30, 1994.
Weisstein, E. W. "Euler-Jacobi Pseudoprime." From MathWorld. http://mathworld.wolfram.com/Euler-JacobiPseudoprime.html.
Weisstein, E. W. "Euler Pseudoprime." From MathWorld. http://mathworld.wolfram.com/EulerPseudoprime.html.
Weisstein, E. W. "Pseudoprime." From MathWorld. http://mathworld.wolfram.com/Pseudoprime.html.
Weisstein, E. W. "Strong Pseudoprime." From MathWorld. http://mathworld.wolfram.com/StrongPseudoprime.html.
