Mostrar que existen $n$ tal que $r|\binom{p^n}{q^n}$

Question

Dos enteros positivos $p,q$ y un alto $r$ son dado, que $r>p>q>1$.
Tengo que demostrar que existen $n$ tal que % $ $$r|\binom{p^n}{q^n}$

¿Debo usar Teorema de Lucas? No puedo resolverlo.

Answer 1

Notación:

• $a\operatorname{mod} m$ es el residuo de $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\}$.

---

Como ya se explicó aquí, tenemos que mostrar que para algunos $n$ y $l$ $$p^n \operatorname{mod} r^l < q^n \operatorname{mod} r^l. $$ Asumir lo contrario.

Vamos $$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\mediados de k$.

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

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

Por Hensell de elevación del lema para cualquier $l\ge 1$ $$ \mathrm{ord}_{r^{l+m}} p = r^l k,\quad \mathrm{ord}_{r^{l+m}} q = r^l j.\la etiqueta{1} $$ El grupo $\mathbb{Z}^*_{r^{l+m}}$ de los invertible elementos modulo $r^{l+m}$ es isomorfo a $C_{r^{l+m-1}}\times G$ donde $|G|=p-1$. Deje $\varepsilon$ ser la imagen de el generador de $C_{r^{l+m-1}}$ (veces que el elemento de identidad de $G$)$\mathbb{Z}^*_{r^{l+m}}$. Entonces lo que sigue es de $(1)$ y el isomorfismo que $$ p = \varepsilon^{sp^m} p'\operatorname{mod} r^{l+m}, \quad q = \varepsilon^{tp^m} p' \operatorname{mod} r^{l+m},\etiqueta{2} $$ donde $r\nmid st$ y $\mathrm{ord}_{r^{l+m}}p' = k$, $\mathrm{ord}_{r^{l+m}}q'=j$. Ahora considere la posibilidad de $$ p^k, p^{2k}, \dots, p^{(r^{l}-1)k} \operatorname{mod} r^{l+m} $$ y $$ q^k, q^{2k}, \dots, q^{(r^{l}-1)k} \operatorname{mod} r^{l+m}. $$ Porque de $(2)$, ambas secuencias contienen $\varepsilon^{p^m}, \varepsilon^{2p^m},\dots, \varepsilon^{(r^{l}-1)p^m}$ en un cierto orden. Desde $p^{ik}\operatorname{mod} r^{l+m} \ge q^{ik}\operatorname{mod} r^{l+m}$ todos los $i$,$p^{k}\operatorname{mod} r^{l+m} = q^{k}\operatorname{mod} r^{l+m}$. Sin embargo, esto no puede suceder por $l$ lo suficientemente grande (por lo que el $r^{l+m}>p^k$). Esto termina la prueba para este caso.

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

Considere la posibilidad de $$ p^{k-1}, p^{2k-1}, \dots, p^{rk-1} \operatorname{mod} r^{d+1}. $$ De $q^{sk-1} = q^{k-1}\operatorname{mod} r^{d+1}$ se sigue que $p^{sk-1}\operatorname{mod} r^{d+1} \ge q^{k-1} \operatorname{mod} r^{d+1}$. Pero $p^{sk-1}$ $s=1\dots,r$ tienen diferentes residuos modulo $r^{d+1}$ y el mismo residuo modulo $r^{d}$. Por lo tanto, los residuos modulo $r^{d+1}$ son iguales a $$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$. La prueba se ha completado.

Answer 2

Edit: Hecho!

Theorm(kummer):Vamos a $n$ $i$ ser enteros positivos con $i\le n$ , y deje $p$ ser un número primo.a continuación, $p^t$ divide $\binom{n}{i}$ si y sólo si $t$ es menor o igual que el número de acarreos en la adición $(n-i)+i$ en la base de $p$

Solución: Afirmamos $n=r$ problema condtion es cierto.

Supongamos $(p^n)_{10}=(p_{n}p_{n-1}...p_0)_r$$(q^n)_{10}=(q_{n}q_{n-1}...q_0)_r$, entonces es claro :

\begin{align} \binom{q^n} {p^n} = \frac {p^n} {q^n} \binom {p^n-1} {q^n-1} \end{align} Usar varias veces a partir de esta fórmula se puede escribir :

\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}

así que para el adicional de llevar a podemos escribir $((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)$ ya que con un poco de fermat theorm sabemos $p^r\equiv p=p_0 \pmod r$ $q^r\equiv q=q_0 \pmod r$ y saber que $q < q+1 \le p < r $ en el derecho de la mayoría de dígitos additon tenemos(tenga en cuenta que $q<q+1$ $q=q_0$ $n=r$ condición):

$(p-q)+(r+q-(q+1))=p-q+r-1$

pero desde $1 \le p-q$ obtenemos $r \le p-q+r-1$ ths vamos a tener al menos un con $n=r$ y con kummer del theorm problema será resuelto.

Answer 3

Escribo de nuevo principal de expresión, que tiene que ser múltiplo de r : $$ {{p^n!} \over {q^n(p^n-p^n)!}} $$ De nuevo he borrado todo, porque me di cuenta de mi error, pero por suerte me encontré otra respuesta : $$ (p^n \mod r) + ((p^n-p^n) \mod r) >= r $$ Voy a explicar un poco esta expresión : $q^n$ contendrá el tiempo x r, o múltiplos de r en su factorial. De todos modos contendrá, al menos, $\lfloor q^n/r\rfloor$ los tiempos de r. Puede ser más, porque si uno de los factores es, por ejemplo, $r^2$ o múltiples, a continuación, contener veces más r. De todos modos, debido a $p^n!$ es mayor, va a contener cada factor de $q^n!$. Sólo necesitamos un factor de r, y va a ser suficiente. Vamos por seguro que tienen más factores de r en esta dividendo si la suma de ambos divisores contendrá menos veces r. Y esto podemos comprobar, tanto con el resto. Vamos a escribir la última expresión en una forma más fácil : $$ r({q^n \sobre r} - \left \lfloor{q^n \sobre r}\right \rfloor) + r({{p^n-p^n} \over r} - \left \lfloor{{p^n-p^n} \over r}\right \rfloor) >=r $$ $$ ({q^n \sobre r} - \left \lfloor{q^n \sobre r}\right \rfloor) + ({{p^n-p^n} \over r} - \left \lfloor{{p^n-p^n} \over r}\right \rfloor) >=1 $$ $$ {p^n \sobre r} - \left \lfloor{q^n \sobre r}\right \rfloor - \left \lfloor{{p^n-p^n} \over r}\right \rfloor >=1 $$ Otra forma de llegar a este resultado es :
Primero definimos algunas funciones :
$N_r(x)$="número de factores primos de r en x!"
$Q_y(x)=\left \lfloor {x \over y} \right \rfloor$
Ahora tenga en cuenta que : $$ N_r(x)=\sum_{k=1}^{{\log(y) \\log(r)}} Q_{r^k}(x) $$ Explico esto último con un ejemplo. Por ejemplo x=29 y r=3. Entonces $$ 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 $$ Que nos permiten contar sólo los múltiplos de 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 $$ Cuántas veces hemos múltiplos de 3^1 ignorando si es 3^2 o 3^3 ? Tenemos exactamente $Q_3(29)=9$ veces. Si tomamos de todos estos factores 3, nos quedamos con :
$3^1$ $3^2*1$
$3^1$ $3^2*2$ , y
$3^2$ $3^3$
Ahora tomamos de nuevo todos estos factores 3 de $3^2$ lugares. Exactamente $Q_{3^2}(29)$=$Q_{9}(29)=3$ veces. Nos quedan sólo con
$3^1$ $3^3$
Así, los factores 3 en total de 29! son : $$ N_3(29)=Q_3(29)+Q_{3^2}(29)+Q_{3^3}(29)=9+3+1=10 $$ Para un general de la prueba consulte https://en.wikipedia.org/wiki/Legendre%27s_formula#Proof.
Después de esta pequeña explicación de la fórmula $N_r(x)$, sigamos :condición Necesaria y suficiente para que nuestra división es múltiplo de r es que : $$ N_r(p^n)-N_r(q^n)-N_r(p^n-p^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-p^n)>=1 $$ $$ \sum_{k=1}^{\infty} {Q_{r^k}(p^n)-Q_{r^k}(q^n)-Q_{r^k}(p^n-p^n)}>= Q_{r}. (p^n)-Q_{r}(q^n)-Q_{r}. (p^n-p^n)>=1 $$ $$ \left \lfloor {p^n \sobre r} \right \rfloor - \left \lfloor {q^n \sobre r} \right \rfloor - \left \lfloor {{p^n-p^n} \over r} \right \rfloor >=1 $$ De hecho, esta función es muy similar a la anterior fórmula, añadiendo uno más del piso. Esta sume, de hecho sólo puede ser 0 o 1.
Digámoslo de esta fórmula en forma de restos : $$ r\left \lfloor {p^n \sobre r} \right \rfloor - r\left \lfloor {q^n \sobre r} \right \rfloor - r\left \lfloor {{p^n-p^n} \over r} \right \rfloor >=r $$ Agregar $-p^n+q^n+(p^n-q^n)=0$ y reordenar $$ -(p^n-r\left \lfloor {p^n \sobre r} \right \rfloor) + (p^n-r\left \lfloor {q^n \sobre r} \right \rfloor)+ ((p^n-p^n)-r\left \lfloor {{p^n-p^n} \over r} \right \rfloor)>=r $$ Definamos $R_r(x)=x \mod r=x-r\left \lfloor {x \over r} \right \rfloor$ y simplfy esta expresión : $$ -R_r(p^n)+R_r(q^n)+R_r(p^n-p^n)>=r $$ Reordenar esta : $$ R_r(q^n)+(R_r(p^n-p^n)-R_r(p^n))>=r $$ Llamamos a $R_r(q^n)+R_r(p^n-q^n)-R_r(p^n)$ principal expresión residual.
Dentro de paréntesis $(R_r(p^n-q^n)-R_r(p^n))$ tenemos forma de $R(a-b)-R(a)$. Los resultados de este sólo puede ser R(-b) o -R(b). En nuestro igualdad vamos a necesitar que el paréntesis de la expresión es mayor o igual que 0 en el fin de conseguir $R_r(-q^n)$.Tenga en cuenta que $R_r(q^n)+R_r(-q^n)=r>=r$. Continuar con esta expresión : $$ R_r(p^n-p^n)-R_r(p^n)>=0 $$ $$ R_r(p^n-p^n)>=R_r(p^n) $$ En el que caso vamos a tener una garantía de que esta desigualdad es verdadera ? En caso de que $$ R_r(p^n)=1 $$ Ahora, tenemos un punto importante : r es primo. Así que podemos aplicar el "pequeño teorema de Fermat" (https://en.wikipedia.org/wiki/Fermat%27s_little_theorem). Si $$ n=r-1 $$ Pero sólo en este caso, siempre ocurrirá que también se $R_r(q^n)=R_r(p^n)=1$ por una misma razón y, a continuación, en la principal expresión obtenemos : $$ R_r(q^n)+R_r(p^n-p^n)-R_r(p^n)=1+R_r(p^n-p^n)-1=R_r(p^n-p^n)<r $$ cuando n=r-1.
Más fácil es trabajar con la siguiente (resumido) condición : $$ R_r(q^n)-R_r(p^n)>0 $$ o $$ R_r(q^n)>R_r(p^n) $$ Esta es una condición necesaria para conseguir un n para resolver principal expresión residual. Saludos. Daniel