solve x^2=2 mod 100049

i know that 2 is a QR since (2/p)=1

i tried to consider x^2-2=0 mod p
as well as looked at manipulating factors of p-1 and (p-1)/2

the solutions are
10948 and 89101

2. Originally Posted by steiner
solve x^2=2 mod 100049

i know that 2 is a QR since (2/p)=1

i tried to consider x^2-2=0 mod p
as well as looked at manipulating factors of p-1 and (p-1)/2

the solutions are
10948 and 89101

This is not a prime! It factors as $10049 = 13\cdot 773$.

It is therefore not solvable because $(2/13) = (-1)^{(13^2-1)/8} = -1$.

3. the prime number 100049 is prime...
three zeros.

should i attempt trying to apply the CRT... and if so... HOW?

i really thought I was onto something earlier with the factoring a quadratic...

i have found similar algorithms on the internet solving quadratic congruences mod 53 and 19 and such, but i can not replicate them with successful results

but i do know that 2 is a QR mod 100049 and is solvable...