# Number theory related question

I was trying to solve a question by programming , where one needs to find $X$ such that $X^2\;mod\;M=N$ ,such that $0 \le N \lt M \le 10^6$. Now here I was able to prove:

Let $Y = q * M + X$ where $0 \le X \lt M$ and $1 \le q$. So $M-1 \lt Y$
$Y^2 \;mod\; M = ((Y \;mod\; M) * (Y \;mod\; M)) \;mod\; M = (X * X) \;mod\; M = X^2 \;mod\; M$
But $0 \le X \lt M$

So $0 \le X \lt M$

However few optimisations has been suggested(In the given answer in book) such that :

1.) $\sqrt{N} \le X \lt M$
2.)Further it is also mentioned that the value of $X^2\;mod\;M$ shall repeat from $M/2$ on wards. So we can change the upper bound from $(M-1)$ to $M/2$

How to prove these above two optimsations mathematically?

• Can I please know the reason why it was downvoted? Jun 27, 2018 at 15:33
• It does not appear you used MathJax or LaTeX, which are probably the main reasons. Jun 27, 2018 at 15:50
• Is this ok now? Jun 27, 2018 at 16:29
• It’s better. What does the percent symbol mean? Jun 27, 2018 at 16:34
• Thanks...I have mentioned that Jun 27, 2018 at 16:46