5
$\begingroup$

An argument that I just came across asserts that if $p$ is prime, and $k, q\in \mathbb{Z}_{>0}$, then

$$\frac{1}{q} \binom{p^k q}{p^k} \equiv 1 \mod p \;.$$

This assertion was made in a way (i.e. without proof or citation) that suggests the author considers it pretty obvious, but it isn't so to me. If there's a simple proof of it, I'd like to see it.

(Note: $q$ need not be coprime to $p$.)

(Searching online I found a result called Lucas' Theorem, which looks like it may include the equivalence above as a special case, but I'm not sure yet. In any case, I did not find the proof of Lucas' theorem particularly easy, but, if the equivalence above is indeed a special case of Lucas' theorem, I hope there may be an easier proof for it.)

$\endgroup$
1
  • 3
    $\begingroup$ This expression actually comes up in one of the proofs of Sylow's Theorem in group theory. It is proved that, this is equal modulo $p$ to the number of subgroup of order $p^k$ in any group of order $p^kq$. By considering the cyclic group, which has a unique subgroup of order $p^k$, you can then conclude that it is in fact equal to $1$ mod $p;$, which does provide a very indirect proof of what you are asking! $\endgroup$
    – Derek Holt
    Jan 29, 2014 at 14:52

2 Answers 2

Reset to default
3
$\begingroup$

Your assertion is as follows. $${1 \over q} \prod_{i=1}^{p^k}{p^k(q-1)+i \over i} \equiv 1 \mod{p}$$ Let $\mathbb{p}(n)$ be largest $e \in \mathbb{N}_0$ so that $p^e \mid n$ and $\sigma(n) = {n \over p^{\mathbb{p}(n)}}$. It is apparent that for every $i < p^k$ $\mathbb{p}(p^k(q-1)+i) = \mathbb{p}(i)$ and $\sigma(p^k(q-1)+i) \equiv \sigma(i) \mod{p}$. Finally for the last $i = p^k$ we have ${p^k(q-1)+p^k \over p^k} = q$ which is eliminated by the fraction $1 \over q$.

$\endgroup$
6
  • $\begingroup$ Thanks! I can't say that I can follow your argument all the way through, but puzzling over it inspired a proof that I've submitted as an answer. It's likely nothing more than a plodding rewording of your proof. $\endgroup$
    – kjo
    Jan 30, 2014 at 12:47
  • 1
    $\begingroup$ You understood a lot of my proof, somehow a proof for such assertion is even simpler than you think. When you arrive at $p^{j_i}{q-1 \over c_i}+1$ it does not matter at all what ${q-1 \over c_i}$ is congruent to $p$ as long as $p \not \mid c_i$ which you already stated, so no need to choose any integers. $\endgroup$
    – P.K.
    Feb 1, 2014 at 16:21
  • $\begingroup$ Thanks for your comment. (I assume you're referring to my introduction of $d_i$ into the argument.) The excessive complexity of my proof comes from the fact that I don't know much about algebra $\!\!\!\!\mod p$ outside of integers, hence the extra effort to put everything in terms of integers... (It reminds me of the extra complexity of mathematical derivations before the acceptance of, e.g., the negative integers.) $\endgroup$
    – kjo
    Feb 1, 2014 at 16:56
  • 1
    $\begingroup$ This is a good example of a situation where rational congruences are powerful. Although it is obvious that such product is an integer, we intuitively have no idea how to pair the factors of denominators for numerators to actually come up with integers to search for congruences. Truth is that congruences are ridiculously easy to generalize for rational numbers; only thing you necessary have to do is to keep an eye for factors of the mod in denominators. For example in this case we immediately see that given any integers $a, b, c, n$ always ${a c + n \over b c + n} \equiv 1 \mod{c}$ $\endgroup$
    – P.K.
    Feb 1, 2014 at 17:21
  • 1
    $\begingroup$ For example above congruence assertion works fine otherwise but say you take $n \equiv 0$ for some factor $f$ of $c$ and it is not so true anymore is it. $\endgroup$
    – P.K.
    Feb 1, 2014 at 17:41
1
$\begingroup$

In the process of trying to understand P.K.'s I came up with the following proof. This could very well be exactly P.K.'s proof, although since I can't fully follow P.K.'s argument I can't say for sure.

Clearly

$$ \frac{1}{q} \binom{p^k q}{p^k} = \binom{p^k q - 1}{p^k - 1} = \prod_{i=1}^{p^k - 1}\frac{p^k (q - 1) + i}{i} = \prod_{i=1}^{p^k - 1}\left( \frac{p^k (q - 1)}{i} + 1 \right) \,.$$

(In what follows, $i$ always represents an arbitrary index of the product in the RHS above, or IOW, an arbitrary element of $\{1,\dots,p^k - 1\}$. Also, every statement about $i$ below should be construed as being implicitly preceded with a "$\forall \, i \in \{1,\dots,p^k - 1\}$".)

The key observation is that $i$ can be factored as $i = p^{k - j_i}c_i$, where $0 < j_i \leq k$ is an integer, and $p \nmid c_i$. This means that

$$\frac{p^k (q - 1) + i}{i} = p^{j_i}\frac{(q - 1)}{c_i} + 1\,,$$

Now, $p \nmid c_i$ means that there exists an integer $0 < d_i < p$ such that

$$\frac{(q - 1)}{c_i} \equiv d_i\,(q - 1) \mod p\;.$$

Since $j_i > 0$, the congruence above implies that

$$\frac{p^k (q - 1) + i}{i} = p^{j_i}\frac{(q - 1)}{c_i} + 1 \;\;\equiv\;\; p^{j_i} d_i (q - 1) + 1 \;\;\equiv\;\; 1\mod p\,,$$

From this it follows immediately that

$$ \frac{1}{q} \binom{p^k q}{p^k} = \prod_{i=1}^{p^k - 1}\left( \frac{p^k (q - 1)}{i} + 1 \right) \;\;\equiv\;\; \prod_{i=1}^{p^k - 1} 1 \;\;\equiv 1\mod p\,.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .