7
$\begingroup$

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}$)

$\endgroup$
15
$\begingroup$

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

$\endgroup$
7
  • 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$ 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$ 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$ Jan 2 '13 at 13:33
1
$\begingroup$

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.

$\endgroup$

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.