Showing that $45083$ is prime

463 Views Asked by At

The question is:

Does $\;x^2 + 10x + 15 = 0\pmod{45083}\;$ have a solution?

I can rearrange this to $(x+5)^2 = 10\pmod {45083} \;$ so if I can show that $10$ has a square root mod 45083, I'm done.

If I can show that $45083$ is prime then I can use Legendre symbols and the Law of Quadratic Reciprocity to complete the question.

I don't know how to show that 45083 is prime. I don't think Wilson's theorem is practical. Trial division takes a very long time.

Maybe there is another way?

1

There are 1 best solutions below

6
On

Indeed $\,45,083\,$ is a prime, so by the QRT:

$$\left(\frac{10}{45083}\right)=\left(\frac{2}{45083}\right)\left(\frac{5}{45083}\right)\stackrel{45083\neq\pm 1\pmod 8}=-\left(\frac{3}5\right)=-(-1)=1$$