1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ x = -9 also works. $ (-9)^2 + 4(-9) + 1 = 46 \equiv 0 (mod \ 23) $ $\endgroup$ – neofoxmulder Feb 9 '14 at 21:30
  • 1
    $\begingroup$ don't know how I got this wrong. Anyway, isn't -9 the same as 14, but just applying the modulo? Thanks, this answers one of my questions. $\endgroup$ – bitoiu Feb 9 '14 at 22:49
  • $\begingroup$ Yes , that's true. x = -18 also works , note $-18 \equiv 5 \ (mod \ 23)$. I am an amateur so i don't know too much but $\frac{\sqrt{12}}{2} = \frac{ 2 \sqrt{3}}{2} = \sqrt{3}$. Also note you can add 3 to both sides of the congruence to complete the square , then you get $(x+2)^2 \equiv 3 \ (mod \ 23) \ --> \ x \equiv -2 \pm \sqrt{3} \ (mod \ 23)$ which is exactly what you got using the quadratic formula (except the mod part but you know how to take care of that little detail right?) This bypasses a lot of arithmetic. :) $\endgroup$ – neofoxmulder Feb 9 '14 at 23:09
  • 1
    $\begingroup$ thanks for your comment, there are infinite solutions on MOD, -18 is the same as 5 and that would be the same as 28. Regarding your second observation, does that explain the answer to my first question? How do we go from $\sqrt(12)$ to $\sqrt(3)$ $\endgroup$ – bitoiu Feb 10 '14 at 9:56
  • $\begingroup$ $\sqrt{12} = \sqrt4 \sqrt 3 = 2 \sqrt 3$. $\endgroup$ – steven gregory Feb 26 '16 at 17:25
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Hi, you're answered two of my questions, so I'll accept your answers, very useful. To decompose $\sqrt{12}$ like you did, you would need to know all the other roots. Would you do that as part of your normal process? $\endgroup$ – bitoiu Feb 10 '14 at 21:40
  • 1
    $\begingroup$ For this problem , not at this time because i can get the same answer by finding root 12 (mod 23). Decomposing root 12 (mod 23) is interesting to me but it seems like a lot of un-necessary work , but i may change my mind if there is an application for the decompositin of root a in (mod p). I am updating my answer after reading the lnk you provided more carfullly. Thank you for posting this question along with your work on it becaus it has given me the opportunity to learn more about this interesting subject. :) $\endgroup$ – neofoxmulder Feb 11 '14 at 3:40
  • 1
    $\begingroup$ you thanking me? Nonsense, thanks for the post, it will be helpful for a long time after this. Thank you very much. $\endgroup$ – bitoiu Feb 11 '14 at 10:40
0
$\begingroup$

If you divide x^2 + 4x + 1 by 23, the only values of x that work are 5 and 14.

So x = 5 mod 23 and x = 14 mod 23.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.