Demostrando que $n\mid(nCr)$ para todos $r$ ( $1 \leq r \leq n-1$ ), sólo si $n$ es primo

Question

Estoy tratando de demostrar que $n\mid(nCr)$ para todos $r$ ( $1 \leq r \leq n-1$ ) si y sólo si $n$ es primo.

Demostrando ahora que si $n$ es primo, entonces $n\mid(nCr)$ es bastante fácil, pero ¿cómo probar que $n\mid(nCr)$ sólo si $n$ ¿es primo?

¿Podría demostrar que si $n$ no es primo, entonces existe un $r$ tal que $n$ no divide $nCr$ ? En caso afirmativo, ¿cómo lo haría? Pensé que sería fácil, pero luego me di cuenta de que para algunos $r, n\mid(nCr)$ aunque $n$ no es de primera, lo que complica un poco las cosas.

He conseguido demostrar que $n\mid(n-1)!$ para no primos mayores o iguales que $6$ lo que significa que a pesar de $n$ siempre se cancela con un producto de factores en $r!(n-r)!$ en algunos casos, habrá otro par de factores que se anulen con el $n$ en $(n-1)!$ y a veces no. Tal vez hay algún tipo de patrón, pero no puedo encontrar por desgracia.

(Preferiría un método que no utilice matemáticas de nivel universitario o superior)

Answer 1

Supongamos en primer lugar que $n$ no es una potencia de un primo. Sea $p$ sea un factor primo de $n$ y que $p^k$ sea su mayor potencia dividiendo $n$ es decir $p^k\mid n$ , $p^{k+1}\nmid n$ . Entonces se deduce del teorema de Lucas que $$ p\nmid{n\choose p^k}, $$ En otras palabras $r=p^k$ es el ejemplo que pedías.

Supongamos entonces que $n=p^k$ para algún primo $p$ y enteros $k>1$ . Entonces no es difícil demostrar que $$ p^2\nmid{n\choose p^{k-1}}. $$ Esto resuelve el caso de la primera potencia.

Answer 2

Supongamos que n no es primo y que $n=mp$ donde $p$ es un primo. Entonces $n\not|\binom{n}{p}$ ya que $$\binom{n}{p}=n \bigg[\frac{(n-1)!}{p!(n-p)!}\bigg]=n\bigg[\frac{(mp-1)!}{p!((m-1)p)!}\bigg]=n\bigg[\frac{(mp-1)(mp-2)(mp-3)\cdots((m-1)p+1)}{p!}\bigg],$$ donde la expresión entre paréntesis no es un número entero ya que $(mp-1)(mp-2)(mp-3)\cdots((m-1)p+1)$ no es divisible por $p$ mientras que $p!$ es.

Answer 3

Tenemos que demostrar que n|ncr. ahora, $nCr=n \cdot(n-1)\cdot(n-2)\cdot(n-3)....\cfrac{n+r-1}{r!}$ Puesto que n es primo y $n \gt r$ entonces no hay factores de $r!$ dividir $n$ . así $n$ no se cancela. Así que n debe dividir a ncr cuando n es primo.

Answer 4

Me sorprende que la gente publique pruebas complejas de un teorema que es fácilmente demostrable con matemáticas de bachillerato. He aquí un ejemplo.

"si n es primo entonces n(nCr) es bastante fácil". correcto, así que nos saltaremos esta. Sólo probaremos la segunda parte, es decir, si n es compuesto, entonces $ n \nmid nCr $ para ciertas "r".

De hecho, esas r son todos los factores primos de n.

Sea r = p donde p es un factor primo de n. entonces n = mp donde m es algún int.

$ nCp = \frac {n(n-1)(n-2)..(n-p+1)}{p(p-1)(p-2)...1} = (\frac {n}{p}) \frac{(n-1).(n-2)...(n-p+1)}{(p-1)(p-2)..1} = (\frac{n}{p}) (n-1)C(p-1) $

desde $ (n-1)C(p-1) $ es un coeficiente binomial por derecho propio, tiene que ser un número entero. Llamémoslo i.

así que $ nCp = \frac{n.i}{p} $

Ahora aquí está la observación más importante de esta prueba. i se forma dividiendo un cierto numerador por un cierto denominador. El numerador es un producto de los términos de (n-1) a (n-p+1). Ninguno de estos términos es divisible por p. ¿Por qué? porque como n es divisible por un primo p, el siguiente entero más pequeño que puede dividirse por p sólo puede ser n-p. Todos los términos del numerador caen entre n y n-p excluyendo los límites, por lo que ninguno de ellos es divisible por p, y tampoco lo es su producto. Por tanto, llamaremos a i "libre de p".

Dado que i no puede dividirse por p, para $nCp$ para ser un int, n tiene que estar dividido por p. Ya que n/p = m, $ nCp = \frac{n.i}{p} = m.i$

Ahora para que n se divida $nCp$ , $m.p$ tiene que dividir $m.i$ . Esto da lugar a dos opciones.

1. m del numerador se divide por m del denominador, e i del numerador se divide por p del denominador.
2. m del numerador se divide por p del denominador, e i del numerador se divide por m del denominador.

La opción 1 es imposible, porque requiere que i se divida por p, y sabemos que i es "libre de p".

La opción 2 da lugar a dos subopciones. O bien m contiene un factor p, o bien no lo contiene. Si no tiene un factor p, entonces claramente $ p \nmid m$ . Y si tiene un factor p, entonces $ m \nmid i $ . (recuerda, i es libre de p). Así que la opción 2 también es una imposibilidad.