# Fermat and strong pseudoprimes

A composite number is said to be a Fermat pseudoprime to the base $a$ if $\gcd(a, n) = 1$ and $a^{n - 1} \equiv 1 \bmod n$.

Let $n$ be an odd composite number, $n = t2^k + 1$ with $t$ odd. Let $a$ be such that $\gcd(a, n) = 1$. It is said that $n$ is a strong pseudoprime to the base $a$ if any of the following conditions is satisfied:

i) $a^t \equiv 1 \bmod n$

ii) There exists $0 \leq i < k$ such that $a^{2^it}\equiv -1 \bmod n$

Let $n$ be an integer and $a, b$ with $\gcd(a, b) = 1$, primes with $n$ and $n$ Fermat pseudoprime to the bases $a$ and $b$. Say if the following statements are true, justifying the answer:

a) If $n$ is a strong pseudoprime to the bases $a$ and $b$ then $n$ is strong pseudoprime to the base $ab$.

b) If $n$ is not a strong pseudoprime for either base $a$ and $b$ then $n$ is a strong pseodoprime to the base $ab$

Thanks!

• The second claim is fine... It could be false, but I don´t know how to prove it by hand Apr 23 '17 at 12:40
• Sorry, I overlooked the requirement that $n$ must be a fermat-pseudoprime to the bases $a$ and $b$. Apr 23 '17 at 20:05
• I edited my question, and hope that $1)$ everything is alright now $2)$ the counterexamples are small enough to be done by hand. Apr 23 '17 at 20:57

A counter-example for $b)$ is $1105=5\cdot 13\cdot 17=2^4\cdot 3\cdot 23+1$

It is a fermat-pseudoprime to the bases $2,3$ and $6$ and it is not strong pseudoprime to any of the bases $2,3$ and $6$

A counter-example for $a)$ is $2353=13\cdot 181=2^4\cdot 3\cdot 7^2+1$

It is a fermat-pseudoprime to the bases $7,19$ and $133$. It is also strong pseudoprime to the bases $7$ and $19$, but not to the base $133$

• Repect to the claim b): 25 is not a Fermat pseudoprime to the bases a and b and in the statement this property is required. Apr 23 '17 at 12:42
• But the claim is how I wrote it. Respect to the claim a): I have to prove by hand (in a papper) that it's true or false... With this big number it's imposible and I don't know if 106485121 is a Fermat pseudoprime to the bases a and b. Apr 23 '17 at 12:48
• Thank you very much! You have helped me a lot Apr 25 '17 at 9:31