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.

• Won't this always be the case whenever $\gcd(a, n) = 1$? Aug 14 '19 at 21:27
• @RobertShore if $\gcd(a, n) = 1$ we get $a^{\varphi(n)} \equiv 1 \bmod n$ but $\varphi(n)$ may not be $n - 1$ or even divide it. Aug 14 '19 at 21:36
• @RobertShore $3^{4-1}=27 \equiv 3 \pmod{4}$\$ Aug 14 '19 at 21:37

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}$$

• Wow! This is excellent. Thank you! Aug 14 '19 at 22:05