How to correctly prove whether $\exists x \in \mathbb{Z}: x^{2} \equiv 43 (\mod 9999)$

Question

I need to prove whether or not there exists an integer $x$ satisfying $x^{2} \equiv 43 (\mod 9999)$.

So far, I have done the following:

We have $x^{2} \equiv 43 (\mod 9999)$ iff $x^{2}-43 = 9999n$. Therefore, by the division algorithm, $x$ must have one of the $9999$ forms: $x = \begin{cases} 9999 n \\ 9999n + 1 \\ 9999n + 2 \\ \vdots \\ 9999n+9998\end{cases}$, which implies that

$x^{2}-43 = \begin{cases} (9999n)^{2}-43 \\ (9999n+1)^{2}-43 \\ (9999n+2)^{2}-43 \\ \vdots \\ (9999n+6)^{2}-43 \\ (9999n+7)^{2} - 43 \\ \vdots \\ (9999n+9998)^{2}-43 \end{cases} = \begin{cases} (9999)^{2}n^{2}-43 \\ (9999)^{2}n^{2}+2(9999n)-42 \\ (9999)^{2}n^{2}+4(9999n)-39 \\ \vdots \\ (9999)^{2}n^{2}+12(9999n)-7 \\ (9999)^{2}n^{2}+14(9999n)+6\\ \vdots \\ (9999)^{2}n^{2}+19996(9999n)+99959961 \end{cases}$

Then, we see that for any $x$, we never have $x^{2} - 43 = 9999k$, $k \in \mathbb{Z}$ (since $43$ is not a perfect square). Therefore, $\nexists$ an integer $x$ satisfying $x^{2} \equiv 43(\mod 9999)$.

However, after I showed this to my professor, he said that this is just an approach, and not a complete argument. He said that to make it a complete argument, one has to list all the calculations so it could be checked.

I'm not entirely sure what he meant by this...

Could somebody please explain to me how I can make this into a complete argument?

Thank you.

Answer 1

I think that the problem that your professor has with your approach is that it doesn't make it clear that you have actually proven the result. While it would work in principal, it would require anyone who wanted to check it to actually do $9999$ calculations, none of which are carried out explicitly. Looking at what you've written, there is no immediate way to deduce that the answer is "yes" or "no"; there is just a block of implicit calculations, and it is implied without justification that all of them would lead to the conclusion that you want to draw.

There is a simpler way to show that there is no integer $x$ with $x^2 \equiv 43 \pmod{9999}$, which requires a lot fewer calculations.

We notice that $9999$ is divisible by $11$, and so if $x^2 \equiv 43 \pmod{9999}$, then also $x^2 \equiv 43 \equiv 10 \pmod{11}$.

At this point, you can square every number from $0$ to $10$ and see that none of them leave a remainder of $10$ when divided by $11$.

Alternatively, you can argue that since $11$ is a prime congruent to $3$ mod $4$, that $-1$ is not a quadratic residue modulo $11$.

As a final possibility, you could also note that $x^2 \equiv 10 \pmod{11}$ implies that $x^{10} \equiv 10^5 \equiv (-1)^5 \equiv -1 \pmod{11}$. But by Fermat's Little Theorem, we should have that $x^{10} \equiv 0 \text{ or } 1 \pmod{11}$, so this would be a contradiction.

Answer 2

Let me change the constants in your equation and ask whether you can have $x^2\equiv 2 \pmod {79}$ I could write the same lines you have done and at the end say we never have $x^2-2=79k$ since $2$ is not a perfect square, but $9^2-2=79\cdot 1$. Numbers which are not squares in $\Bbb Z$ can be squares in $\Bbb Z/n\Bbb Z$ as this example shows. I suspect you are expected to use quadratic reciprocity.

Answer 3

$9999|x^2-43$ means $k|x^2-43$ if $k|9999$.

So $x^2 \equiv 1\mod 3$ so $x=1+3k $

$x^2\equiv -1 \mod 11$. This one we know has no solution as i) the squares of $0...,10$ are not equivalent to $-1$ modulo 11. ii) Fermats Little Theorem say $x^{10}\equiv 1 \mod 11$ but $(x^2)^5\equiv -1 \not \equiv 1 \mod 11$.

We would also need $x^2\equiv 43\equiv 144\mod 101$ so $x=12 + 101k $ but as we know there are no solutions we needn't bother.