9
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ The terms need not form a complete residue system modulo $n$. They do if $b$ and $n$ are relatively prime. $\endgroup$ Jul 15, 2016 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$ Jul 15, 2016 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$ Jul 15, 2016 at 3:39

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ How does it follow that $v_p(a+jb) = v_p(a) = k$? $\endgroup$
    – Puzzled417
    Jul 15, 2016 at 4:07
  • $\begingroup$ What is $\gcd\left(\frac{a+jb}{p^k},p\right)$? $\endgroup$ Jul 15, 2016 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, 2016 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$ Jul 15, 2016 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, 2016 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.