ソロベイ–シュトラッセン素数判定法
n = 221が素数かどうかを判定したいとする。(n−1)/2=110である。
ランダムにaを取る(ここではa = 47 < n)。このとき、
a mod n = 47 mod 221 = −1 mod 221
( a n ) {\displaystyle ({\tfrac {a}{n}})} mod n = ( 47 221 ) {\displaystyle ({\tfrac {47}{221}})} mod 221 = −1 mod 221.
これにより、221が素数であるか、47が221のEuler liarであることが分かる。もう一つ別のa(ここではa = 2)で試す。
a mod n = 2 mod 221 = 30 mod 221
( a n ) {\displaystyle ({\tfrac {a}{n}})} mod n = ( 2 221 ) {\displaystyle ({\tfrac {2}{221}})} mod 221 = −1 mod 221.
2は221が合成数であることを示すEuler witnessであるため、47は実はEuler liarであった。なおこの方法では221の約数(13と17)については何も分からないことに注意されたい。