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


Leave a comment

Filed under Number theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s