Let $(a\_0,a\_1,\dotsc)$ be an infinite sequence of natural numbers containing all the natural numbers. Assume that $a\_x\equiv a\_y\pmod{m}$ if and only if $x\equiv y\pmod{m}$, for all $x,y\in\mathbb{N}$ and $m\in\mathbb{N}\_{\geq 1}$. Prove that $a\_n=n$ for all $n\in\mathbb{N}$.


I have tried to prove using induction, but I cannot seem to be able to proove the base case $a\_0=0$.



Let $(a_0,a_1,\dotsc)$ be an infinite sequence of natural numbers such that $a_x\equiv a_y\pmod{m}$ iff $x\equiv y\pmod{m}$. Prove that $a_n=n$
If $a\_x=a\_y$, then $a\_x\equiv a\_y\pmod{m}$ for all positive integers $m$, hence $x\equiv y\pmod{m}$ for all positive integers, so that $x=y$. Therefore $n\mapsto a\_n$ is a permutation of the natural numbers. Now the positive integer $m:=|a\_{n+1}-a\_n|$ satisfies $a\_{n+1}\equiv a\_n\pmod{m}$, whence $n+1\equiv n\pmod{m}$, and therefore $m=1$. This means that $a\_{n+1}$ equals $a\_n-1$ or $a\_n+1$. However, $a\_{n+1}=a\_n-1$ would force $a\_{n+2}=a\_n-2$, $a\_{n+3}=a\_n-3$, etc., which is a contradiction after $a\_n$ steps. Hence $a\_{n+1}=a\_n+1$ for all $n\in\mathbb{N}$, and from here it is clear that $a\_n=n$ for all $n\in\mathbb{N}$.


