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.

Let n be a positive integer. Show that in any set of n consecutive integers there is exactly one divisible by n.

Here is the solution:

Let $a,~a+1,...,a+n-1$ be the integers in the sequence. The integers $(a+i)\mod n$, $i=0,1,2,...,n-1$, are distinct, because $0 < (a+j) - (a+k) < n$ whenever $0 \le k < j \le n -1$. Because there are n possible values for $(a+i)\mod n$ and there are n different integers in the set, each of these values is taken exactly once. It follow that there is exactly one integer in the sequence that is divisible by n.

Few things I don't quite understand:

Why is the sequence of integers $a,~a+1,...,a+n-1$, instead of being $a,~a+1,...,a+n$?

How does $0 < (a+j) - (a+k) < n$ make the values calculated from the modulus distinct? Also, what is the motivation for $0 < (a+j) - (a+k) < n$? Why are we allowed to use this fact?

share|improve this question
    
The reason being that it ends at $a+n-1$ is that if it ended at $a+n$, it would be a set of $n+1$ consecutive integers and conceivably, there could be two integers divisible by $n$ in the set. This would happen if $a$ is divisible by $n$. –  Cameron Williams Apr 23 '13 at 19:01
    
If you want you could use: $a+1, a+2, \ldots, a+n$. –  genepeer Apr 23 '13 at 19:08
add comment

1 Answer 1

up vote 1 down vote accepted

There are $n$ integers. $a = a+0$, so if you had $\{ a, a+1, \ldots, a+n\}$, then you have a "$+0$", "$+1$", and so on up to "$+n$" -- the $a+0$ term counts, so you would have $n+1$ terms.

If $0 \le k < j < n-1$, then $j > k$, and $(a+j)-(a+k) = a+j-a-k = a-a+j-k = j-k > 0$. But since $j-k < j$, and $j \le n-1$, then $j-k < n$.

So the moduli must be distinct simply by definition of how modular arithmetic works. You can't have something divisible by $n$ more frequently than once every $n$ terms!

share|improve this answer
    
So there difference being less than n--that is, $j - k < n$--proves that when taking the modulus the result is distinct? I'm sorry, I don't quite see it. –  Mack Apr 23 '13 at 20:05
1  
Assume that $(a+j) \bmod n$ and $(a+k)\bmod n$ are both some integer $N$. Then, $a+j = c_1n + N$ and $a+k = c_2n+N$ by the division algorithm. Then, $a+j-(a+k) = c_1n+N - (c_2n +N)$, implying that $j-k = (c_1-c_2)n$, so $j-k$ is divisible by $n$. But $0<j-k<n$, so this conclusion must be false. –  Arkamis Apr 23 '13 at 21:12
add comment

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.