1. ## Modular solutions question

Which of the following equations have a solution?

(a) $\displaystyle x^2 \equiv$ $\displaystyle 17$ ($\displaystyle mod$ $\displaystyle 29$)

(b) $\displaystyle 3x^2 \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)

(c) $\displaystyle 2x^2 \equiv$ $\displaystyle 27$ ($\displaystyle mod$ $\displaystyle 41$)

(d) $\displaystyle x^2 +5x \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)

Could anyone show me how to solve these step by step? I can't just submit my answers as 'has a solution', 'has no solution.' Thanks!

2. Originally Posted by Proof_of_life
Which of the following equations have a solution?

(a) $\displaystyle x^2 \equiv$ $\displaystyle 17$ ($\displaystyle mod$ $\displaystyle 29$)

(b) $\displaystyle 3x^2 \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)

(c) $\displaystyle 2x^2 \equiv$ $\displaystyle 27$ ($\displaystyle mod$ $\displaystyle 41$)

(d) $\displaystyle x^2 +5x \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)

Could anyone show me how to solve these step by step? I can't just submit my answers as 'has a solution', 'has no solution.' Thanks!
These are problems based on quadratic residues.I hope you are familiar with the legendre symbol. For reference, if p is an odd prime...

(a) Compute $\displaystyle \left(\frac{17}{29}\right)$

(b) Since (31,3) = 1, compute $\displaystyle \left(\frac{4}{31}\right)$

(c) $\displaystyle 2x^2 \equiv$ $\displaystyle 27$ ($\displaystyle mod$ $\displaystyle 41$) is same as $\displaystyle 2x^2 \equiv$ $\displaystyle -14$ ($\displaystyle mod$ $\displaystyle 41$). Again we have (2,41) = 1. Therefore compute $\displaystyle \left(\frac{34}{41}\right)$

(d)This one is interesting. You have to transform this quadratic congruence to linear by completing the squares and then find the quadratic residue

3. Originally Posted by Proof_of_life
Which of the following equations have a solution?

(a) $\displaystyle x^2 \equiv$ $\displaystyle 17$ ($\displaystyle mod$ $\displaystyle 29$)

(b) $\displaystyle 3x^2 \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)

(c) $\displaystyle 2x^2 \equiv$ $\displaystyle 27$ ($\displaystyle mod$ $\displaystyle 41$)

(d) $\displaystyle x^2 +5x \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)

Could anyone show me how to solve these step by step? I can't just submit my answers as 'has a solution', 'has no solution.' Thanks!
There are probably theorems involved there that I don't know, but here goes:
a) You can get this simply by a listing. No number a modulo 29 has 17 as its square. There is no solution.

b)
$\displaystyle 3x^2 \equiv 12~\text{(mod 31)}$

$\displaystyle 3x^2 - 12 \equiv~0\text{(mod 31)}$

$\displaystyle 3(x^2 - 4) \equiv~0\text{(mod 31)}$

$\displaystyle x^2 - 4 \equiv~0\text{(mod 31)}$

$\displaystyle x^2 \equiv 4 \text{(mod 31)}$

$\displaystyle x \equiv 2, 29$

c)
$\displaystyle 2x^2 \equiv 27~\text{(mod 41)}$

$\displaystyle 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod 41)}$

$\displaystyle x^2 \equiv 34~\text{(mod 41)}$
and this has no solution.

d)
$\displaystyle x^2 + 5x \equiv 12~\text{(mod 31)}$

Complete the square:
$\displaystyle x^2 + 5x + 14 \equiv 26~\text{(mod 31)}$
(Just as a note:
$\displaystyle \frac{5}{2} \to 16 \cdot 5 \equiv 18$
So add $\displaystyle 18^2 \equiv 14$
to both sides.)

$\displaystyle (x + 13)^2 = 26~\text{(mod 31)}$
and this has no solution for x + 13, so there is no solution for x.

-Dan

4. Hello,

and this has no solution.
and this has no solution for x + 13, so there is no solution for x.
So how do you know for it ?
Testing for all the congruences ?

5. Originally Posted by Moo
Hello,

So how do you know for it ?
Testing for all the congruences ?
Yup. I'm taking the "uneducated lout" method and working through the possibilities one by one. I haven't learned how to evaluate Legendre symbols. (And couldn't even remember the name for them until Isomorphism posted it.)

-Dan

6. Originally Posted by topsquark
Yup. I'm taking the "uneducated lout" method and working through the possibilities one by one. I haven't learned how to evaluate Legendre symbols. (And couldn't even remember the name for them until Isomorphism posted it.)

-Dan
I don't know either ~
But it's quite a tough job to do this way

7. Thanks guys! That helps a lot.

8. You can kill these problems with the Golden theorem.
Originally Posted by Proof_of_life
(a) $\displaystyle x^2 \equiv$ $\displaystyle 17$ ($\displaystyle mod$ $\displaystyle 29$
$\displaystyle (17/29) = (29/17) = (12/17) = (3/17) = (17/3) = (2/3) = (-1)^{(3^2-1)/8} = -1$.

(b) $\displaystyle 3x^2 \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)
First $\displaystyle 3^{-1} \equiv 21$ so we get $\displaystyle x^2 \equiv 4(\bmod 31)$. That is definitely solvable.

(c) $\displaystyle 2x^2 \equiv$ $\displaystyle 27$ ($\displaystyle mod$ $\displaystyle 41$)
Note $\displaystyle 2^{-1}\equiv 21$ so $\displaystyle x^2\equiv -7(\bmod 41)$.
$\displaystyle (-7/41) = (-1/41)(7/41) = (-1)^{(41-1)/2}(7/41)$$\displaystyle = (41/7) = (-1/7) = (-1)^{(7-1)/2} = -1$.

(d) $\displaystyle x^2 +5x \equiv$ $\displaystyle 12$ ($\displaystyle mod$ $\displaystyle 31$)
$\displaystyle 5\equiv 36(\bmod 31)$ thus $\displaystyle x^2 + 36x\equiv 12(\bmod 31)$. Add $\displaystyle 324$ to both sides to get $\displaystyle (x+18)^2\equiv -5(\bmod 31)$.
$\displaystyle (-5/31) = (-1/31)(5/31) = -(31/5)=-(1/5) = -1$

9. Hi

Originally Posted by topsquark
c)
$\displaystyle 2x^2 \equiv 27~\text{(mod 41)}$

$\displaystyle 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod 41)}$

$\displaystyle x^2 \equiv 34~\text{(mod 41)}$
and this has no solution.
Shouldn't the second line be $\displaystyle 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod} \,41{ \color{red}\cdot 21}\text{)}$ ?

10. Originally Posted by Moo
I don't know either ~
But it's quite a tough job to do this way
I have a nice calculator.

-Dan

11. Originally Posted by flyingsquirrel
Hi

Shouldn't the second line be $\displaystyle 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod} \,41{ \color{red}\cdot 21}\text{)}$ ?
No. 21 is the multiplicative inverse of 2 a modulo 41, so all I am doing here is "dividing" both sides by 2.

-Dan

12. Hi

Originally Posted by topsquark
c)
$\displaystyle 2x^2 \equiv 27~\text{(mod 41)}$

$\displaystyle 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod 41)}$

$\displaystyle x^2 \equiv 34~\text{(mod 41)}$
and this has no solution.
Shouldn't the second line be $\displaystyle 21 \cdot 2x^2 \equiv 21 \cdot 27~\text{(mod} \,41{ \color{red}\cdot 21}\text{)}$ ?
Why? One is allowed to multiply congruences by the same number without changing the modulos of the congruence?

13. Originally Posted by topsquark
No. 21 is the multiplicative inverse of 2 a modulo 41, so all I am doing here is "dividing" both sides by 2.
OK
Originally Posted by ThePerfectHacker
Why? One is allowed to multiply congruences by the same number without changing the modulos of the congruence?
Yes, that's right that it doesn't change anything as long as one works with implications. I never thought about this and I always multiplied the modulos each time I multiplied the congruences.

14. Originally Posted by flyingsquirrel
Yes, that's right that it doesn't change anything as long as one works with implications.
Hmm... where does it not work?

15. For example : $\displaystyle x \equiv 0\,[2] \Rightarrow 2x \equiv 0\,[2]$ but the other way is wrong : $\displaystyle 2x \equiv 0\,[2] \not \Rightarrow x \equiv 0\,[2]$

If we multiply the modulo and the congruence by 2, both ways are correct : $\displaystyle x \equiv 0\,[2] \Leftrightarrow 2x \equiv 0\,[4]$

Page 1 of 2 12 Last