Solving simple mod equations

Question

Solve $3x^2 + 2x + 1 \equiv 0 \mod 11$

Additionally, I have an example problem, but a step in the middle has confused me:

$3x^2 + 5x - 7 \equiv 0 \mod 17$. Rearrange to get $3x^2 + 5x \equiv 7 \mod 17$.

$\implies 6\cdot 3x^2 + 6\cdot 5x \equiv 6*7 \mod 17$.

The next line reads $x^2 + 30x \equiv 8 \mod 17$, which I am confused about; I understand how $8$ came to be ($42 - 34$, reduced to $8$) but what happened to the coefficient of $3x^2$? This example is from my notes in NT class, so perhaps I copied something incorrectly, or did I?

For the first problem, you don't need to finish the whole problem. Once you get to a point where it looks something like $(x+15)^2 \equiv 10 \mod 17$ (result of the example problem), I know how to proceed. It's the beginning parts that have muddled me a bit...

Help would be greatly appreciated.

Answer 1

One way is to multiply through by $3$ to get the equivalent congruence $9x^2+6x+3\equiv 0\pmod{11}$. Then rewrite as $(3x+1)^2+2\equiv 0\pmod{11}$. We get lucky because this can be rewritten as $(3x+1)^2\equiv 9\pmod{11}$.

Remark: In general, if we are looking at the congruence $ax^2+bx+c\equiv 0\pmod{m}$, where $m$ is odd and relatively prime to $a$, one can multiply through by $4a$ and then complete the square. In our case, since $b$ was even, we could more simply multiply through by $a$.

Alternately, for out particular problem, we could multiply through by the inverse of $3$ modulo $11$. So multiply through by $4$, and again complete the square. That was the strategy used in the worked example modulo $17$. Since $3\cdot 6=18\equiv 1\pmod{17}$, $6$ is the moduloar inverse of $3$, and multiplying throgh by $6$ leaves us with a quadratic congruence with the lead coefficient of the quadratic equal to $1$.

Answer 2

Note that $3 \equiv 5^2$, therefore $3x^2 +2x +1 \equiv 5^2x^2 + 2 \cdot 5 \cdot 5^{-1} x + 5^{-2} - 5^{-2} +1$ and since $5^{-1} \equiv 9$ this means $3x^2 +2x +1 \equiv 5^2x^2 + 2 \cdot 5 \cdot 9 x + 9^2 - 3 \equiv (5x + 9)^2 - 3$, so you want to solve $(5x + 9)^2 \equiv 3 \equiv 5^2$, therefore $(5x + 9) \equiv \pm 5$, giving $5x \equiv 7$ and $5x \equiv 8$, giving $x \equiv 8$ and $x \equiv 6$.

Answer 3

$3x^2 + 2x + 1 \equiv 0 \pmod{11}$

Since $3 \cdot 4 \equiv 12 \equiv 1 \pmod{11}, \quad \frac 13 \equiv 4 \pmod{11}$

So, multiplying both sides by $4$, we get

$x^2 + 8x + 4 \equiv 0 \pmod{11}$

Half of $8$ is $4$ and $4^2 = 16 \equiv 5 \pmod{11}$. So

$x^2 + 8x + 4 \equiv x^2 + 8x + 5 - 1 \equiv (x+4)^2 - 1 \pmod{11}$

So you get

$(x+4)^2 - 1 \equiv 0 \pmod{11}$

$(x+4)^2 \equiv 1 \pmod{11}$

$x+4 \equiv 1 \pmod{11} \quad \text{or} \quad x+4 \equiv -1 \pmod{11}$

$x \equiv 8 \pmod{11} \quad \text{or} \quad x \equiv 6 \pmod{11}$

Note that this implies

$3x^2+2x+1 \equiv 3(x-6)(x-8) \pmod{11}$