1
$\begingroup$

If $8q,8q+1,8q+2$ are consecutive positive integers, then prove that at least one among them is a multiple of $3$.

One proof is that by expressing $8q=3m+r$. Is there any other way of doing it without taking $8q=3m+r$?

$\endgroup$
  • 1
    $\begingroup$ Taken modulo 3, the three numbers will be 0, 1, 2 (or some cyclic permutation of the three). So their product is 0 mod 3. However, this is just dressing up your suggested argument in more fancy clothing, so it does not qualify. $\endgroup$ – Harald Hanche-Olsen Jul 8 '14 at 9:21
  • 2
    $\begingroup$ I'm a bit confused about the connection between this question and its elder brother. $\endgroup$ – Jyrki Lahtonen Jul 8 '14 at 9:54
  • $\begingroup$ To make things a bit easyer (and more structural): ask how to prove that one of $n,n+1,n+2$ is a multiple of $3$ when $n$ is an integer. Here $n=8q$ where $q$ is a positive integer is a special case of that. $\endgroup$ – drhab Jul 8 '14 at 9:56
  • $\begingroup$ Consider $n,n+1,n+2$. Reduce the three numbers modulo $3$. Note that no two of the above $3$ consecutive numbers are congruent modulo $3$. (If $n+i$ and $n+j$ where $i,j=0,1,2$, $i\neq j$ are congruent, then it would imply $3|i-j$, a contradiction as $0<i-j<3$). So, by property of $Complete$ $Residue$ $Set$, $n,n+1,n+2$ is congruent to $0,1,2$ modulo 3 in some order. Hence the claim. $\endgroup$ – Swapnil Tripathi Jul 8 '14 at 10:09
15
$\begingroup$
  • One of the numbers in $(1;2;3)$ is divisible by $3$.

  • Suppose one of the numbers in $(n;n+1;n+2)$ is divisible by $3$.

  • Now consider $(n+1;n+2;n+3$).

    • If $n$ was divisible by $3$, then so is $n+3$. So that is OK.
    • If either of $n+1$ or $n+2$ was divisible by $3$, then they still are now. So in that case we're also good.
  • Again by using induction and with a similar argument, you prove that this statement also holds for all non-positive integers.

By induction, the statement is now proven, for all triples of consecutive integers. Thus in particular for $(8q;8q+1;8q+2)$.


The same arguments can be used to prove that out of any $N$ consecutive integers, one is a multiple of $N$.

$\endgroup$
3
$\begingroup$

I have seen many answers to related questions that in the context of this question, would be along the lines of "consider all possible values of $q$ modulo $3$". Here is a different approach.

If we multiply everything together modulo $3$, we get:

$$8q(8q + 1)(8q + 2) \equiv 2q^3 + q\pmod 3$$

By Fermat's Little Theorem,

$$2q^3 + q \equiv 2q + q \equiv 0\pmod 3$$

This implies that $3$ divides $(8q)(8q +1)(8q+2)$.

Since $3$ is a prime and it divides $(8q)(8q +1)(8q+2)$, then by Euclid's Lemma, it divides at least one of $8q$ and $(8q +1)(8q+2)$.

If it divides $8q$, then we are done. If not, it must divide $(8q+1)(8q+2)$. Again, using Euclid's lemma, it must divide at least one of $(8q+1)$ and $(8q +2)$.

It follows that at least one of the three must be divisible be $3$.

$\endgroup$
  • $\begingroup$ I like this one ! $\endgroup$ – mick Jan 7 '17 at 20:52
3
$\begingroup$

Hint $ $ A triple of consecutive integers contains a multiple of $\,3\,$ iff its left/right-shifted triple does:

$$\begin{array}{}& \color{#C00}a, &\!\!\!\! a+1, &\!\!\!\! a+2 & \\ \leftrightarrow & &\!\!\!\! a+1,&\!\!\!\! a+2, &\!\!\!\! \color{#C00}{a+3} \end{array}\qquad$$

because $\,3\mid\color{#c00} a\iff 3\mid \color{#c00}{a+3}.\ $ So, by repeatedly left/right-shifting, we deduce that it is true for any given triple iff it is true for the "base" triple $\,1,2,3\,$ (which, indeed, contains a multiple of $\,3).$

Remark $\ $ You may find it instructive to present this as a rigorous proof by induction, and ponder the relationship with the Division with Remainder Algorithm. The same idea extends to yield a proof that any sequence of $\,n\,$ consecutive integers contains a multiple of $\,n.$

$\endgroup$
2
$\begingroup$

You can work mod 3: then (working in $\mathbb{Z}/3\mathbb{Z}$ and skipping the bar notation) $8q(8q+1)(8q+2)=2q(2q+1)(2q-1)=q-q^3$. And the polynomial $X^3-X$ over $\mathbb{Z}/3\mathbb{Z}$ has each element of $\mathbb{Z}/3\mathbb{Z}$ as a root.

$\endgroup$
2
$\begingroup$

Write a proof by induction. It is ok for $k=0$.

now, if either $8k, 8k+1, 8k+2$ is a multiple of 3, then

$$\begin{align} 8(k+1) &= (8k+2)+3\times 2\\ 8(k+1)+1 &= 8k+3\times 3\\ 8(k+1)+2 &= (8k+1)+3\times 3 \end{align} $$and one of them is a multiple of 3.

$\endgroup$
2
$\begingroup$

Yet another way is to observe that $$ 8q(8q+1)(8q+2)=6\binom{8q+2}3. $$ Then use the fact that the binomial coefficients are integers.

But it is IMHO questionable whether proving that binomial coefficients are integers is any easier than the ways suggested by others.

$\endgroup$
  • $\begingroup$ The trick is to use pascal's triangle INSTEAD of writing the binomial coëfficiënt as a fraction of factorials. Although one also needs to show that the product is that particular binomial coëfficiënt. $\endgroup$ – mick Jan 7 '17 at 20:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.