How can I solve a certain congruence equation?

Question

I want to solve the congruence $3x^2 + 6x + 1 \equiv 0 \pmod {19}$.

I know that one way to solve this is to first solve the congruence: $t^2 \equiv 5 \pmod {19}$, because $b^2 - 4ac \equiv 24 \equiv 5 \pmod {19}$.

The problem is that I am having difficulties even solving the congruence $t^2 \equiv 5 \pmod {19}$.

Does anybody have an idea how to solve either of the two above congruences?

Answer 1

sol = Solve[ 3 x^2 + 6 x + 1 == 0, x, Modulus -> 19]

or

Reduce[3 x^2 + 6 x + 1 == 0, x, Modulus -> 19]

Confirm:

Mod[3 x^2 + 6 x + 1, 19] /. sol

Answer 2

An alternative solution of these types of congruences is possible via completing the square (as you alluded to with variable t) and using PowerModList.

3 x (x + 2) = -1,  mod 19
3 x (x + 2) = 18,  mod 19
x (x + 2) = 6,     mod 19
(x + 1)^2 = 7,     mod 19

Now let t = x + 1 and solve Mod[t^2,19]=7 for t with PowerModList.

t -> PowerModList[7, 1/2, 19]

t -> {8, 11}

Hence, x -> {7, 10}.