Prueba: si $p$ es primo, y $0<k<p$ $p$ divide $\binom pk$

Question

Pregunta : Si $p$ es primo, y $0< k< p$ muestran que $ p \mid {p \choose k}$

${p \choose k}$ puede ser reescrita como:

$${p(p-1)(p-2)\dots(p-(k-1))(p-k)! \over (p-k)!\cdot k(k-1)(k-2)\dots3\cdot2\cdot1}$$

Ahora el $(p-k)!$ cancela. Ya que en el numerador tenemos k números enteros consecutivos, k divide a uno de ellos (no p como p es primo y $k <p$). Entonces k-1 divide a otro uno o dos términos en el k términos consecutivos (de nuevo, no p). Este razonamiento continúa hasta que 3 y 2.

Esto significa que ${p \choose k}$ puede ser reescrita como pq lo que implica $p | {p \choose k}$

Lo que si alguno de esta prueba es incorrecta. Estoy preocupado acerca de cualquier "se superpone', es decir, decir k-6 divide a los términos k-3 divide a invalidar el argumento.

P. S. espero que el de arriba es legible como soy nuevo en este sitio. Gracias!

Answer 1

Tenemos $${p\choose k}=\frac{p}{k}{{p-1}\choose {k-1}}$$ y desde $(p,k)=1$,$p|{p\choose k}$.

Answer 2

Voy a tratar de darle una divertida prueba. Tome $k$ tal que $0 < k < p$. El grupo $\mathbf{F}_p = \mathbf{Z}/p\mathbf{Z}$ actúa sobre el conjunto de $X$ de los subconjuntos de a $\mathbf{F}_p$ de cardenal $k$, es decir, por $Y\in X\mapsto Y+\alpha :=\{ y+\alpha \; | \; y \textrm{ in } Y \} \in X$ por cada $\alpha\in \mathbf{F}_p$. (Como la traducción son bijective, conservan el cardenal, de modo que los conjuntos de cardinal $k$ son de hecho enviados a los conjuntos de cardinal $k$.) Esta acción induce una partición de $X$ en órbitas, y un conocido de primaria grupo de resultados de la teoría asegura que cada órbita tiene un cardenal dividiendo el cardenal del grupo $\mathbf{F}_p$, es decir, dividiendo $p$. Como $p$ es primo, cada órbita debe tener un cardenal igual a $1$ o $p$. Ahora, imagine que hay una órbita de cardenal $1$. Esto significa que hay un subconjunto $J$ (del cardenal $k$) $\mathbf{F}_p$ que es estable por toda traducción por elementos de la $\alpha \in\mathbf{F}_p$ y $k > 0$, $J$ no está vacía, así que vamos a $x$ estar en ella. A continuación, $1 = x + \underbrace{(1-x)}_{:=\alpha\in\mathbf{F}_p}$ está en él. Como $1$ genera el aditivo grupo $\mathbf{F}_p$, podemos ver que $J$ contiene, de hecho, toda la $\mathbf{F}_p$, violando así la hipótesis de $k < p$. Por lo tanto, no hay ninguna órbita del cardenal $1$, y por la observación anterior, todas las órbitas debe tener el cardenal $p$. Como $X$ es distinto de la unión de las órbitas, el cardenal de $X$ es simplemente igual a $np$ donde $n$ es el número de disctinct órbitas. Pero ¿cuál es el cardinal de a $X$ ? Recuerde, $X$ es el conjunto de subconjuntos de a $\mathbf{F}_p$ (que es un conjunto cardenal $p$) que han cardenal $k$. Por lo que el cardenal de $X$${p \choose k}$, el cual es divisible por $p$. $\square$

Answer 3

Escrito explícitamente $\frac{p!}{k!(p-k)!}$ no es un múltiplo único de $p$ en el numerador. Pero este es un número entero, por lo que es un múltiplo de a $p$.

---

Su argumento no puede ser falsa, lo que significa que no se superponen. Trataré de ser más explícito:

$$\binom{p}{k}=\frac{p\cdot (p-1) \cdots (p-k+1)}{k \cdot (k-1) \cdots 1}$$

Todos hemos acordado ya que, si este es un entero, entonces este es un múltiplo de a $p$. La pregunta puede ser reformulada: ¿por $\binom{p}{k}$ tiene que ser un número entero?

Motivación 1 (combinatoria interpretación, en primer lugar, se puede ver como una trampa respuesta, pero esta no lo es): $\binom{p}{k}$ es el número de formas de elegir los $k$ objetos en $p$ objetos idénticos.

Motivación 2: sería suficiente para demostrar que si $q^\alpha$ divide exactamente el denominador (para algunos prime $q \le k < p$ $q^\alpha$ divide también el numerador. Cómo mostrar? Algebraicamente, el número de factores de $q$ que se divide $n!$ es exactamente $$\sum_{i \ge 1}\left\lfloor \frac{n}{q^i}\right\rfloor.$$ Esto es comúnmente conocido como Polignac la fórmula. Por lo tanto, tenemos que mostrar, equivalentemente, que para cada uno de los prime $q<p$ hemos $$\sum_{i \ge 1}\left\lfloor\frac{p}{q^i}\right\rfloor \ge \sum_{i \ge 1}\left\lfloor \frac{p-k}{q^i}\right\rfloor+\sum_{i \ge 1}\left\lfloor \frac{k}{q^i}\right\rfloor.$$ Pero esto es inmediato, ya que para cada uno positivo $x,y$ tenemos $\lfloor x+y\rfloor \ge \lfloor x\rfloor +\lfloor y\rfloor$. El reclamo sigue sumando más de $i$.

---

De manera más general, este argumento puede ser modificada para todos fuertemente divisible secuencia, es decir, secuencias de $(a_n)_{n \in \mathbf{N}}$ tal que $\text{gcd}(a_n,a_m)=a_{\text{gcd}(n,m)}$. [Por ejemplo, funciona para los números de Fibonacci].

Answer 4

Kummer del Teorema, una prueba de que se da en esta respuesta, dice que el número de factores de $p$ $\binom{n}{k}$ es el número de la base-$p$ lleva al agregar $k$$n-k$. Cuando la adición de $k$ $p-k$ base$p$, obtenemos un si $0\lt k\lt p$. Por lo tanto, no es exactamente un factor de $p$$\binom{p}{k}$$0\lt k\lt p$.

Si aplicamos la fórmula de $(1)$,$\sigma_p(k)=k$$\sigma_p(p-k)=p-k$$\sigma_p(p)=1$, podemos obtener el número de lleva a ser $$ \frac{\sigma_p(k)+\sigma_p(p-k)-\sigma_p(p)}{p-1}=\frac{k+(p-k)-1}{p-1}=1 $$

Answer 5

Lucas teorema dice $\displaystyle \binom n k \equiv \binom {\left \lfloor {n / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {n \bmod p} {k \bmod p} \pmod p$, vamos a $p=n$, entonces tenemos $$\displaystyle \binom p k \equiv \binom {\left \lfloor {p / p} \right \rfloor} {\left \lfloor {k / p} \right \rfloor} \binom {p \bmod p} {k \bmod p} \pmod p$$ and $p\equiv0\pmod p$ , if $0 < k < p$ we have $k \bmod p \ne 0$ but $$\displaystyle \binom {p \bmod p} {k \bmod p} = \binom 0 {k \bmod p} = 0$$ a partir de la cual el resultado se deriva