For any positive integer $a$, prove that there exists infinitely many composite $n$ such that $a^{n-1}\equiv 1\mod n$. Studying for an upcoming comprehensive exam we stumbled upon the following problem:
Prove that for every positive integer $a$, there exists infinitely many composite integers $n$ such that $a^{n-1}\equiv 1 \mod n$. (Hint: Choose $n=\frac{a^{2p}-1}{a^2-1}$ for a suitable prime $p$.)
We have tried many approaches to no avail. The most promising approach involved choosing $p$ such that $a$ is a quadratic residue modulo $p$. Then $n-1=\frac{a^2(a^{2(p-1)}-1)}{a^2-1}$ has a factor of $p$ (the second factor in the numerator is a difference of squares which factors to another difference of squares and finally an $a^{(p-1)/2}-1$ pops out which by our choice of $p$ must be divisible by $p$. We were unable to conclude from here. Any help would be appreciated. 

First: If $p$ is a prime and
$$n=\frac{a^{2p}-1}{a^2-1} =1+a^2+a^4+...+a^{2p-2}$$
Then 
$$ 1+a^2+a^4+...+a^{2p-2}=0 \pmod{n} \\
a^2( 1+a^2+a^4+...+a^{2p-2})=0 \pmod{n} \\
a^2+a^4+...+a^{2p-2}+a^{2p}=0 \pmod{n} \\
$$
Subtracting the first and last relation you get
$$1=a^{2p} \pmod{n}$$
Now, if you now chose $p,n$ so that $2p |n-1$ you get 
$$a^{n-1} \equiv 1 \pmod{n}$$
Note that $2p |n-1$ means
$$2p|a^2(1+a^2+...+a^{2p-4})$$
It is easy to make the RHS even and if you want 
$$p|1+a^2+...+a^{2p-4}$$
the easiest way is to pick $p >a^2-1$ (to make sure that $a^2-1$ cannot be divisible by $p$) and use
$$a^{2p-2} \equiv (a^{p-2})^2\equiv 1 \pmod{p}$$
