Solving quadratic modulo congruence: review.

Question

I've been trying to solve a quadratic modulo congruence and I think I have the right solution, but in the end there's two things:

1) I cannot explain how $\sqrt(12)$ divided by 2 mod 23 is equal to $\sqrt(3)$. By pure chance I looked at another link to try and understand quadratic modulo function and there's where I took this from (http://web.science.mq.edu.au/~chris/numbers/CHAP03%20Quadratic%20Congruences.pdf)

2) In the end I have two solutions I got to the second one by some trial and error. So I would like to improve this for future scenarios.

Let me explain my rationale:

The congruence is: $$ {x}^2 +4{x} + 1 \equiv 0 \pmod {23}$$

I get this into a quadratic formula

$${x} = \frac {-4 \pm \sqrt{4^2 -4*1*1}}2 $$

which simplifies to:

$${x} = \frac {-4 \pm \sqrt{12}}2 $$

I know $\sqrt{12}$ is valid in$\pmod {23}$ since $gcd(12,23)=1$. However the calculations of the square roots made me think the proble was not being solved correctly, and then on the link provided above I saw a simplification of ${\sqrt{12}\over2} = \sqrt{3}$, which made me try again

Question: I know that dividing by 2 is the same as the multiplicative inverse. So I played with the idea of $\sqrt{12} * 2^{-1} = 12^{-1} * 2^{-1}$ but still I didn't see how this could become $\sqrt{3}$

Assuming this is correct, I proceeded by simplifying the congruence to:

$$x = -2 \pm \sqrt{3}$$

Manually I found that 7 was a square root of 3, and so I proceeded with:

$$x = -2 + 7 \land x= -2 -7 $$ $$x = 5 \land x= -9 $$

I tested both solutions and both work. I didn't use -9, I used -14, since I used the positive MOD of -7.

$$x = 5 \land x= 14 $$

So this worked, both solutions were valid testing against the original formula, but I'm left with quite a few questions:

1. The mentioned above division of the square root?
2. Should I have tried all manual square roots of 3 until 23.
3. Do I have more solutions?

And to finish, if there's anything left I didn't mention and can be improved in my process, please let me know.

I hope this is a valid question.

Kind regards.

Update: I've updated the question due to insightful comments that addressed some of the questions.

Answer 1

I'll try to help. It appears you have some concern about root 12 in mod 23. I do not know if that concern is justified in general. However ,

$ \sqrt{12} = 9 \ \ or \ 14 $

$ \sqrt{4} = 2 \ or \ 21$

$\sqrt{3} = 7 \ or \ 16 $

$ \sqrt{4} \cdot \sqrt{3} = (2 \cdot 7) \ or \ (2 \cdot 16) \ or \ (21 \cdot 7) \ or \ (21 \cdot 16) $

$\sqrt{4} \cdot \sqrt{3} = 14 \ or \ 9 \ or \ 9 \ or \ 14 $

So it looks like we can split up root 12 ,

$ \frac{-4 \ \pm \ \sqrt{12} }{2} = -2 \ \pm \ \frac{\sqrt{4} \cdot \sqrt{3} }{ \sqrt{4}} = -2 \ \pm \ \sqrt{3} $

You can bypass the quadratic formula. Complete the square by adding 3 to both sides of the congruence.

You can always complete the square on any quadratic congruence.

UPDATE: For question 3 , there can be exactly 2 solutions since the mod is prime (23) and co-prime to the coefficient of x^2 (1).

I found a way to make your idea using $ 2^{-1} $ work , the inverse of 2 is 12 in (mod 23) because

$ 2 \cdot 12 \equiv 1 \ (mod \ 23) $

We can then write

$ (-4 \ \pm \ \sqrt{12} ) \cdot 2^{-1} = (-4 \ \pm \ \sqrt{12} ) \cdot 12 $

$ -48 \ \pm \ 12 \cdot \sqrt{12} = -2 \ \pm \ 12(9 \ or \ 14) $

Using 9 for root 12 gives the two solutions for x as you can check.