4
$\begingroup$

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!

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

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$

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 23 '17 at 12:42
  • 1
    $\begingroup$ 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. $\endgroup$ Apr 23 '17 at 12:48
  • 1
    $\begingroup$ Thank you very much! You have helped me a lot $\endgroup$ Apr 25 '17 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.