# Prove that $\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$ is an integer

Let $a$ and $b$ be integers and $n$ a positive integer. Prove that $$\dfrac{b^{n-1}a(a+b)(a+2b)\cdots(a+(n-1)b)}{n!}$$ is an integer.

Define $v_p(x)$ such that if $v_p(x) = n$, then $p^n \mid x$ but $p^{n+1} \nmid x$. Then we need to show that $v_p(b^{n-1})+v_p(a)+v_p(a+b)+\cdots+v_p(a+(n-1)b)\geq v_p(n!)$ for all primes $p$. How should we do that?

• The terms need not form a complete residue system modulo $n$. They do if $b$ and $n$ are relatively prime. – André Nicolas Jul 15 '16 at 2:25
• The problem is general enough! I have no immediate plan of attack. There are many proofs of the special case $b=1$. Possibly one of them can be adapted. – André Nicolas Jul 15 '16 at 2:43
• One approach is to show that if $p$ is a prime that does not divide $b$, then the terms $a, \dots, a+(n-1)p$ have "enough" $p$'s. For the other primes, the $b^{n-1}$ should be enough to push us over. – André Nicolas Jul 15 '16 at 3:39

Fix a prime natural number $p$. For an integer $m$ and a nonnegative integer $r$, let $p^r\parallel m$ denote the condition that $p^r\mid m$ but $p^{r+1}\nmid m$. We shall ignore the trivial cases (namely, $n=1$, $a=0$, and $b=0$). Suppose that $p^k\parallel a$ and $p^l\parallel b$ for some integers $k,l\geq 0$.

First, we assume that $k < l$ (whence $l\geq 1$). It follows immediately that $v_p(a+jb)=v_p(a)=k$ for all $j=0,1,2,\ldots,n-1$. Thus, $$v_p\left(b^{n-1}\,\prod_{j=0}^{n-1}\,(a+jb)\right)=v_p\left(b^{n-1}\right)+\sum_{j=0}^{n-1}\,v_p(a+jb)=(n-1)l+nk\,.$$ Note that $$v_p(n!)=\sum_{j=1}^\infty\,\left\lfloor\frac{n}{p^j}\right\rfloor<\sum_{j=1}^\infty\,\frac{n}{p^j}\leq \sum_{j=1}^\infty\,\frac{n}{2^j}=n\,.$$ Consequently, $\displaystyle v_p(n!)\leq n-1\leq (n-1)l\leq (n-1)l+nk=v_p\left(b^{n-1}\,\prod_{j=0}^{n-1}\,(a+jb)\right)$.

Now, suppose that $k \geq l$. Then, it is evident that, for every $s=1,2,\ldots$, the congruence $$a+jb\equiv 0\,\pmod{p^{l+s}}$$ has at least $\left\lfloor\dfrac{n}{p^s}\right\rfloor$ solutions $j\in\{0,1,2,\ldots,n-1\}$. That is, $$\sum_{j=0}^{n-1}\,v_p(a+jb)\geq nl+\sum_{s=1}^{\infty}\,\left\lfloor\frac{n}{p^s}\right\rfloor=nl+v_p(n!)\geq v_p(n!)\,.$$ Ergo, we again obtain $\displaystyle v_p(n!)\leq v_p\left(b^{n-1}\,\prod_{j=0}^{n-1}\,(a+jb)\right)$.

That is, in all cases, $\displaystyle v_p(n!)\leq v_p\left(b^{n-1}\,\prod_{j=0}^{n-1}\,(a+jb)\right)$. Because $p$ is arbitrary, we conclude that $n!$ divides $\displaystyle b^{n-1}\,\prod_{j=0}^{n-1}\,(a+jb)$. I believe that there should be a combinatorial proof of this statement, and hope to see it.

• How does it follow that $v_p(a+jb) = v_p(a) = k$? – Puzzled417 Jul 15 '16 at 4:07
• What is $\gcd\left(\frac{a+jb}{p^k},p\right)$? – Batominovski Jul 15 '16 at 4:08
• About the congruence you said having that many solutions, what if we had like $125+j \cdot 625 = 5^3(1+5j)$. Where are the solutions for $j$ here? – Puzzled417 Jul 15 '16 at 4:25
• I'm assuming you are taking $p=5$, $a=125$, and $b=625$. What are $k$ and $l$ in this case? Do they satisfy $k\geq l$? – Batominovski Jul 15 '16 at 4:31
• You may switch it to $p = 5, a = 625,$ and $b= 125$. Then we have $5^3(j+5)$. – Puzzled417 Jul 15 '16 at 4:35