Exist Term in Arithmetic Sequence Divisible by Number

From ProofWiki
Jump to navigation Jump to search



Theorem

Let $\sequence {a_k}$ be an $n$-term arithmetic sequence in $\Z$ defined by:

$a_k = a_0 + k d$ for $k = 0, 1, 2, \dots, n - 1$

Let $b$ be a (strictly) positive integer such that $b$ and $d$ are coprime and $b \le n$.

Then there exists a term in $\sequence {a_k}$ that is divisible by $b$.


Proof

We claim that at least one of the first $b$ terms:

$a_0, a_0 + d, a_0 + 2 d, \dots, a_0 + \paren {b - 1} d$

is divisible by $b$.

Consider the remainders of each term after division by $b$.

They can takes on values of $0 \le r < b$.

If one of them gives $r = 0$ then we are done.


Aiming for a contradiction, suppose not.

Since there are $b$ terms but only $b - 1$ possible remainders, by Pigeonhole Principle at least two terms must share a remainder.

That is:

$a_0 + i d \equiv a_0 + j d \pmod b$

for some $i, j$ where and $0 \le i < j \le b - 1$.

But then:

$\paren {j - i} d \equiv 0 \pmod b$

so $b \divides \paren {j - i} d$.

Since $b \perp d$, by Euclid's Lemma we have $b \divides \paren {j - i}$.

Since $0 < j - i < b$ we must have $b \nmid \paren {j - i}$ by Absolute Value of Integer is not less than Divisors.

This is a contradiction.

Therefore there is at least one term that is divisible by $b$.

$\blacksquare$