# How to prove that a particular form of numbers achieve all remainders modulo $n$?

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

• 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. Jan 30, 2021 at 9:54
• 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. Jan 30, 2021 at 10:50
• Would you like to engage with the comments, Aditya? Jan 31, 2021 at 22:39
• 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? Feb 1, 2021 at 2:25
• Mark Bennet, I was actually thinking about triangular numbers. Feb 1, 2021 at 2:31

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.