# Thread: Divisibility

1. ## Divisibility

Was going through the divisibility chapter and stumbled across this excercise that kinda stumped me.

Let $a$ be and integer. prove that $3 \mid a(a + 1)(a + 2)$. (Hint: Consider three cases.)

Now I see the answer as being evident. 3 divides or is a multiple of 1 of 3 consecutive numbers. $a(a + 1)(a + 2)$ lists 3 consecutive number so 3 is definitely going to divide their product. I'm just lost on how exactly to write the proof ... I hate divisibility chapter. The entire section is riddled with things we take for granted but have a hard time proving Thanks for any help guys!

(Small note: This section is prior to congruence or modulo so I'd like to avoid using those to prove it.)

2. Consider the integer a. There are three possibilities.

Case 1: There is an integer k such that a=3k
Case 2: There is an integer k such that a=3k+1
Case 3: There is an integer k such that a=3k+2

In case 1, a is divisible by 3.
In case 2, a+2=(3k+1)+2=3k+3=3(k+1) so that a+2 is divisible by 3
In case 3, a+1= (3k+2)+1=3k+3=3(k+1) so that a+1 is divisible by 3

Notice that all I am using in this argument is the definition of divisibility by 3. If you understand he definition, then the argument is straightforward and almost obvious.

3. Dr. Steve has given you a rigorous proof, but I think it would also be acceptable to simply say that, of any three consecutive integers, one must be a multiple of three.

4. I suppose one could also use the Pigeonhole Principle to do something like this in general.

Let $a,a+1,a+2,\ldots,a+(n-1)$ be any $n$ consecutive integers. We wish to show that at least one of them (well, really, exactly one of them) is divisible by $n$.

Suppose that none of them were. Now, we know that, by the division algorithm, when you divide an integer by $n$, the remainder must be smaller than $n$; that is, the remainder upon division by $n$ is in the set $\{0,1,2,\ldots,n-1\}$.

Since we are assuming that none of the integers $a,a+1,a+2,\ldots,a+(n-1)$ are divisible by $n$, we know that none of the remainders upon division by $n$ is $0$. So our possible remainders are $1,2,\ldots,n-1$; there are $n-1$ possible remainders. But there are $n$ numbers in our list; since there are more numbers than remainders, the Pigeonhole Principle says that at least two (different) numbers in our list have the SAME remainder upon division by $n$.

Let these two numbers be $a+i$ and $a+j$, where we assume $0\leq i. Suppose their remainder upon division by $n$ is $r$, and using the division algorithm, write $a+i=nq_1+r,a+j=nq_2+r$, for some integers $q_1,q_2$. Then

$j-i=(a+j)-(a+i)=(nq_2+r)-(nq_1+r)=nq_2-nq_1=n(q_2-q_1)$.

Condense the equality to only the first and last terms:

$j-i=n(q_2-q_1)$.

This says $n|(j-i)$. But the inequality $0\leq i implies $0. So $j-i$ is a positive integer which is both less than $n$ AND divisible by $n$. This is clearly impossible.

Hence, the conclusion we must draw is that our assumption that none of $a,a+1,a+2,\ldots,a+(n-1)$ are divisible by $n$ is faulty; hence at least one of them (in fact, EXACTLY one, which can be shown using the same subtraction trick) is divisible by $n$.

----------

Obviously this is over-elaborate, but I really put in every detail for sake of a thorough explanation of a method of doing this question that doesn't involve consideration of multiple cases. Even if you don't answer the question this way, I hope this was enlightening or useful to you in some way.