Here is my question:

Solve the equation $3m^2\equiv 1\pmod{p}$, where $p$ is some prime.

This seems to be closely related to quadratic residues. For example, if we were to solve $x^2\equiv -1\pmod{p}$, we can conclude that the equation has solutions if and only if $p\equiv 1\pmod{4}$, using the famous Euler's criterion, $$\left(\frac{-1}{p}\right)\equiv (-1)^{\frac{p-1}{2}}\pmod{p}.$$

However, since now the square is multiplied by $3$, I had no idea what to do. I tried multiplying the inverse of $3$ modulo $p$ (assume $p\neq 3$), to get $m^2\equiv 3^{-1}\pmod{p}$ but I don't know if I did anything wrong or is this even the right path to go.

Can anyone help? Thanks in advance.


Multiply through by 3, getting $(3m)^2\equiv{}3\mod{p}$.

Then there are clearly only solutions if 3 is a quadratic residue. Suppose it is, and $3\equiv{a^2}$. Then $3m\equiv{}\pm{a}$.


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.