Find all solutions of

$$\large x^2 \equiv 11 \pmod{3167}$$

Question

Find all solutions of

$$\large x^2 \equiv 11 \pmod{3167}$$

perl · Answer

x = 1417 mod 3167
x = -1417 mod 3167

perl · Answer

(this is not the most efficient approach)
To solve this ,since 3167 is prime
x^2 = 11 mod 3167
x^2 - 11 = 0 mod 3167
(x - sqrt(11) ) ( x + sqrt(11)  = 0 mod 3167
x = sqrt(11) 
x = - sqrt(11)
We need to find the square root of 11 modulo 3167
by squaring every number from 0 to 3167 (in fact we only need to go halfway) and reducing modulo 3167, we can see that x = 1417

ganeshie8 · Answer

Yes! those are all the solutions

mathmath333 · Answer

@perl how did u find "square root of 11 mod 3167".

perl · Answer

i used this calculator http://www.numbertheory.org/php/squareroot.html

perl · Answer

enter a: 11
m : 3167

mathmath333 · Answer

ok

perl · Answer

there is a better way to solve this, using number theory

ganeshie8 · Answer

wolfram is pretty good wid modular arithmetic too http://www.wolframalpha.com/input/?i=x%5E2%3D11+mod+3167

ganeshie8 · Answer

yes there is a nice simple formula..

ganeshie8 · Answer

$$x^2\equiv a \pmod{p} \iff x \equiv  \pm  a^{(p+1)/4} \pmod{p}$$

ganeshie8 · Answer

that works always except when $p$ is of form $4k+1$

perl · Answer

oh 
-1417 = 1750 mod 3167

ganeshie8 · Answer

yes :) atmost two solutions are possible as the degree is $2$

mathmath333 · Answer

i thought u used primitive roots to solve this

ganeshie8 · Answer

Exactly! that formula was derived using primitive roots

ganeshie8 · Answer

we don't need to use that formula if we know a primitive root... then we can directly take discrete logarithm both sides

but we're not given a primitive root of 3167 in the problem, so...

mathmath333 · Answer

this case is for prime $p$ only or for prime and  composite both

$x^2\equiv a \pmod{p} \iff x \equiv  \pm  a^{(p+1)/4} \pmod{p}$

ganeshie8 · Answer

$p$ must be a prime

ganeshie8 · Answer

see if it really works using below simple example : $$x^2 \equiv 2 \pmod{7}$$

perl · Answer

so the problem reduces to solving
$$

\Large { x = \pm 11^{\frac{3167 + 1}{4}} \mod {3167}\
x = \pm 11^{792} \mod {3167}\
 

}$$

ganeshie8 · Answer

yes $x=\pm 11^{792}$ is a legitimate answer :)

perl · Answer

is there a way to simplify that , so it is less than 3167

ganeshie8 · Answer

http://www.wolframalpha.com/input/?i=11%5E792+mod+3167

mathmath333 · Answer

in case i know the primitive root is $5$ then how to solve further


$\large \color{black}{\begin{align} 2\text{ind}_5x\equiv \text{ind}_511 \pmod {3166}\hspace{.33em}\~\



\end{align}}$

ganeshie8 · Answer

thats a neat way to solve this! xD
lets see...

ganeshie8 · Answer

solve $\text{ind}_5x$ first

mathmath333 · Answer

how

mathmath333 · Answer

and how to form table for this upto 10

ganeshie8 · Answer

solving is exactly same as solving any logarithm equation

ganeshie8 · Answer

$$\large \color{black}{\begin{align} 2\text{ind}_5x\equiv \text{ind}_511 \pmod {3166}\hspace{.33em}\~\



\end{align}}$$

is exactly same as

$$\large \color{black}{\begin{align} 2\text{log}_5x\equiv \text{log}_511 \pmod {3166}\hspace{.33em}\~\



\end{align}}$$

ganeshie8 · Answer

how do we solve a logarithm equation ? 
first we need to "have" the value of $\log_5 11$
we need to look up in logarithm table because computing it manually is a pain

ganeshie8 · Answer

basically we need the discrete logarithm table for base 5.. 
we can form a table but hmm... nobody cooks up logarithm tables everytime they face with a log equation... they just look up preexisting logarithm tables right

mathmath333 · Answer

ok how to compute that with wolfram $ind_5=11$

ganeshie8 · Answer

one sec..

mathmath333 · Answer

i mean $\text{ind}_511$

mathmath333 · Answer

is it this one http://www.wolframalpha.com/input/?i=solve+5%5E%28x%29+mod+3166%3D11+over+integers

ganeshie8 · Answer

for $\text{ind}_5 11$,   weneed to solve 
$$11 = 5^x \pmod{316\color{red}{7}}$$

ganeshie8 · Answer

also there is a direct command for discretelogarithm : http://www.wolframalpha.com/input/?i=MultiplicativeOrder%5B5%2C+3167%2C+%7B11%7D%5D

mathmath333 · Answer

ok $2476$

ganeshie8 · Answer

yes plug that in  and solve ind_5 x

ganeshie8 · Answer

$$\large \color{black}{\begin{align} 2\text{ind}_5x\equiv \text{ind}_511 \pmod {3166}\hspace{.33em}\~\



\end{align}}$$

$$\large \color{black}{\begin{align} 2\text{ind}_5x\equiv 2476 \pmod {3166}\hspace{.33em}\~\



\end{align}}$$

simply divide $2$ through out

ganeshie8 · Answer

we get
$$\large \color{black}{\begin{align} \text{ind}_5x\equiv 1238 \pmod {1583}\hspace{.33em}\~\



\end{align}}$$

mathmath333 · Answer

yes this one

ganeshie8 · Answer

yes solve x

mathmath333 · Answer

$x\equiv 5^{1238} \pmod {1583}$

mathmath333 · Answer

is that correct   $\uparrow$

ganeshie8 · Answer

nope 
1238 is the index of x in  mod 3167  relative to base 5

ganeshie8 · Answer

$$x\equiv 5^{1238} \pmod{\color{Red}{3167}}$$

mathmath333 · Answer

okk

mathmath333 · Answer

y did u write 
1583

$\large \color{black}{\begin{align} \text{ind}_5x\equiv 1238 \pmod {\color{red}{1583}}\hspace{.33em}\~\



\end{align}}$

ganeshie8 · Answer

thats right, there are no typoes

ganeshie8 · Answer

that comes from dividing 2 in :

$$\large \color{black}{\begin{align} 2\text{ind}_5x\equiv 2476 \pmod {3166}\hspace{.33em}\~\



\end{align}}$$

mathmath333 · Answer

ok

ganeshie8 · Answer

I know it is a bit confusing as we're changing modulus back and forth among 3 different numbers :  3167, 3166, 1583

it just takes some more practice to see whats going on clearly