# Showing that $n$ is pseudoprime to the base $a$

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

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.