Find all the solutions of $x^2 \equiv 1 \mbox{ mod }365$.

Question

Find all the solutions of $x^2 \equiv 1 \mbox{ mod }365$.

We know that $365=5\cdot 73$. So if I could find the solutions of $x^2 \equiv 1 \mbox{ mod }5$ and $x^2 \equiv 1 \mbox{ mod }73$, using CRT I could find the solutions of the given equation.
I can solve $x^2 \equiv 1 \mbox{ mod }5$ by hand, but I'm sure that there is an easier way to solve $x^2 \equiv 1 \mbox{ mod }73$.
Would appreciate your help:)

Answer 1

For any prime $p$, you can show that $x^2\equiv1\bmod p\iff x\equiv \pm1\bmod p$. To this end, notice that $$x^2\equiv 1\bmod p\iff \exists k\in\mathbb Z: x^2=k\cdot p+1\iff (x+1)(x-1)=k\cdot p$$ Euclid's Lemma implies now that either $p\mid x+1\iff x\equiv -1\bmod p$ or $p\mid x-1\iff x\equiv 1\bmod p$.

Answer 2

I'm sure that there is an easier way to solve $x^2 \equiv 1 \mbox{ mod }73$.
Would appreciate your help:)

$x^2\equiv1\bmod73\iff x\equiv\pm1\bmod73$