# Proving Congruence Modulo

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?

-
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

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?

-

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

-
How to prove that one of the factors is congruent to 0 mod x? –  primemiss Sep 1 '12 at 19:28
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

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

-
Note: Reversely, shifting by $-1$ proves it for sequences starting with negative integers. –  Bill Dubuque Sep 1 '12 at 21:26

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

-