Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
1  
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 2

Theorem :

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

link

share|improve this answer

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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