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

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$$.
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$$.
I'm sure that there is an easier way to solve $$x^2 \equiv 1 \mbox{ mod }73$$.
$$x^2\equiv1\bmod73\iff x\equiv\pm1\bmod73$$
• Yes, now to solve $x^2 \equiv 1 \mod 365$, apply the Chinese Remainder theorem with $x \equiv ±1 \mod 5$. – J. Linne Dec 10 '20 at 0:34