About a specific step on a proof of ${p^Rm\choose p^R} \equiv m \pmod{mp}$

110 Views Asked by At

I'm following a proof of the following fact: let $p > 0$ be a prime. Then if $m, R \in \mathbb{N}$,

$$ {p^Rm\choose p^R} \equiv m \pmod{mp} $$

It starts by noting that ${p^Rm\choose p^R} = m{p^Rm-1\choose p^R-1}$ and so it suffices to see that ${p^Rm-1\choose p^R-1} \equiv 1 \pmod{p}$. Then, it follows by expanding as follows:

$$ {p^Rm-1\choose p^R-1} = \frac{(p^Rm-1)\cdots (p^Rm-1-(p^Rm-1))}{(p^R-1)\cdots 1} = \\ = \frac{(p^Rm-1-(p^Rm-1))\cdots (p^Rm-1)}{(p^R-1)\cdots 1} = \prod_{j = 1}^{p^R-1}\left(\frac{p^Rm}{j}-1\right) $$

and since $p^R \not | j$, there exist coprime $m_j,s_j$ with $p \not | s_j$ such that $\frac{p^Rm}{j} = p\frac{m_j}{s_j}$. In effect, we can take $\frac{m_j}{s_j}$ the irreducible fraction representation of $\frac{p^{R-1}m}{j}$ from which the equality follows, and $p \not | s_j$ because since $p^{R-1}ms_j = jm_j$, the contrary would imply $p^R | jm_j$ and thus $p | m_j$ which would contradict $m_j$ and $s_j$ being coprime. So far I'm following along, but here's the step that I'm having doubts about; it is claimed that:

$$ \prod_{j = 1}^{p^R-1}\left(\frac{p^Rm}{j}-1\right) = (-1)^{p^R-1} + p\frac{n}{s} \tag{1} $$

with $p \not | s$ and $lcd(n,s) = 1$. How is $(1)$ justified? I don't see how it is an immediate consequence of the previous steps. From there on I can see how the result follows quite directly: since the last expression is after all an integer, and since $p \not | s$, $lcd(n,s) = 1$, we have that $s = 1$ and thus $\prod_{j = 1}^{p^R-1}\left(\frac{p^Rm}{j}-1\right) \equiv 1\pmod{p}$ as desired.

1

There are 1 best solutions below

3
On BEST ANSWER

Replacing every factor by the corresponding expression $p \frac{m_j}{s_j}$ from your post we have that the left hand side of $(1)$ equals

$$\prod_{j = 1}^{p^R-1}\left(\frac{p m_j}{s_j}-1\right)$$

Written even more concisely it is of the form

$$\prod_{j = 1}^{N}(x_j-1) \tag{2}$$

where $x_j = pm_j/s_j$ and $N = p^R - 1$.

Now writing out this product as you learn in high school you get $2^N$ terms, exactly one of which equals $(-1)^N$ and all the other terms are products of some positive number of $x_j$'s with some sign (plus or minus). The $(-1)^N$ also appears on the right hand side of (1) so the remaining question is if we can write the sum of the 'other terms' in the form $p \frac{n}{s}$. With the desired properties.

We note a few things that all the 'other terms' in the expansion of (2) have in common.

  • Each individual term $X$ is a product of $x_j$'s, so it can be written as a fraction whose denominator is the product of some positive number of $s_j$'s and whose enumerator contains at least one factor $p$ (in fact one for each $x_j$ contributing to $X$).

  • In the representation in the previous bullet point, the denominator of $X$ is a divisor of the number $s := \prod_{j=1}^N s_j$. This $s$ really is intended to be the $s$ of the original post, but we define it here as the product of all the $s_j$.

  • By the previous bullet point, $X$ has a unique representation as a fraction whose denominator equals $s$. Since we obtained this representation by multiplying both enumerator and denominator of the representation in the first bullet point by a positive integer, the enumerator of the new representation is still divisible by $p$.

Now we look at the sum of all the terms. It can be represented as a fraction with denominator $s$ by the last bullet point and, also by that bullet point, the enumerator of that fraction is a sum of integers each of which is divisible by $p$. Hence the enumerator is divisible by $p$ as well.

This shows that indeed the right hand side of (1) can be written as $(-1)^N + p\frac{n}{s}$ with $N, p, s$ as above, and some $n$.

The fact that $p$ does not divide $s$ follows from the definition of $s$.

I am not sure what you mean by $lcd(n, s) = 1$ but from the fact that the left hand side of $(1)$ is an integer, we have that the right hand side is an integer as well.

From here it follows that $(pn)/s$ is an integer so that $s|(pn)$ and hence $q|(pn)$ for every prime factor $q$ of $s$. By Euclid's lemma this means $q$ divides $p$ or $q$ divides $n$. But $q|p$ is only possible when $q = p$, since both are prime, and $q = p$ is ruled out by $q | s$.

So we find that $q|n$ and hence that $pn/s = pn'/s'$ for integers $n' = n/q, s' = s/q$. Repeating this process until no $q$'s are left we end up with $pn/s = pk/1 = pk$ for some $k$.

It follows that the right hand side of $(1)$ is of the form $(-1)^N + pk$ for some integer $k = n/s$ and since $N$ is even this means that the left hand side of $(1)$ is congruent $1 \mod p$.