3
$\begingroup$

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?

  • 0
    Well, you get (at nearly but not quite the same price) that your products are all congruent to zero modulo $x!$, so you might as well prove that!2012-09-01

4 Answers 4

5

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?

3

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

  • 0
    @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.2012-09-01
2

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

  • 0
    Note: Reversely, shifting by $-1$ proves it for sequences starting with negative integers.2012-09-01
1

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