Divisibility property involving binomial coefficients and largest prime power divisor

Question

Let $p$ be a prime, let $x$ be an integer not divisible by $p$, and let $j\geq 1$. Denote, as usual, by $\nu=\nu_p(j+1)$ the largest exponent such that $p^{\nu}$ divides $j+1$.

My question : is it true that $p^{\nu}$ always divides $\binom{x-1}{j}=\frac{(x-1)\ldots(x-j)}{j!}$ ?

My thoughts : I have checked that it holds for $p=2,3,5$ and $x\leq 1000$. It is also easy to check when $j$ is "small" compared to $p$ (for example when $j\lt p$, the numerator is divisible by $p$ but not the denominator, so we are done).

It is natural to use Legendre's formula here : we know that

$$ \nu_p(j!)=\sum_{t=1}^{\infty}\left \lfloor \frac{j}{p^t}\right\rfloor, \nu_p((x-1)\ldots(x-j))=\sum_{t=1}^{\infty} \left\lfloor \frac{x-1}{p^t}\right\rfloor -\left \lfloor \frac{x-(j+1)}{p^t}\right\rfloor $$

So, it would suffice to show the following inequality :

$$ \sum_{t=1}^{\infty}\left \lfloor \frac{x-1}{p^t}\right\rfloor - \left\lfloor \frac{x-(j+1)}{p^t}\right\rfloor - \left\lfloor \frac{j}{p^t}\right\rfloor \geq \nu $$

But then I'm stuck.

Answer 1

The easy proof is that:

$$x\binom{x-1}{j}=(j+1)\binom{x}{j+1}\tag1$$

So $$\nu_p(x)+\nu_p\left(\binom {x-1}j\right)\geq \nu_p(j+1).$$

But $p\not\mid x$ means $\nu_p(x)=0.$

(1) shows more generally that if $d\mid j+1$ and $\gcd(d,x)=1,$ then $d\mid \binom{x-1}{j}.$

---

To extend your approach using Legendre.

If $p\not \mid x$ then show for $t>0:$ $$\left\lfloor \frac{x-1}{p^t}\right\rfloor=\left\lfloor\frac{x}{p^t}\right\rfloor$$

and, for $t\leq\nu,$ $$\left\lfloor\frac{x-(j+1)}{p^t}\right\rfloor =\left\lfloor\frac{x}{p^t}\right\rfloor-\frac{j+1}{p^t}$$

So (*):

$$ \begin{align} \nu_p\left(\binom{x-1}j\right)&\geq \sum_{t=1}^{\nu}\left(\left \lfloor \frac{x-1}{p^t}\right\rfloor - \left\lfloor \frac{x-(j+1)}{p^t}\right\rfloor - \left\lfloor \frac{j}{p^t}\right\rfloor\right)\\ &=\sum_{t=1}^{\nu}\left(\frac{j+1}{p^t}-\left\lfloor\frac{j}{p^t}\right\rfloor\right) \end{align} $$

Finally, for $t\leq \nu,$ $$\left\lfloor\frac{j}{p^t}\right\rfloor =\frac{j+1}{p^t}-1.$$

---

Note: We get in (*) $$\sum_{t=1}^{\infty}\geq \sum_{t=1}^{\nu}$$ because all the terms in the infinite sum are non-negative, using the general inequality:

$$\lfloor \alpha+\beta\rfloor\geq \lfloor \alpha\rfloor +\lfloor\beta\rfloor.$$

Answer 2

Legendre's Formula can be written as $\nu _p(n!)=\frac{n-s_p(n)}{p-1}$, with $s_p(n)$ the sum of digits in base $p$ of $n$. On this view, you can write the inequality that you want as (this using that $\nu _p(j+1)=\nu _p((j+1)!/j!)$):
$$\frac{1+s_p(j)-s_p(j+1)}{p-1}\leq \frac{s_p(j)+s_p(x-1-j)-s_p(x-1)}{p-1},$$ which is equivalent to $$1-s_p(j+1)-s_p(x-(j+1))\leq -s_p(x-1),$$ adding both sides an $x$ and dividing over $p-1,$ using again Legendre's, one ends up on $$\frac{1}{p-1}+\nu _p(((j+1)!(x-1-j)!))\leq \frac{1}{p-1}+\nu _p((x-1)!)=\frac{1}{p-1}+\nu _p(x!),$$ which is true because $\binom{x}{j+1}$ is an integer.