Number of roots of a quadratic equation modulo 325

Question

Any Help solving this question ?

a) Find ONE solution $\overline x\in\Bbb Z/325\Bbb Z$ such that $x^2\equiv-1\pmod{325}$. (Hint: CRT and lifting.)

b) How many solutions $\overline x$ to the above equation are there, and why?

Answer 1

$325=5^2\cdot 13$ so let's solve $x^2\equiv -1\pmod{25}$, $x^2\equiv -1\pmod{13}$.

Case $1$: $\mod{25}$

If $x^2\equiv -1\pmod{25}$, then $x^2\equiv -1\pmod 5$ so $x\equiv\pm2\pmod 5$

$$(5k+2)^2=25k^2+20k+4\equiv 20k+4\equiv-1\pmod{25}\implies 4k\equiv -1\pmod 5\\\implies k\equiv 1\pmod 5$$ $$(5k-2)^2=25k^2-20k+4\equiv -20k+4\equiv-1\pmod{25}\implies 4k\equiv 1\pmod 5\\\implies k\equiv 4\pmod 5$$ So we have $x^2\equiv-1\pmod{25}\implies x\equiv\pm7\pmod{25}$

Case $2$: $\mod 13$

We see upon inspection that $x^2\equiv -1\pmod{13}\implies x=\pm 5$

See if you can use CRT to find all solutions to $x^2\equiv -1\pmod{325}$

Answer 2

We can prove by using Discrete Logarithm and Linear Congruence Theorem that $x^2\equiv a\pmod m$ has zero or two solutions if $m$ has a primitive root.

Now, $\displaystyle x^2\equiv-1\pmod{325}\equiv-1\pmod{25}$

$\displaystyle x^2\equiv-1\equiv49\pmod{25}\equiv7^2\implies x\equiv\pm7\pmod{25}\ \ \ \ (1)$

Again, $x^2\equiv-1\pmod{325}\equiv-1\pmod{13}$

$\displaystyle x^2\equiv-1\pmod{13}\equiv25\equiv5^2\implies x\equiv\pm5\pmod{13}\ \ \ \ (2)$

Now apply CRT on $(1),(2)$ to find four in-congruent solutions