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 $x$ is positive integer, prove that for all integers $a$, $(a+1)(a+2)\cdots(a+x)$ is congruent to $0\!\!\!\mod x$.

Any hints? What are the useful concepts that may help me solve this problem?

share|improve this question
    
hint: you multiply $x$ consecutive integers so that one... –  Raymond Manzoni Sep 1 '12 at 18:35
    
There are no "concepts", just original thought. Try to prove that one of the brackets is divisible by $x$ by considering what $a$ is mod $x$. –  fretty Sep 1 '12 at 18:37
    
Hint: can you think of any reason why $x$ must divide one of the numbers $a,\ldots,a+x$? –  shoda Sep 1 '12 at 18:39
    
So I can use factorial notation? –  primemiss Sep 1 '12 at 18:43
    
so that one of them must be a multiple of $x$ (every $x$-th integer is a multiple of $x$). –  Raymond Manzoni Sep 1 '12 at 18:55
show 1 more comment

4 Answers

Note that there is some $k$ such that $0\leq k< x$ and $a\equiv k\mod x$. Then $$a+(x-k)\equiv k+x-k\equiv x\equiv 0\mod x$$ and what do you get when you multiply this by other stuff?

share|improve this answer
add comment

One of the numbers $a+1, a+2,\ldots, a+x$ is congruent to $0$ mod $x$. Multiplying by $0$ yields $0$.

share|improve this answer
    
How to prove that one of the factors is congruent to 0 mod x? –  primemiss Sep 1 '12 at 19:28
1  
In any set of seven consecutive days, one will be a Tuesday. The reason is the same as that. If you have seven consecutive days, you get one of each day of the week, and if you have $x$ consecutive integers, then you've got one in every congruence class mod $x$. For example, consider $60,61,62,63,64,65,66$. Seven consecutive integers. They are congruent mod $7$ to $4,5,6,0,1,2,3$, respectively. –  Michael Hardy Sep 1 '12 at 22:02
    
@primemiss: By the definition of the equivalency relation, there exists a $p$ and a $q$ with $0 \leq q < x$ such that $a = px + q$. That means that $a + (x - q) = (p + 1)x \equiv 0 \mod x$ with $0 < x - q \leq x$. –  Niklas B. Sep 1 '12 at 23:06
add comment

Hint $\ $ Any sequence of $\,n\,$ consecutive naturals has an element divisible by $\,n\,$. This has a simple proof by induction: shifting such a sequence by one does not change its set of remainders mod $\,n,\,$ since it effectively replaces the old least element $\:\color{#C00}a\:$ by the new greatest element $\:\color{#C00}{a+n}$

$$\begin{array}{}& \color{#C00}a, &\!\!\!\! a+1, &\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1 & \\ \to & &\!\!\!\! a+1,&\!\!\!\! a+2, &\!\!\!\! \cdots, &\!\!\!\! a+n-1, &\!\!\!\! \color{#C00}{a+n} \end{array}\qquad$$

Since $\: \color{#C00}{a\,\equiv\, a\!+\!n}\pmod n,\:$ the shift does not change the remainders in the sequence. Thus the remainders are the same as the base case $\ 0,1,2,\ldots,n-1\ =\: $ all $ $ possible remainders mod $\,n.\,$ Therefore the sequence has an element with remainder $\,0,\,$ i.e. an element divisible by $\,n.$

share|improve this answer
    
Note: Reversely, shifting by $-1$ proves it for sequences starting with negative integers. –  Bill Dubuque Sep 1 '12 at 21:26
add comment

This has been already nicely answered, but here is another way to state an approach.

You will also be able to notice that you do not need the last term $(a + x)$ to have the relation you want.

What you hope to find is one of the factors divisible by $x$. How do do know you can find one?

Any of the factors (mod $x$) will be the equivalent of the remainder of $a$ when divided by $x$ plus the remainder of the added term when divided by $x$.

The remainder of $a$, call it r, will be $1\leq r< x$. And each of the added terms (other than $x$) will be equal to itself, that is one of the numbers $1$ thru $x - 1$.

So one of these sums (factors) will definitely exactly equal $x$.

share|improve this answer
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.