Editing Solovay–Strassen primality test (section)

==Example==
Suppose we wish to determine if {{math|1=''n'' = 221}} is prime. We write (''n''&minus;1)/2=110.

We randomly select an ''a'' (greater than 1 and smaller than ''n''): 47.
Using an efficient method for raising a number to a power (mod ''n'') such as [[Modular exponentiation#Left-to-right binary method|binary exponentiation]], we compute:
* {{math|1=''a''<sup>(''n''&minus;1)/2</sup> mod ''n''  =  47<sup>110</sup> mod 221  =  &minus;1 mod 221}}
* <math>\left(\tfrac{a}{n}\right) \bmod n = \left(\tfrac{47}{221}\right) \bmod 221 = -1 \bmod 221</math>
This gives that, either 221 is prime, or 47 is an Euler liar for 221. We try another random ''a'', this time choosing {{math|1=''a'' = 2}}:
* {{math|1=''a''<sup>(''n''&minus;1)/2</sup> mod ''n''  =  2<sup>110</sup> mod 221  =  30 mod 221}}
* <math>\left(\tfrac{a}{n}\right) \bmod n = \left(\tfrac{2}{221}\right) \bmod 221 = -1 \bmod 221</math>.
Hence 2 is an Euler witness for the compositeness of 221, and 47 was in fact an Euler liar. Note that this tells us nothing about the prime factors of 221, which are actually 13 and 17.