# $3x^2 ≡ 9 \pmod{13}$

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.

$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.

• Thanks. Can you explain briefly what a field is? Or provide an alternative explanation using high-school level expressions :) – random guy Jan 2 '13 at 13:10
• @randomguy The hey is that $13$ is prime, so a polynomial equation of degree $n$ can have at most $n$ roots modulo any prime. – Thomas Andrews Jan 2 '13 at 13:19
• @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$). – Clive Newstead Jan 2 '13 at 13:21
• 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)) – random guy Jan 2 '13 at 13:25
• @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! – Jyrki Lahtonen Jan 2 '13 at 13:33