Prove that $p^n$ divides rising factorial $a^{(b)}$ for all integers $a$ iff $\sum^\infty_{i=1} floor(b/p^i) \ge n$

Question

Let $p$ be a prime integer, and $b$ and $n$ positive integers. Prove that $p^n$ divides $a^{(b)}$ for all integers $a$ iff $\sum^\infty_{i=1} floor(b/p^i) \ge n$.

Note: $a^{(b)}$ is the rising factorial, $a(a+1)(a+2)...(a+n-1)$.

This question was inspired by Putnam 2016 A1.

Proof:

Consider a sequence $s$ of $j$ consecutive integers, with $\prod{s}$ their product (i.e., the product of all elements of the sequence). Let $div(s, m)$ be the number of elements of $s$ divisible by $m$. By the fundamental theorem of arithmetic, $p^n$ divides $\prod{s}$ iff $\sum^{\infty}_{i=1}div(s,p^i) \ge n$.

By the division algorithm, $floor(j/m) \le div(s,m) \le ceil(j/m)$ for all positive integers $m$. Furthermore, if $s_0 \mod y = 1$, $div(s,m) = floor(j/m)$.

Therefore, $\sum^{\infty}_{i=1}div(s,p^i) \ge \sum^{\infty}_{i=1}floor(j/p^i)$, so $\sum^\infty_{i=1} floor(b/p^i) \ge n$ implies $p^n$ divides $a^{(b)}$.

Conversely, if $\sum^\infty_{i=1} floor(b/p^i) < n$, then there exists an $a$ for which $p^n$ does not divide $a^{(b)}$: For any $a$ = $zp^n+1$, with $z$ a nonnegative integer, $s_0 \mod p^r = 1, r\le n$, so $\sum^{\infty}_{i=1}div(s,p^i) = \sum^{\infty}_{i=1}floor(j/p^i)$.

Questions:

1. Is this proof correct?
2. Is it optimal? Is there a simpler, more elegant, or otherwise superior proof?
3. Is it written well? How can the writing be improved?

Answer 1

This is correct and is a good way to go about it, but the proof could be written more clearly. I think this is somewhat of a difficult proof to express, but I have some suggestions on how to do it well: first, there is a critically important quantity that you have not named anywhere despite the fact that your whole proof is talking about it: we should define something like

For an integer $m$ and prime $p$, let $\|m\|_p$ be the maximum $k$ such that $p^k$ divides $m$.

Having some notation for this let's you be really explicit about your proof and how exactly the Fundamental Theorem of Arithmetic is involved. In particular, you can productively introduce two precise lemmas after this:

Using the Fundamental Theorem of Arithmetic, we observe that $\|m\|_p$ is equal to the number of powers of $p$ that divide $m$ and that $\|m_1m_2\|_p = \|m_1\|_p + \|m_2\|_p$.

Only once you have the simplest elements in place is it wise to bring in a sequence - and, while bundling terms into larger objects like sequences is often useful, this is not such a case; using indices is clearer here than avoiding them - especially since $\prod s$ for a sequence $s$ is likely to confuse readers who expect the term after $\prod$ to be an expression of some indexing quantity - not a symbol representing a sequence. So, instead, we might write:

Let $m_1, m_2, \ldots, m_{\ell}$ be any finite sequence of integers. Repeatedly applying the previous property gives $$\left\|\prod_{i=1}^{\ell} m_i\right\|_p=\sum_{i=1}^{\ell}\|m_i\|_p.$$

We might then just state, in words, the result you mean with the $\operatorname{div}$ function:

Note that, by our first observation, the right hand side counts the number of pairs $(k,i)$ such that $p^k$ divides $m_i$.

After this, it's clear that you have good reason to define another quantity.

Let $\operatorname{div}(c,m)$ be the number of multiples of $c$ in the sequence $m$. We can rewrite the last expression as $$\left\|\prod_{i=1}^{\ell} m_i\right\|_p=\sum_{i=1}^{\infty}\operatorname{div}(p^i, m).$$

Then, we introduce that fact that $m$ is a sequence of consecutive integers:

Note that if $m$ is a sequence of $b$ consecutive integers, then $$\operatorname{floor}(b/c) \leq \operatorname{div}(c,m)$$

Since we never use the upper bound, we don't have a good reason to introduce it - we want to keep the reader focussed on what matters, since we can immediately leap to the conclusion;

If we substitute $c=p^i$ into this inequality and sum over $i$ we get $$\sum_{i=1}^{\infty}\operatorname{floor}(b/p^i)\leq \sum_{i=1}^{\infty}\operatorname{div}(p^i, m) = \left\|\prod_{i=1}^{\ell} m_i\right\|_p$$

And we can then basically state what we're trying to prove and we have it right here:

As a consequence of this equation, if $n\leq \sum_{i=1}^{\infty}\operatorname{floor}(b/p^i)$ then it must also be that, for any sequence $m$ of $b$ consecutive integers we have $\left\|\prod_{i=1}^{\ell} m_i\right\|_p$ - or, otherwise said, that $p^n$ divides $a^{(b)}$ for all $a$.

And then, for the converse, we just note one last thing:

Note that if $m$ is the sequence of the first $b$ positive integers, then $\operatorname{div}(c,m) = \operatorname{floor}(b/c)$, implying that $$\left\|1^{(b)}\right\|_p = \sum_{i=1}^{\infty}\operatorname{floor}(b/p^i)$$ In particular, this implies that $p^n$ divides $1^{(b)}$ if and only if $n \leq \sum_{i=1}^{\infty}\operatorname{floor}(b/p^i)$ which in, combination with the previous direction, shows that $p^n$ divides $a^{(b)}$ for all $a$ if and only if $n \leq \sum_{i=1}^{\infty}\operatorname{floor}(b/p^i)$.

Mostly, the edits I suggest here are to be more verbose and more gradual - as you have it, you've packed all of the machinery you're using into the first two sentences. The effect of this is that, before the reader has processed anything about your argument, they're trying to make sense of (1) a somewhat odd product notation and (2) an unmotivated definition. That's not great because it falls back on "the reader can mechanically verify this" rather than "the reader understands the flow of the argument." Generally, definitions are best to introduce when it's already somewhat clear what you're going to do with them.

The other edits I suggest are more on the lines of cleaning unnecessary things up - in particular, you sort of mix remarks with proof, but there's a reason authors often write a short proof and then collect remarks afterwards: it is not helpful for the reader to process a condition like "this is an equality if $m\equiv 1\pmod{c}$" in the middle of a proof because that's not relevant to the direction the proof is showing at that moment.