Could someone just clear up what exactly a strong pseudoprime is for me? Every book seems to say something slightly different!

From my notes it appears it might be if it passes the Miller-Rabin-Shang pseudoprime test however that doesn't actually say strong pseudoprime in my notes but seems to be the method used in tutorials for the strong pseudoprime problem...

Here's the question I'm doing...

Show that the Carmichael number 561 is not a strong pseudoprime to base 2, but that 2047 is. Show, however, that 2047 is not a strong pseudoprime to base 3.

The way I have been doing it is based on wikipedia. The number $\displaystyle p$ we are testing is of the form $\displaystyle d \cdot 2^s + 1$, then it is a strong pseudoprime (to base 2 for ex) if...

$\displaystyle 2^d \equiv 1$ mod p

So,

$\displaystyle 561 = 35\cdot 2^4 + 1$

Now since 561 = 3x11x17, we use the method shown by tonio here...

http://www.mathhelpforum.com/math-he...ongruence.html to find an answer.

Now since I got 263 from this, does that mean that 561 is NOT a strong pseudoprime to base 2 or do I have show it does not pass both of the tests here

Strong pseudoprime - Wikipedia, the free encyclopedia...

Is that even how i answer this question?