# Convenient no.s

Call a natural number n "convenient", if n^2 + 1 is divisible by 1000001. Prove that among the numbers 1, 2, ... , 1000000 there are evenly many "convenient" numbers.

I have tried modular arithmetic but I m unable to understand the meaning of evenly convenient no.s neither I am able to solve it. The question is from Mathematical circles (Russian Experience).Please help

• For what it's worth, I feel like "evenly many" refers to "there are an even number of". Mathematically, this would likely be interpreted as the quadratic congruence $$n^2 \equiv -1 \pmod {1,000,001}$$ not that I know how to solve such congruences, or find the number of solutions to them myself. But it might be worth looking into. – Eevee Trainer Mar 20 '19 at 7:02

And no, we don't need to find all of the solutions, or even exactly how many there are. We just need a symmetry relation: if $$n$$ is a solution, so is $$1000001 - n$$.
• There is a minute chance of overcounting for we might have an occasion when $n=1000001-n$. Let's leave ruling out that possibility in the present case for the OP :-) – Jyrki Lahtonen Mar 20 '19 at 7:24