Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
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. –  Harald Hanche-Olsen Jul 8 at 9:21
1  
I'm a bit confused about the connection between this question and its elder brother. –  Jyrki Lahtonen Jul 8 at 9:54
    
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. –  drhab Jul 8 at 9:56
    
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. –  Swapnil Tripathi Jul 8 at 10:09

6 Answers 6

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

share|improve this answer
1  
+1 Here $n=8q$ as special case. Goed gedaan 'user'. –  drhab Jul 8 at 9:59
2  
ooo, I like the induction here. –  Cruncher Jul 8 at 14:37

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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