3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Won't this always be the case whenever $\gcd(a, n) = 1$? $\endgroup$ – Robert Shore Aug 14 at 21:27
  • 1
    $\begingroup$ @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. $\endgroup$ – 0XLR Aug 14 at 21:36
  • $\begingroup$ @RobertShore $3^{4-1}=27 \equiv 3 \pmod{4}$$ $\endgroup$ – N. S. Aug 14 at 21:37
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Wow! This is excellent. Thank you! $\endgroup$ – Drew Meier Aug 14 at 22:05

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.