3
$\begingroup$

Problem. Prove that the product of $n$ consecutive integers is divisible by $n$

Proof.

To prove this, it is enough to show that amongst any $n$ consecutive integers, we can always find one that is divisible(or a multiple) of $n$.

Let $A = \{a_0, a_1 a_2, \dots, a_n\}$ be the set containing such consecutive integers. Let us see how we form such a sequence, we pick an arbitrary nonnegative integer, say $a_0$, then add 1 to obtain the second term which is $a_2 = a_0 + 1$. The third term is of course $a_3 = a_0 + 2$, continuing this way, the nth term is thus $a_n = a_0 + (n - 1)$.

Notice that if $n$ is a multiple of $a_0$ then there is nothing to prove, if Otherwise holds, then we can always divide each $a_i$'s in $A$ by $n$ the residue classes modulo n is either increasing or decreasing, depending on the choice of $a_0$

Since each $a_i$'s are distinct, then it follows that their residue classes modulo n are distinct.
Upon dividing each term by n and computing their residue classes, we obtain

$$(a_0, a_1, a_2, . . . a_n) \equiv (1, 2, 3, \dots, (n - 1)) \pmod n.$$

Since they are $n$ terms and $(n -1)$ remainders, by the Pigeon hole principle, there must be two terms, say $a_l$ and $a_k$, in the set $A$ such that $a_l = ps + r$ and $a_k = tu + r$ But this contradicts our initial assumption that no two terms in A are congruent to the same residue classes modulo n. Hence it follows that our residue classes is not complete (hence 0 is missing) and hence $\exists a_v \in A$ such that $a_v \equiv 0 \pmod n$.

Q.E.D

Is there any error(s) in this proof? Can it be modified and made shorter? Was there any fallacy in it?

$\endgroup$
  • $\begingroup$ Is the first term $a_0$ or $a_1$? Becuase if the first term is $a_0$ the last term is $a_{n - 1}$ and the second term is $a_1$. $\endgroup$ – Trevor Gunn Dec 25 '17 at 21:03
  • $\begingroup$ First term is $a_1$ @Trevor $\endgroup$ – Icosahedron Dec 25 '17 at 21:14
2
$\begingroup$

In this line:

$$(a_0, a_1, a_2, . . . a_n) \equiv (1, 2, 3, \dots, (n - 1)) \pmod n$$

either are assuming that $a_0 \equiv 1 \pmod n$ or you are refering to the set of remainders instead of the ordered list of remainders.

You have the right ideas but you are trying to hard to include the pigeonhole principle in your proof and as a result, your proof is longer than it needs to be. For one thing: this statement

Since each $a_i$'s are distinct, then it follows that their residue classes modulo $n$ are distinct.

is not sufficiently justified. For instance $2,4,6$ are all distinct but have the same residue class mod $2$.

The pigeonhole principle works by contradiction in this case and adds extra "fluff" to the proof that doesn't need to be there. In the end the conclusion is that $a_l \equiv a_k \pmod n$ with $l \ne k$. In this case you still need to manipulate the terms to get the right value of $a_i$ so that $a_i \equiv 0 \pmod n$. Alternatively, you can prove that the remainders are all distinct in which case you should skip the application of the pigeonhole principle and use the result that if you have a surjective map (taking remainders) from a set with $n$ elements to a set of $n$ elements, the map has to be injective as well.

Instead, keep to what you know and try to prove it mathematically. You know that the remainders go up by 1 until you get to $n$ and then the start over at $0$. You know that every possible remainder should appear exactly once.

Here's what your proof should say:

Let $a_0,\dots,a_{n-1}$ be a sequence of $n$ consecutive integers. If $a_0 \equiv 0 \pmod n$ we are done. So suppose $a_0 \equiv r \pmod n$ with $0 < r < n$. Then $a_1 \equiv r + 1 \pmod n$ and $a_2 \equiv r + 2 \pmod n$ and so on, until we have $$ a_{n - r} \equiv r + (n - r) \equiv 0 \pmod n $$ and since $0 < r < n$, we have $0 < n - r < n$ so that $a_{n - r}$ is in our list.

Notice that we are not trying to use the pigeonhole principle, instead we are keeping to the idea that the remainder goes up by one each time. It is important that we separate out $a_0 \equiv 0 \pmod n$ because then $n - r = n$ (since $r = 0$) and $a_n$ is not in the list. Starting the numbering from $a_0$ is helpful because we don't have to add or subtract $1$ like we would have to do if we started from $a_1$.

$\endgroup$
1
$\begingroup$

You are considering $n+1$ integers, if you start the indexing from $0$, but it is possibly a repeated typo, since you mention “the second term which is $a_2=a_0+1$”.

Distinct numbers may have the same remainder modulo $n$, so the pigeonhole principle cannot be applied directly. It is actually true that $n$ consecutive integers have distinct remainders, but this is exactly what you need to prove.


The proof is much simpler. Let $a,a+1,\dots,a+(n-1)$ be a sequence of $n$ consecutive integers. If $n\mid a$, we are done. If $a\equiv r\pmod{n}$, with $0<r<n$, then $$ a+(n-r)\equiv r+(n-r)\equiv n\equiv 0\pmod{n} $$ and, by assumption, $0<n-r<n$, so $a+(n-r)$ belongs to the sequence.

$\endgroup$

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.