I really have no idea where to start with this question:
Find all $n$ such that if $gcd(a,n)=1$ then $a^2=1$ mod $n$
I found out that it works for $n = 8$, since all odd numbers modulo 8 have order $\leq 2$.
It looks so easy... Can somebody help me? Thanks!
Update: Immediately after posting this, something reminded me of the Carmichael function. Maybe I need to use that one?
On
All we need is Carmichael Function $\displaystyle \lambda(n)|2$
If the highest power of prime $p>2$ that divides $n$ in $k, \phi(p^k)=p^{k-1}$ will divide $\displaystyle \lambda(n)$
$\displaystyle\implies p\le3,k\le1$
If $p=2,\lambda(2^k)=2^{k-2}$ which must divide $\displaystyle \lambda(n)\implies k-2\le1$
Hint: Note that $n=24$ works, and therefore so do all divisors of $24$. Why $24$? Because $3$ and $8$ work, and are relatively prime.
To prove there are no more, first suppose that some prime $\ge 5$ divides $n$. Show that $n$ does not have the required property.
Next suppose that $2^4$ divides $n$. Show that $n$ does not have the required property.
Finally, show that if $9$ divides $n$, then $n$ does not have the required property.
Added: We give a sample proof, doing the middle one. Let $n=2^k m$, where $k\ge 4$ and $m$ is odd. Let $a$ be a solution of the system of congruences $x\equiv 3\pmod{2^k}$, $x\equiv 1\pmod{m}$. There is a solution, by the Chinese Remainder Theorem, and it is relatively prime to $n$. Since $a^2\not\equiv 1\pmod{2^k}$, we have $a^2\not\equiv 1\pmod{n}$.