What is $3x^2 ≡ 9 \pmod{13}$?

By simplifying the expression as $x^2 ≡ 3 \pmod{13}$ and applying brute force I can show that the answers are 4 and 9, but how to approach this in a more efficient way?

I tried by stating that what the expression above says essentially means $13|(3x²-9)$, which only gives me more variables ($3x²-9=13k, k \in \mathbb{Z}$)


We have $13\mid 3(x^2-3)\iff 13\mid(x^2-3)$ as $(3,13)=1$ so, $x^2\equiv3\pmod {13}$.

Now, any number $x$ can be $\equiv 0,\pm1,\pm2,\pm3,\pm4,\pm5,\pm6 \pmod {13}$

So, $x^2\equiv 0,1,4,9,16(\equiv3),25(\equiv 12\equiv-1),36(\equiv10\equiv-3)\pmod {13}$

So, $x\equiv\pm4\pmod {13}$

For a larger prime, we can use Quadratic Reciprocity Theorem, to check the solutions exists or not before the trial as follows:

$$\left(\frac 3{13}\right)\left(\frac{13}3\right)=(-1)^\frac{(13-1)(3-1)}4=1$$

Now, $\left(\frac{13}3\right)=\left(\frac13\right)$ and $y\equiv\pm1\iff y^2\equiv1\pmod 3\implies \left(\frac{13}3\right)=1\implies \left(\frac{13}3\right)=1$ hence $3$ is a quadratic residue of $13$ and the given equation is solvable.

| cite | improve this answer | |

$x^2\equiv 3 \equiv 16 \pmod {13}$.

So, this equation has solution $x\equiv \pm 4\pmod {13}$. And we know polynomial over a field of degree n has at most n solutions. Since $\mathbb{F}_{13}$ is field, this equation has at most 2 solution.

| cite | improve this answer | |
  • 1
    $\begingroup$ Thanks. Can you explain briefly what a field is? Or provide an alternative explanation using high-school level expressions :) $\endgroup$ – random guy Jan 2 '13 at 13:10
  • $\begingroup$ @randomguy The hey is that $13$ is prime, so a polynomial equation of degree $n$ can have at most $n$ roots modulo any prime. $\endgroup$ – Thomas Andrews Jan 2 '13 at 13:19
  • 1
    $\begingroup$ @randomguy: A field is an algebraic structure which allows you to do addition, subtraction, multiplication and division. Examples include the rational numbers, the real numbers, the complex numbers, and the integers modulo $p$ for prime $p$. Examples of algebraic structures which are not fields are the integers (e.g. $1$ and $2$ are integers but $\frac{1}{2}$ is not) and the integers modulo $n$ for non-prime $n$ (e.g. $2$ has no inverse modulo $4$). $\endgroup$ – Clive Newstead Jan 2 '13 at 13:21
  • $\begingroup$ But still I don't see how can I come from here to the final result (i.e how to show that 9 is also a solution; 9 isn't not congruent to 4 (mod 13)) $\endgroup$ – random guy Jan 2 '13 at 13:25
  • 4
    $\begingroup$ @randomguy: A possibly more high school level way of saying the stuff about fields is the following. You are looking for integers $x$ (or residue classes mod 13) such that $13\mid(x^2-3)$. As explained by tetori, $x^2-3$ is divisible by 13 if and only if $x^2-16=(x-4)(x+4)$ is divisible by 13. As 13 is a prime, this happens exactly when 13 divides either $x-4$ or $x+4$. There you have your answer! $\endgroup$ – Jyrki Lahtonen Jan 2 '13 at 13:33

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.