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

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.

Tags:

Number Theory

Contest Math

Related

will a nonempty countable and compact subset of a metric space always contain an isolated point? (1) Sum of two factorials in two ways; (2) Value of $a^{2010}+a^{2010}+1$ given $a^4+a^3+a^2+a+1=0$. Proving that $\frac{ab}{c^3}+\frac{bc}{a^3}+\frac{ca}{b^3}> \frac{1}{a}+\frac{1}{b}+\frac{1}{c}$ Does there exist an injection $f:\mathbb{R}\to P(\mathbb{N})$ that satisfies these conditions? Cantor Set (Hausdorff) $f:\mathbb{R}\rightarrow\mathbb{R}$ is not one-to-one if $[f(x)]^2-4\cdot f(x^5)+3=0,\forall x\in\mathbb{R}$? How to use Stokes theorem in the presence of holes? Let $T$ be any subset of $\{1,2,3,...,100\}$ with $69$ elements. Prove that one can find four distinct integers such that $a+b+c=d$. Prove that $\sum_{l=0}^{n} \binom{n}{l}^2 (x+y)^{2l} (x-y)^{2(n-l)} = \sum_{l=0}^{n} \binom{2l}{l} \binom{2(n-l)}{n-l} x^{2l}y^{2(n-l)}$ Is there a *simple* example showing that uncorrelated random variables need not be independent? System with a Lyapunov function over $\mathbb{R}^n$ but not globally asymptotically stable Algebraic Geometry: What am I doing wrong?

Recent Posts