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

  • $\begingroup$ 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. $\endgroup$ – Eevee Trainer Mar 20 '19 at 7:02

As noted in the comments, "evenly many" here simply means that the number of solutions is even.

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

| cite | improve this answer | |
  • $\begingroup$ 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 :-) $\endgroup$ – Jyrki Lahtonen Mar 20 '19 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.