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.
 A: 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.
A: Edit: Done!
Theorm(kummer):Let $n$ and $i$ be positive integers with $i\le n$ , and let $p$ be a prime number.then $p^t$ divides $\binom{n}{i}$ if and only if $t$ is less than or equal to to the number of carries in the addition $(n-i)+i$ in the base $p$
Solution:
We claim for $n=r$ problem condtion is true.
Suppose $(p^n)_{10}=(p_{n}p_{n-1}...p_0)_r$ and $(q^n)_{10}=(q_{n}q_{n-1}...q_0)_r$ then it is clear :
\begin{align}
   \binom{q^n} {p^n} = \frac {p^n} {q^n} \binom {p^n-1} {q^n-1}
\end{align}
 Using multiple times from this formula we can write :
\begin{align}
   \binom{q^n} {p^n} = \frac {p^n} {q^n}×...× \binom {p^{n-1}-(q+1)} {q^{n-1}-(q+1)}
\end{align}
so for the additional carry we can write $((p_{n}p_{n-1}...p_0)_r - (q_{n}q_{n-1}...q_0)_r) + ((q_{n}q_{n-1}...q_0)_r -(q_0+1)_r)$ since with little fermat's theorm we know $p^r\equiv p=p_0 \pmod r$ and $q^r\equiv q=q_0 \pmod r$ 
and knowing that $q < q+1 \le p < r $ in the right most digits additon we have(note that $q<q+1$ and $q=q_0$ with $n=r$ condition):
$(p-q)+(r+q-(q+1))=p-q+r-1$
but since $1 \le p-q$ we get $r \le p-q+r-1$ ths  we are going to have at least one carry with $n=r$ and with kummer's theorm problem will be solved.
A: I write again main expression, which need to be multiple of r :
$$
{{p^n!} \over {q^n(p^n-q^n)!}}
$$
Again i have deleted everything, because i found my error, but luckily i found another answer : 
$$
(q^n \mod r) + ((p^n-q^n) \mod r) >= r
$$
I will explain a little bit this expression : $q^n$ will contain x times r, or multiples of r in his factorial. Anyway it will contain at least $\lfloor q^n/r\rfloor$ times r. It can be more, because if one factor is for example $r^2$ or multiple, then it will contain more times r. Anyway, because $p^n!$ is higher, it will contain every factor of $q^n!$. We only need one factor of r, and it will be enough. We will by sure have more factors of r in this dividend if a sum both divisors will contain less times r. And this we check with both remainder. Let us write last expression in a more easier form :
$$
r({q^n \over r} - \left \lfloor{q^n \over r}\right \rfloor) +
r({{p^n-q^n} \over r} - \left \lfloor{{p^n-q^n} \over r}\right \rfloor) 
>=r
$$
$$
({q^n \over r} - \left \lfloor{q^n \over r}\right \rfloor) +
({{p^n-q^n} \over r} - \left \lfloor{{p^n-q^n} \over r}\right \rfloor) 
>=1
$$
$$
{p^n \over r} - \left \lfloor{q^n \over r}\right \rfloor
- \left \lfloor{{p^n-q^n} \over r}\right \rfloor
>=1
$$
Another way to get to this result is :
First we define few functions :
$N_r(x)$="number of prime factors r in x!"
$Q_y(x)=\left \lfloor {x \over y} \right \rfloor$
Now note that :
$$
N_r(x)=\sum_{k=1}^{{\log(y) \over \log(r)}} Q_{r^k}(x)
$$
I explain this last step with a example. For example x=29 and r=3. Then 
$$
x!= 1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20*21*22*23*24*25*26*27*28*29
$$
Let us count only multiples of 3 : 
$$
3^1*1,3^1*2,3^2*1,3^1*4,3^1*5,3^2*2,3^1*7,3^1*8,3^3
$$
How many times we have multiples of 3^1 disregarding if it is 3^2 or 3^3 ? We have exactly $Q_3(29)=9$ times. If we take of all this factors 3, we left with :
$3^1$ from $3^2*1$ 
$3^1$ from $3^2*2$ ,and
$3^2$ from $3^3$ 
Now we take of again all this factors 3 from $3^2$ places. Exactly $Q_{3^2}(29)$=$Q_{9}(29)=3$ times. We left only with 
$3^1$ from $3^3$ 
So, factors 3 in total from 29! are :
$$
N_3(29)=Q_3(29)+Q_{3^2}(29)+Q_{3^3}(29)=9+3+1=10
$$
For a general proof refere to https://en.wikipedia.org/wiki/Legendre%27s_formula#Proof.
After this little explanation of formula $N_r(x)$, let us continue :Necessary and sufficient condition that our division is multiple of r is that :
$$
N_r(p^n)-N_r(q^n)-N_r(p^n-q^n)>=1
$$
$$
\sum_{k=1}^{\infty} Q_{r^k}(p^n)-\sum_{k=1}^{\infty} Q_{r^k}(q^n)-\sum_{k=1}^{\infty} Q_{r^k}(p^n-q^n)>=1
$$
$$
\sum_{k=1}^{\infty} {Q_{r^k}(p^n)-Q_{r^k}(q^n)-Q_{r^k}(p^n-q^n)}>=
Q_{r}(p^n)-Q_{r}(q^n)-Q_{r}(p^n-q^n)>=1
$$
$$
\left \lfloor {p^n \over r} \right \rfloor -
\left \lfloor {q^n \over r} \right \rfloor -
\left \lfloor {{p^n-q^n} \over r} \right \rfloor >=1
$$
In fact, this function is very similar to previous formula adding one more floor. This sume, in fact can be only 0 or 1.
Let us put this formula in a form of remainders :
$$
r\left \lfloor {p^n \over r} \right \rfloor -
r\left \lfloor {q^n \over r} \right \rfloor -
r\left \lfloor {{p^n-q^n} \over r} \right \rfloor >=r
$$
Add $-p^n+q^n+(p^n-q^n)=0$ and reorder
$$
-(p^n-r\left \lfloor {p^n \over r} \right \rfloor) +
(q^n-r\left \lfloor {q^n \over r} \right \rfloor)+
((p^n-q^n)-r\left \lfloor {{p^n-q^n} \over r} \right \rfloor)>=r
$$
Let us define $R_r(x)=x \mod r=x-r\left \lfloor {x \over r} \right \rfloor$ and simplfy this expression :
$$
-R_r(p^n)+R_r(q^n)+R_r(p^n-q^n)>=r
$$
Reorder this :
$$
R_r(q^n)+(R_r(p^n-q^n)-R_r(p^n))>=r
$$
We call $R_r(q^n)+R_r(p^n-q^n)-R_r(p^n)$ main residual expression.
Inside parenthesis $(R_r(p^n-q^n)-R_r(p^n))$ we have form $R(a-b)-R(a)$. Results from this can be only R(-b) or -R(b). In our equality we will need that parenthesis expression is bigger or same as 0 in order to get $R_r(-q^n)$.Note that $R_r(q^n)+R_r(-q^n)=r>=r$. Continue then with this expression :
$$
R_r(p^n-q^n)-R_r(p^n)>=0
$$
$$
R_r(p^n-q^n)>=R_r(p^n)
$$
In which case we will have a guaranty that this inequality is true ? In case 
$$
R_r(p^n)=1
$$
Now, we have a important point : r is prime. So we can apply "little Fermat theorem" (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem). If
$$
n=r-1
$$
But just in this case, always will happen that also $R_r(q^n)=R_r(p^n)=1$ for a same reason and then in main expression we get :
$$
R_r(q^n)+R_r(p^n-q^n)-R_r(p^n)=1+R_r(p^n-q^n)-1=R_r(p^n-q^n)<r
$$
when n=r-1. 
Easier is to work with next (abstracted) condition :
$$
R_r(q^n)-R_r(p^n)>0
$$
or
$$
R_r(q^n)>R_r(p^n)
$$
This is a necessary condition in order to get a n for resolve main residual expression. 
Greatings. Daniel
