# Constructing pseudoprimes to the base 3.

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?

-
Did you mean $2^{n-1}$, or $2^n - 1$? I wasn't sure. – Arturo Magidin Apr 29 '12 at 3:48
Sorry, (2^n)-1. – Sksnchd Apr 29 '12 at 3:54
I presume you mean Fermat pseudoprimes? – joriki Apr 29 '12 at 4:30
Okay... your question boils down to "given a base-$3$ Fermat pseudoprime, construct another base-$3$ Fermat pseudoprime from it". Am I right? – J. M. Apr 29 '12 at 17:43

## 2 Answers

Theorem :

If $n$ and $2n-1$ are primes , where $n>3$ , then $p=n\cdot(2n-1)$ is a pseudoprime to base $3$ .

link

-

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.

-
How do we know these pseudoprimes aren't actually primes? – Gerry Myerson May 12 '12 at 6:53
@Gerry: $\dfrac{a^{2p} - 1}{a^2 - 1} = \dfrac{a^p - 1}{a - 1}\dfrac{a^p + 1}{a+1}$ – mixedmath May 12 '12 at 19:06