Prueba de la primacía $p$ divide $\binom{p}{k}$ para $k\in\{1,\ldots,p-1\}$

Question

Demuestre si $p$ es un primo, entonces $p \mid \binom pk$ para $k\in\{1,\ldots,p-1\}$

Realmente no sé por dónde empezar con esto.

Puedo ver que tengo que usar el hecho de que $p$ es primo en alguna parte - no ocurre lo mismo con los números compuestos, por ejemplo $4\nmid 6=\binom42$ .

He comprobado que esto es cierto para los primeros primos:

• $3$ divide $\binom 31=\binom32=3$
• $5$ divide ambos $\binom 51=\binom 54=5$ y $\binom 52=\binom 53=10$
• $7$ divide $\binom71=\binom76=7$ , $\binom72=\binom75=21$ y $\binom73=\binom74=35$ .

Answer 1

$\binom{p}{k} = \frac{p!}{k!(p-k)!} = \frac{p(p-1)...(p-k+1)}{k!}$

desde $\binom{p}{k}$ es un número entero, y ninguno de los miembros de $k!$ puede dividir a p ( ya que es un primo), entonces $p|\binom{p}{k}$

Answer 2

Hay una forma muy bonita de expresar esto, que debería introducirte en una notación que realmente deberías conocer.

Definamos la función $v_p:\mathbb{Z}\to\mathbb{N}\cup\{\infty\}$ definiendo $v_p(x)$ para ser el más alto $i$ tal que $p^i$ divide $x$ (donde tomamos $v_p(0)=\infty$ ). Extendamos entonces $v_p$ a un mapa $v_p:\mathbb{Q}\to\mathbb{Z}$ al establecer $v_p\left(\frac{a}{b}\right)=v_p(a)-v_p(b)$ . Se puede comprobar rápidamente que $v_p$ disfruta de la siguiente agradable propiedad:

$$v_p(xy)=v_p(x)+v_p(y)\quad\mathbf{(1)}$$

Además, vemos por mera definición, que $p\mid x$ para $x\in\mathbb{Z}$ si y sólo si $v_p(x)>0$ . Ahora bien, hay que tener en cuenta que por $\mathbf{(1)}$ tenemos que

$$\displaystyle \begin{aligned}v_p\left({p\choose k}\right) &= v_p\left(\frac{p!}{k!(p-k)!}\right)\\ &= v_p(p!)-v_p(k!)-v_p((p-k)!)\end{aligned}\quad\mathbf{(2)}$$

Pero, como $\ell!=1\cdots \ell$ podemos utilizar $\mathbf{(1)}$ de nuevo para deducir que para cada $\ell\in\mathbb{N}$ uno tiene que

$$v_p(\ell!)=\sum_{j=1}^{\ell}v_p(j)$$

Ahora, si $j<p$ entonces evidentemente $p\nmid j$ para que $v_p(j)=0$ . Así,

$$v_p(k!)=\sum_{j=1}^{k}v_p(j)=\sum_{j=1}^{k}0=0$$

y

$$v_p((p-k)!)=\sum_{j=1}^{p-k}v_p(j)=\sum_{j=1}^{p-k}0=0$$

Pero

$$v_p(p!)=\sum_{j=1}^{p}v_p(j)=\sum_{j=1}^{p-1}v_p(j)+v_p(p)=\sum_{j=1}^{p-1}0+1=1$$

Así, utilizando $\mathbf{(2)}$ podemos concluir que

$$v_p\left({p\choose k}\right)=1-0-0=1$$

y por lo tanto $\displaystyle p\mid {p\choose k}$ y además $p$ es la mayor potencia de $p$ dividiendo ${p\choose k}$ .

Answer 3

Por definición, $\binom{p}{k}$ puede ampliarse de la siguiente manera:
$\binom{p}{k}$ = $\frac{p!}{k!(p - k)!}$

Desde $\binom{p}{k}$ es un número entero positivo por definición, denotémoslo como $n$ , $n \in \mathbb N$ .
$n$ = $\frac{p!}{k!(p - k)!}$

Ahora, mueve el denominador al lado izquierdo:
$n$ $\cdot$ $k!(p - k)!$ = $p!$

$p!$ es obviamente divisible por $p$ .
Por lo tanto, $n$ $\cdot$ $k!(p - k)!$ también es divisible por $p$ . Por lo tanto, al menos un factor debe ser divisible por $p$ :

1. $k!$ no es divisible por $p$ porque $k < p$ y $p$ es primo.
2. $(p - k)!$ no es divisible por $p$ porque $(p - k) < p$ y $p$ es primo.

De eso, $p \mid n \Rightarrow p \mid \binom{p}{k}$

Answer 4

Dejar $a = (p-1)!$ y $b = k!(p-k)!$ entonces $\binom pk = p*(a/b)$ así que $b*\binom pk = p*a$ . Por lo tanto $p\mid b*\binom pk$ y $p$ no divide $b$ ya que es un producto de números naturales cada uno de los cuales es menor que $p$ . por lo tanto, ya que $p$ es primo $p\mid \binom pk$ .

Answer 5

Con un poco de teoría de grupos, se puede prescindir de la factorización en primos.

Dejemos que $X=\{0,1,\ldots,p-1\}$ y que $f:X\to X$ sea la operación de desplazamiento $x\mapsto (x+1)\bmod p$ . Claramente $f^p$ es la identidad en $~X$ . Esta función también proporciona una operación $\overline f:\mathcal P(X)\to\mathcal P(X)$ de la colección $\mathcal P(X)$ de $2^p$ subconjuntos de $X$ a sí mismo: $\overline f:S\mapsto\{\,f(x)\mid x\in S\,\}$ .

La parte de la teoría de grupos es que repitiendo $\overline f$ o bien da una órbita de tamaño $1$ o de tamaño $~p$ para un determinado $S$ o bien $\overline f(S)=S$ o bien el $p$ subconjuntos $S,\overline f(S),\overline f{}^2(S),\ldots,\overline f{}^{p-1}(S)$ son todos diferentes. De manera menos formal: girar un collar de $p$ cuentas de colores por pasos unitarios o bien da una sola coloración (para un collar monocromático) o bien $p$ diferentes coloraciones. También se ve que $\overline f(S)=S$ sólo se produce cuando $S=\emptyset$ o $S=X$ .

El subconjunto $\overline f(S)$ de $X$ siempre tiene el mismo tamaño que $S$ . Por lo tanto, la iteración $\overline f$ divide la $\binom pk$ subconjuntos de tamaño $~k$ en órbitas de tamaño $~p$ , siempre y cuando $k\notin\{0,p\}$ para excluir los puntos fijos $\emptyset$ y $~X$ . Esto demuestra $p\mid\binom pk$ .

También se puede demostrar la propiedad orbital sin teoría de grupos. Supongamos algún par entre los subconjuntos $S,\overline f(S),\overline f{}^2(S),\ldots,\overline f{}^{p-1}(S)$ coinciden: $\overline f{}^k(S)=\overline f{}^l(S)$ para $0\leq k<l<p$ . Entonces, porque $\overline f$ es invertible hay que tener $\overline f{}^{l-k}(S)=S$ ; poniendo $d=l-k$ e iterando se obtiene que también $\overline f\,{}^{nd}(S)=S$ para $n=1,2,3,\ldots$ . Desde $d$ no divide $~p$ y los exponentes $nd$ puede reducirse en módulo $~p$ (como $\overline f\,{}^p$ es la identidad), una de esas potencias se reduce a $1$ por lo que se concluye que $\overline f(S)=S$ .