1
$\begingroup$

Show that if $n=\frac{a^{2p}-1}{a^2-1},$ where $a$ is an integer, $a>1$, and $p$ is an odd prime not dividing $a(a^2-1)$, then $n$ is pseudoprime to the base $a$.

Let $n=\frac{a^{2p}-1}{a^2-1}=1+a^2+(a^2)^2+(a^2)^3+\cdots$. Then $n-1=\frac{a^{2p}-1}{a^2-1}-1=\frac{a^{2p}-a^2}{a^2-1}=a^2\frac{(a^2)^{p-1}-1}{a^2-1}.$

I have kind of hit a roadblock with this proof. I'm stuck trying to show that $n-1$ is even and that $p | (a^{2p}-1)\equiv 0 \mod p$. Is there some obvious steps that I'm missing

$\endgroup$
3
$\begingroup$

Write

$$\begin{align} n-1 &= \frac{a^{2p}-a^2}{a^2-1}\\ &= \frac{(a^p-a)(a^p+a)}{a^2-1}\\ &= a\frac{a^{p-1}-1}{a^2-1}(a^p+a). \end{align}$$

Since $p$ is odd, $a^2-1$ divides $a^{p-1}-1$, so we have written $n-1$ as a product of three integers, and the last one, $a^p+a$ is even, whether $a$ is even or odd. Hence $n-1$ is even.

Also, since $p\nmid a$, we have $a^{p-1}\equiv 1\pmod{p}$, and since by assumption $p\nmid (a^2-1)$, we further have

$$p \mid \frac{a^{p-1}-1}{a^2-1}.$$

Together, $2p\mid n-1$, and so $(a^{2p}-1) \mid (a^{n-1}-1)$, which implies $n\mid (a^{n-1}-1)$.

We do not have $p\mid (a^{2p}-1)$, since $a^{2p} = a^{2(p-1)+2} \equiv a^2 \not\equiv 1\pmod{p}$, but that is not anything we would need.

$\endgroup$

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.