Thread: quadratic congruence

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

please help me

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

please help me

This is not a prime! It factors as .

It is therefore not solvable because .

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...