(Note: Here numbers mean positive integers, all variables used are positive integers)

This query is regarding a particular question where I need to prove that a particular form of numbers ("particular form of numbers", for example squares, cubes, $4n+1$ etc.) can attain every remainder modulo $n$ for some positive integer $n$.

So my question is, what is the general process to approach this type of problem?

For example suppose we need to find the type of numbers $k$ for which the sequence $1^2, 2^2, 3^2 , \cdots $ contains all the remainders modulo $k$. (That is , the equation $r^2 = x \pmod k$ has a solution $r$ for all $x=1,2, \cdots k$).

So far, I have not been able to make any rigourous proof. So please give some general method to approach these type of question.

  • 3
    $\begingroup$ There isn't any $k>2$ for which the squares contain all the remainders, since $x^2$ and $(k-x)^2$ have the same remainder. $\endgroup$ Jan 30, 2021 at 9:54
  • 1
    $\begingroup$ I think you need to be more specific about what you are asking. For some conditions (eg numbers are squares) the answer is trivial. For cubes it would be a bit more interesting. But without being more specific, there is no hope of a general method. I think Hardy and Wright "Introduction to the theory of numbers" has a good basic account of solving polynomial congruences. $\endgroup$ Jan 30, 2021 at 10:50
  • $\begingroup$ Would you like to engage with the comments, Aditya? $\endgroup$ Jan 31, 2021 at 22:39
  • $\begingroup$ I'm sorry I couldn't reply that time. Ok so Gerry Myerson can you please explain your comment a bit? Why does $x^2$ and $(k-x)^2 $ having the same remainder force some remainders to never occur? $\endgroup$
    – Aditya
    Feb 1, 2021 at 2:25
  • $\begingroup$ Mark Bennet, I was actually thinking about triangular numbers. $\endgroup$
    – Aditya
    Feb 1, 2021 at 2:31

1 Answer 1


Partial progress : Here's the proof that $n$ power numbers for any even $n>1$ (i.e. squares, $4$ th powers etc.) can't achieve all remainders modulo $k$ for $k \gt 2$.

Define sets $A$ and $B$ as $A=\{ km, km+1, \cdots , km+k-1 \} $ $B=\{ 0,1,2 \cdots , k-1 \}$. See that $|A|=|B|$.

Define a map $p : A \mapsto B$ such that $p(a)=r$ where $ a^n \equiv r \pmod k$.

For any $a \in A$, Note that $a^n \equiv (k-a)^n \pmod k$. (Since $n$ is even, it is trivial by binomial theorem)

$\implies p $ is not a one one map and because $|A|=|B|$, $p$ can not be onto.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .