Show that there exist $n$ such that $r$ divides $\binom{p^n}{q^n}$

Cross-posted to Math Overflow

Two positive integers $p,q$ and a prime $r$ are given, such that $r>p>q>1$. I have to show that there exist $n$ such that $$r\ \text{divides}\ \binom{p^n}{q^n}$$

Should I use Lucas' theorem? I can't solve it.

Solution 1:

Notation:

• $a\operatorname{mod} m$ is the residue of $a$ modulo $m$.
• $v_r(a) = \max\{n\ge 0: r^n\mid a\}$,
• $\mathrm{ord}_{m}(a) = \min\{n\ge 1: m\mid a^n-1\}$.

As it was already explained here, we need to show that for some $n$ and $l$ $$p^n \operatorname{mod} r^l < q^n \operatorname{mod} r^l. $$ Assume the contrary.

Let $$k = \mathrm{ord}_r p.$$ If $q^k\neq 1\pmod r$, then we are done with $n=k$, $l=1$. So we have $j:=\mathrm{ord}_r q\mid k$.

Denote $$m = v_r(q^k-1).$$ If $v_r(p^k-1)>m$, then $n=k, l=m+1$ works.

Case 1. $v_r(p^k-1)=m$.

By Hensell's lifting lemma for any $l\ge 1$ $$ \mathrm{ord}_{r^{l+m}} p = r^l k,\quad \mathrm{ord}_{r^{l+m}} q = r^l j, $$ so $$ \mathrm{ord}_{r^{l+m}} p^k = r^l,\quad \mathrm{ord}_{r^{l+m}} q^k = r^l.\tag{1} $$

The group $\mathbb{Z}^*_{r^{l+m}}$ of invertible elements modulo $r^{l+m}$ is cyclic of order $r^{l+m-1}(r-1)$. Let $\varepsilon$ be its generator. Then it follows from $(1)$ that $$ p^k = \varepsilon^{sr^m(r-1)} \operatorname{mod} r^{l+m}, \quad q^k = \varepsilon^{tr^m(r-1)} \operatorname{mod} r^{l+m},\tag{2} $$ where $r\nmid st$. Now consider $$ p^k, p^{2k}, \dots, p^{(r^{l}-1)k} \operatorname{mod} r^{l+m} $$ and $$ q^k, q^{2k}, \dots, q^{(r^{l}-1)k} \operatorname{mod} r^{l+m}. $$ Because of $(2)$, both sequences contain $\varepsilon^{r^m(r-1)}, \varepsilon^{2r^m(r-1)},\dots, \varepsilon^{(r^{l}-1)r^m(r-1)}$ in some order. Since $p^{ik}\operatorname{mod} r^{l+m} \ge q^{ik}\operatorname{mod} r^{l+m}$ for all $i$, then $p^{k}\operatorname{mod} r^{l+m} = q^{k}\operatorname{mod} r^{l+m}$. However, this cannot happen for $l$ large enough (so that $r^{l+m}>p^k$). This finishes the proof for this case.

Case 2. $d:=v_r(p^k-1)<m$.

Consider $$ p^{k-1}, p^{2k-1}, \dots, p^{rk-1} \operatorname{mod} r^{d+1}. $$ From $q^{sk-1} = q^{k-1}\operatorname{mod} r^{d+1}$ it follows that $p^{sk-1}\operatorname{mod} r^{d+1} \ge q^{k-1} \operatorname{mod} r^{d+1}$. But $p^{sk-1}$ for $s=1\dots,r$ have different residues modulo $r^{d+1}$ and the same residue modulo $r^{d}$. Therefore, the residues modulo $r^{d+1}$ are equal to $$p^{k-1}\operatorname{mod} r^{d}, (p^{k-1}\operatorname{mod} r^{d}) + r^{d}, \dots, (p^{k-1}\operatorname{mod} r^{d}) + (r-1)r^{d}$$ in some order. In particular, we get $q^{k-1} \operatorname{mod} r^{d+1} \le p^{k-1}\operatorname{mod} r^{d}<r^{d}$. But then $$q^{k}\operatorname{mod} r^{d+1} = \big(q\cdot (q^{k-1} \operatorname{mod} r^{d+1})\big)\operatorname{mod} r^{d+1}$$ cannot be equal to $1$, since $q<r$. The proof is now complete.