A complete residue system from an arithmetic progression

Solution 1:

There is a simple, well-known theorem about that:

If $a$, $b$ and $m$ are integers, $m\ge 2$ and $\gcd(b,m)=1$ then the set $\{a,a+b,a+2b,\ldots,a+(m-1)b\}$ is a complete residue system.

This implies, for example, that the set contains exactly one multiple of $m$.

Solution 2:

Take $a\in\mathbb{N}$ and suppose that $a\equiv 1\pmod 3$. Then \begin{align*} a&\equiv 1\pmod 3\\ a+10\equiv 11&\equiv 2\pmod 3\\ a+20\equiv 21&\equiv 0\pmod 3 \end{align*}

If we instead have $b\in\mathbb{N}$ such that $b\equiv 2\pmod 3$, then adding $10$ to $b$ is sufficient. The case in which we have $\equiv 0\pmod 3$ is obviously trivial.

Solution 3:

If $\,b\,$ is coprime to $\,m\,$ then $\,a+ib,\, i = 1,\ldots,m\,$ is a complete residue system mod $\,m\,$ since

$$\ a+ib \equiv a+j b \iff (i\!-\!j)b\equiv 0\overset{(b,m)=1}\iff i\!-\!j\equiv 0\iff i = j\,\ {\rm by}\,\ 1\le i,j\le m$$

Hence, being complete, it contains an element $\equiv 0,\,$ i.e. a multiple of $\,m.$

Remark $\ $ When $\,b = 1\,$ we obtain the well-known special case that any sequence of $\,m\,$ consecutive integers contains a multiple of $\,m.$

Solution 4:

If $d$ is relatively prime to $b$, then $a + d j$ is divisible by $b$ if and only if $j \equiv -a d^{-1} \mod b$. Thus exactly one of any $b$ consecutive terms of the arithmetic sequence $a, a+d, a+2d, \ldots$ is divisible by $b$.

Solution 5:

In general let $d$ be the common difference of an arithmetic sequence, where $3\nmid d$, and let $a$, $a+d$, and $a+2d$ be three consecutive terms in that sequence. Now WLOG if we assume $3\nmid a$ then we can write $a$ and $d$ as: $$a=3k+1\quad\text{ or }\quad a'=3k+2\quad\text{ and }\quad d=3j+1\quad\text{ or }\quad d'=3j+2$$ for some $j$, $k\in\mathbb{Z}$, where primes have been added to distinguish the two possibilities for $a$ and $d$. Now look at the four possibilities we have for $a+d$, and $a+2d$: $$a+d=3(k+j)+2,\quad \quad a+2d=3(k+2j)+3\qquad (A)$$ $$a+d'=3(k+j)+3,\quad \quad a+2d'=3(k+2j)+5\qquad (B)$$

$$a'+d=3(k+j)+3,\quad \quad a'+2d=3(k+2j)+5\qquad (C)$$ $$a'+d'=3(k+j)+4,\quad \quad a'+2d'=3(k+2j)+6\qquad (D)$$

As can be seen, since we assumed $3\nmid a$, only one member of the three consecutive terms is divisible by $3$ on listing all possible combinations (A), (B), (C), and (D). It would make no difference if we assumed $3\nmid a+d$ or $3\nmid a+2d$ as our starting point as the problem is cyclic modulo $3$. By this look at the congruences of $a$, $a+d$, $a+2d\pmod{3}$ for each of (A), (B), (C), and (D) and you see we get the full set of residue classes $[0]$, $[1]$, $[2]$ modulo $3$ in some order, which is the reason we get one and only one number divisible by $3$.

Further for some $m$ for which $\gcd(m,d)=1$ look at $m$ consecutive terms of an arithmetic sequence module $m$: $$a,\ a+d,\ a+2d,\dotsc,\ a+(m-1)d\pmod{m}\qquad (E)$$ then $a+kd\equiv a+jd\pmod{m}$ iff $(k-j)d\equiv 0\pmod{m}$ for $0\le k,j\le m-1$, which since $[0]$, $[1]$, $[2],\dotsc,\ [m-1]$ form a complete residue system modulo $m$ we must have $[k]=[j]$ modulo $m$, and so in fact $k=j$ with respect to our $m$ consecutive terms with any distinct pair of terms incongruent modulo $m$, and only one unique number in the set being divisible by $m$. To see this imagine (E) rewritten with respect to residue classes modulo $m$ reordered so: $$a+[0],\ a+[1],\ a+[2],\dotsc,\ a+[m-1]\pmod{m}\qquad (E')$$ If $m\mid a$ then $m\equiv a+[0]\pmod{m}$, and we also see $m$ cannot divide any other number in the set; if $m\nmid a$ then we can write $a=mj+k$ where $j$, $k\in\mathbb{Z}$, and $\gcd(k,m)=1$, which is in the class $[mj+k]=[k]=[k']$ modulo $m$, and $[k']+[k'']=[0]$ modulo $m$, $0<k',k''\le m-1$, where $[k']$ and $[k'']$ are additive inverses in the complete residue system (note that $[0]$ is self inverse wrt addition).