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?

  • 2
    $\begingroup$ The terms need not form a complete residue system modulo $n$. They do if $b$ and $n$ are relatively prime. $\endgroup$ – André Nicolas Jul 15 '16 at 2:25
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Jul 15 '16 at 2:43
  • $\begingroup$ 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. $\endgroup$ – 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.

  • $\begingroup$ How does it follow that $v_p(a+jb) = v_p(a) = k$? $\endgroup$ – Puzzled417 Jul 15 '16 at 4:07
  • $\begingroup$ What is $\gcd\left(\frac{a+jb}{p^k},p\right)$? $\endgroup$ – Batominovski Jul 15 '16 at 4:08
  • $\begingroup$ 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? $\endgroup$ – Puzzled417 Jul 15 '16 at 4:25
  • $\begingroup$ 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$? $\endgroup$ – Batominovski Jul 15 '16 at 4:31
  • $\begingroup$ You may switch it to $p = 5, a = 625,$ and $b= 125$. Then we have $5^3(j+5)$. $\endgroup$ – Puzzled417 Jul 15 '16 at 4:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.