Editing Strong pseudoprime (section)

==Motivation and first examples==
Let us say we want to investigate if ''n'' = 31697 is a [[probable prime]] (PRP). We pick base ''a'' = 3 and, inspired by [[Fermat's little theorem]], calculate:
: <math>3^{31696} \equiv 1 \pmod {31697}</math>
This shows 31697 is a Fermat PRP (base 3), so we may suspect it is a prime. We now repeatedly halve the exponent:
: <math>3^{15848} \equiv 1 \pmod {31697}</math>
: <math>3^{7924} \equiv 1 \pmod {31697}</math>
: <math>3^{3962} \equiv 28419 \pmod {31697}</math>
The first couple of times do not yield anything interesting (the result was still 1 modulo 31697), but at exponent 3962 we see a result that is neither 1 nor minus 1 (i.e. 31696) modulo 31697. This proves 31697 is in fact composite (it equals 29×1093). Modulo a prime, the residue 1 can have no other square roots than 1 and minus 1. This shows that 31697 is {{em|not}} a strong pseudoprime to base 3.

For another example, pick ''n'' = 47197 and calculate in the same manner:
: <math>3^{47196} \equiv 1 \pmod {47197}</math>
: <math>3^{23598} \equiv 1 \pmod {47197}</math>
: <math>3^{11799} \equiv 1 \pmod {47197}</math>
In this case, the result continues to be 1 (mod 47197) until we reach an odd exponent. In this situation, we say that 47197 {{em|is}} a strong probable prime to base 3. Because it turns out this PRP is in fact composite (can be seen by picking other bases than 3), we have that 47197 is a strong pseudoprime to base 3.

Finally, consider ''n'' = 74593 where we get:
: <math>3^{74592} \equiv 1 \pmod {74593}</math>
: <math>3^{37296} \equiv 1 \pmod {74593}</math>
: <math>3^{18648} \equiv 74592 \pmod {74593}</math>
Here, we reach minus 1 modulo 74593, a situation that is perfectly possible with a prime. When this occurs, we stop the calculation (even though the exponent is not odd yet) and say that 74593 {{em|is}} a strong probable prime (and, as it turns out, a strong pseudoprime) to base 3.