4

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!

Robert Soupe
  • 14,663
Alicia Bryant
  • 53
  • 2
  • The second claim is fine... It could be false, but I don´t know how to prove it by hand – Alicia Bryant Apr 23 '17 at 12:40
  • Sorry, I overlooked the requirement that $n$ must be a fermat-pseudoprime to the bases $a$ and $b$. – Peter 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. – Peter Apr 23 '17 at 20:57

1 Answers1

1

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$

Peter
  • 84,454
  • 1
    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. – Alicia Bryant Apr 23 '17 at 12:42
  • 1
    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. – Alicia Bryant Apr 23 '17 at 12:48
  • 1
    Thank you very much! You have helped me a lot – Alicia Bryant Apr 25 '17 at 09:31