# A statement about divisibility of relatively prime integers

I'm solving a problem, and the solution makes the following statement: "The common difference of the arithmetic sequence 106, 116, 126, ..., 996 is relatively prime to 3. Therefore, given any three consecutive terms, exactly one of them is divisible by 3." Why is this statement true? Where does it come from? Is it generalizable to other numbers?

• And here I thought it was something about "relatively prime statements" – Yuriy S Jul 21 '16 at 21:56

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

• Also, most of the other answers hint at a proof of that theorem. – Jeppe Stig Nielsen Jul 22 '16 at 8:04

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.

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

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

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