(i) Show that the quadratic congruence $ax^2 + bx + c \equiv 0 \pmod p$ where $p \not \mid a$ can be written as
$$ y^2 \equiv m \pmod p $$
(ii) Solve the following quadratic congruences, all moduli are prime:
(a) $2x^2 + 2x + 1 ≡ 0 \pmod {29}$
(b) $5x^2 + 9x + 4 ≡ 0 \pmod {101}$
(c) $7x^2 + 9x + 3 ≡ 0 \pmod {41}$
(d) $2x^2 + 20x + 49 ≡ 0 \pmod {61}$
(i) We "complete the square" for the expression $ax^2 + bx + c$.
$$ ax^2 + bx + c = a \biggl ( x^2 + \frac{bx}{a} + \frac{b^2}{4a^2} \biggr ) + (c - \frac{b^2}{4a}) = a \biggl ( x + \frac{b}{2a} \biggr ) ^2 + (c - \frac{b^2}{4a}) $$
This suggests we multiply throughout by $4a$
$$ 4a(ax^2 + bx + c) = 2^2a^2 \biggl ( x + \frac{b}{2a} \biggr ) ^2 + (4ac - b^2) = ( 2ax + b ) ^2 + (4ac - b^2) $$
Going back to the congruence and multiplying by $4a$ gives
$$ \begin{align} ax^2 + bx + c & \equiv 0 \pmod p \\ \\ 4a(ax^2 + bx + c) & \equiv 0 \pmod p \tag{*} \\ \\ ( 2ax + b ) ^2 + (4ac - b^2) & \equiv 0 \pmod p \\ \\ ( 2ax + b ) ^2 & \equiv (b^2 - 4ac) \pmod p \end{align}$$
So the congruence can be written in the form $y^2 \equiv m \pmod p$, where $y = (2ax + b)$ and $m = (b^2-4ac)$.
Because $p \not \mid a$, multiplying by $4a$ at line (*) does not introduce incorrect solutions to the congruence. That is, we can't conclude that $4a \equiv 0 \pmod p$. Note that this does require $p \ne 2$, not made clear in the exercise.
(ii)
(a) We can rewrite $2x^2 + 2x + 1 ≡ 0 \pmod {29}$ as
$$ (4x + 2)^2 \equiv 25 \pmod {29} $$
This gives us $(4x+2) \equiv \pm 5 \pmod {29}$, which gives us $4x \equiv 32 \pmod {29}$, and $4x \equiv 80 \pmod {29}$. The solutions for $x$ are $x \equiv 8 \pmod {29}$ and $x \equiv 20 \pmod {29}$.
(b) We can rewrite $5x^2 + 9x + 4 ≡ 0 \pmod {101}$ as
$$ (10x + 9)^2 \equiv 1 \pmod {101} $$
This gives us $(10x + 9) \equiv \pm 1 \pmod {101}$, which gives us $10x \equiv 800 \pmod {101}$, and $10x \equiv 1000 \pmod {101}$. The solutions for $x$ are $x \equiv 80 \pmod {101}$ and $x \equiv 100 \pmod {101}$.
(c) We can rewrite $7x^2 + 9x + 3 ≡ 0 \pmod {41}$ as
$$ (14x+9)^2 \equiv 38 \pmod {41} $$
Trial and error does not appear to find a value congruent to $38 \pmod {41}$ that is a square, so we use Euler's Criterion to check whether a solution exists.
We have $41 \not \mid 38$, and
$$ 38^{\frac{41-1}{2}} \equiv 38^{20} \equiv (38^2)^10 \equiv 9^10 \equiv 3486784401 \equiv -1 \pmod {41} $$
This means the congruence has no solution.
(d) We can rewrite $2x^2 + 20x + 49 ≡ 0 \pmod {61}$ as
$$ (4x + 20)^2 \equiv 8 \pmod {61} $$
Trial and error does not appear to find a value congruent to $8 \pmod {61}$ that is a square, so we use Euler's Criterion to check whether a solution exists.
We have $61 \not \mid 8$, and
$$ 8^{\frac{61-1}{2}} \equiv 8^{30} \equiv (8^6)^5 \equiv (27)^5 \equiv -1 \pmod {61} $$
This means the congruence has no solution.