When $n$ is a pseudo prime to the base 2, $2^{n}-1$ is also a pseudo prime to the base 2. This implies there are infinitely many pseudoprimes to the base 2. Then, how can I construct pseudoprimes to the base 3 from known pseudoprime to the base 3 in similar way to show that there are infinitely many pseudo primes to the base 3?
Constructing pseudoprimes to the base 3.
-
0Okay... your question boils down to "given a base-$3$ Fermat pseudoprime, construct another base-$3$ Fermat pseudoprime from it". Am I right? – 2012-04-29
2 Answers
Claim: If $p$ is an odd prime not dividing $a^2-1$, then $m := \dfrac{a^{2p} - 1}{a^2 - 1}$ is a pseudoprime base $a$
Proof: We know $a^p \equiv a \mod p$, so we also know $a^{2p} \equiv a^2 \mod p$. So we know that $p \mid (a^{2p} - a^2)$. By hypothesis, we assumed that $p \not | \;\,(a^2 - 1)$, and noting that $m-1 = \dfrac{a^{2p} - a^2}{a^2 - 1}$, we see that $p \mid (m-1)$.
In fact, looking closer at $\displaystyle \sum_{i = 1}^{p-1} a^{2(p-i)} = a^{2(p-1)} + a^{2(p-2)} + \ldots + a^2 \equiv m-1 \mod p$, we have that $m-1$ is the sum of an even number of terms that all have the same parity. Thus $2 \mid (m-1)$, and so $2p \mid (m-1)$.
Then we have that $(a^{2p} - 1) \mid (a^{m-1} - 1)$, and $a^{2p} - 1 = m(a^2 - 1)$, a multiple of $m$.
Thus $a^{2p} - 1 \equiv 0 \mod m$, which gives $a^{m-1} \equiv 1 \mod m$ $\diamondsuit$
Now use that there are infinitely many primes that are coprime to $3^2 - 1$, and we see that we get infinitely many pseudoprimes base 3.
-
0@Gerry: $\dfrac{a^{2p} - 1}{a^2 - 1} = \dfrac{a^p - 1}{a - 1}\dfrac{a^p + 1}{a+1}$ – 2012-05-12
Theorem :
If $n$ and $2n-1$ are primes , where $n>3$ , then $p=n\cdot(2n-1)$ is a pseudoprime to base $3$ .