# Monthly Archives: May 2015

## Prime power dividing product of consecutive integers

The following proposition (not as a proposition but merely as a one-line fact) was stated in a paper that I have been studying as ‘easily seen’ to hold, while I, unfortunately, could not see it so easily! Nonetheless, I think it is a nice result.

For $a$ a positive integer, we use the usual notation $v_p(a)$ to denote the largest integer $k$ such that $p^k\mid a$ and $p^{k+1}\nmid a$. (Apparently, this is called the $p$-adic order, I still haven’t figured out why.) Further, we write $p^k\parallel a$ if $v_p(a)=k$.

Proposition. Let $p$ be a prime number and $n,k$ positive integers. Let $n+a$ be an integer with $n\le n+a\le n+k$ that is maximally divisible by $p$, i.e., with $v_{p}(n+a)=\max\{v_{p}(n+j):0\le j\le k\}$. Then, if

$\displaystyle p^h\parallel\frac{n(n+1)\cdots (n+k)}{n+a}$,

then $p^h\mid k!$.

We will use the following lemma which is easy to prove.

Lemma. For all real numbers $\alpha,\beta$,

$\displaystyle \lfloor\alpha+\beta\rfloor=\begin{cases}\lfloor\alpha\rfloor+\lfloor\beta\rfloor+1,&\{\alpha\}+\{\beta\}\ge 1\\ \lfloor\alpha\rfloor+\lfloor\beta\rfloor,&\{\alpha\}+\{\beta\}<1\end{cases}$

where $\{\alpha\}:=\alpha-\lfloor\alpha\rfloor$ is the fractional part of $\alpha$.

Proof of the proposition. Let $s=v_{p}(n+a)$. Then

$\displaystyle h=\sum_{j=1}^s\left(\left\lfloor\frac{n+k}{p^j}\right\rfloor-\left\lfloor\frac{n-1}{p^j}\right\rfloor\right)-s$.

First suppose that $(k+1,p)=1$. Then $v_{p}(k!)=v_{p}((k+1)!)$, so by the lemma we get

$\displaystyle h\le\sum_{j=1}^s\left(\left\lfloor\frac{k+1}{p^j}\right\rfloor+1\right)-s\le v_p((k+1)!)=v_{p}(k!)$,

as desired. Now suppose that $p^u\parallel k+1$ for some $u\ge 1$. Then $\{\frac{k+1}{p^j}\}=0$, so $\{\frac{n-1}{p^j}\}+\{\frac{k+1}{p^j}\}<1$, for each $j\le u$. Thus

\displaystyle\begin{aligned}h&\le\sum_{j=1}^u\left\lfloor\frac{k+1}{p_i^j}\right\rfloor+\sum_{j=u+1}^s\left(\left\lfloor\frac{k+1}{p_i^j}\right\rfloor+1\right)-s\\ &=\sum_{j=1}^u\left(\left\lfloor\frac{k}{p_i^j}\right\rfloor+1\right)+\sum_{j=u+1}^s\left(\left\lfloor\frac{k}{p_i^j}\right\rfloor+1\right)-s\\ &\le v_{p}(k!).\end{aligned}

Hence the result follows. $\square$