Find the solution for $x$ with $0 \le x \lt 13$ so $13 \mid 3x^2+9x+7 $.

Question

Find the solution for $x$ with $0 \le x \lt 13$ so $13 \mid 3x^2+9x+7 $.
I got this question in my discrete mathematics class.
I don't really get the idea how 13 can divide $3x^2+9x+7 $
All of my friend told me to try all the number between 0 and 12, but I know that's not how to solve this question.
Can anyone help me?
Thanks.

Answer 1

Let's work in $\mod 13$. We want $3x^2+9x+7 \equiv 0 \pmod {13}$. Now $7 \equiv -6$ so you have $3x^2+9x-6 \equiv 0 \pmod {13}$. Because $\gcd(3, 13) = 1$, we can "divide both sides" by $3$ and get $x^2+3x-2 \equiv 0 \pmod {13}$

Notice that $-2 \equiv -28$, so $x^2+3x-28 \equiv 0 \pmod {13}$ which you can factor to $(x-4)(x+7)\equiv 0 \pmod {13}$. Because $13$ is prime, we have $x \equiv 4$ or $x \equiv -7 \equiv 6$.

Answer 2

Actually that's a perfectly good way to solve this question! You have 13 numbers to check, which sounds quite reasonable.

You can make it a bit easier, though: $7 = 13 - 6$, and $13$ divides the $13$ we just made, so $13 \mid 3x^2+9x+7$ iff $13 \mid 3x^2+9x-6$; that is, iff $13 \mid 3(x^2+3x-2)$; that is, iff $13 \mid x^2+3x-2$. That just makes the numbers a bit simpler.

If you want to be even more clever, notice that $$x^2+3x-2 = x^2+3x-28+26 = (x-4)(x+7) + 2 \times 13$$ so $13 \mid x^2+3x-2$ iff $13 \mid (x-4)(x+7)$. I don't really know how one would come up with that, though, other than magic.

Answer 3

The discriminant of the equation $3x^2+9x+7=0$ equals $81-4 \cdot 9 \cdot 7=-3=10=7^2 \mod 13$. Taking into account that $3^{-1}=9 \mod 13$ we have $$ x_1=\frac{-9+7}{6}=\frac{-2}{6}=-\frac{-1}{3}=-9=4 \mod 13, $$ $$ x_2=\frac{-9-7}{6}=\frac{-16}{6}=\frac{-8}{3}=-8 \cdot 9=5 \cdot 9=45=6 \mod 13. $$

Thus $x=4$ and $x=6.$