Si $n$ es compuesto, entonces $n$ divide $(n-1)!$.

Question

Tengo una prueba y la necesidad de algunos comentarios. Parece muy obvio que la afirmación es verdadera, pero siempre es obvio que son un poco más difícil de demostrar. Así que agradecería cualquier comentario. Gracias!

Aquí es lo que se me pide probar:

Si $n$ es compuesto, a continuación,$(n-1)! \equiv 0 \pmod n$.

Prueba:

$n$ está compuesto $\implies n=ab$ donde$a,b \in \mathbb{Z}$$0<a,b<n$.

Caso 1: Si $a=b$$n=a^{2}$. Ahora $n \mid (n-1)! \implies a \mid (n-1)!$, por lo que $$\begin{aligned} (n-1)! &\equiv 1\times 2\times \dotsb \times a \times\dotsb\times (n-a)\times\dotsb\times (n-1) \\ &\equiv 1\times 2\times \dotsb\times a \times\dotsb\times -a\times\dotsb\times -1 \\ &\equiv 0 \pmod n \end{aligned}$$

Caso 2: $0<a<b<n$.

Entonces, desde $a \mid n$, $b \mid n$ y $n \mid (n-1)!$ tenemos que $a \mid (n-1)!$$b \mid (n-1)!$.

Por lo que esto implica $(n-1)! \equiv 1\times 2\times \dotsb\times a \times\dotsb\times b\times\dotsb\times (n-1) \equiv 0 \pmod n$, Q. E. D.

Answer 1

Si $n > 4$$n = a \cdot b$$a, b \geq 2$$a + b \leq n - 1$. Desde ${a+b \choose a}$ es un número entero de ello se sigue que $n = a \cdot b \mid a! \cdot b! \mid (a + b)! \mid (n - 1)!$.

Answer 2

Sugerencia $\rm\,\ n\, =\, \color{#C00}a\:\!\color{#0A0}b\:|\:1\!\cdot\! 2\cdots\color{#C00} a\:\color{#0A0}{(a\!+\!1)\, (a\!+\!2) \cdots (a\!+\!b)}\cdots (ab\!-\!1)\,\ $ al $\rm\,\ a\!+\!b \le ab\!-\!1$

Nota $\ $ Que $\rm\:\color{#0A0}b\:$ se divide por encima de la $\rm\color{#0A0}{green}$ plazo es que no se deduce del hecho de que es divisible por $\rm\,b!\,$ por la integralidad del coeficiente binomial $\rm\:(a\!+\!b:a),\:$ como en WimC la respuesta. Más bien, me deducir de la mucho más sencillo hecho de que cualquier secuencia de $\rm\,b\,$ enteros consecutivos contiene un múltiplo de $\rm\,b,\,$ que es una consecuencia inmediata de (Euclidiana) de la división. Para la integridad. he aquí una prueba: $$\rm\ mod\ b\!:\ a\!+\!b\equiv k\in [\color{#C00}0,\color{#0A0}{b\!-\!1}]\ \Rightarrow\ b\:|\:a\!+\!b\!-\!k\in [\color{#0A0}{a\!+\!1},\color{#C00}{a\!+\!b}]$$

Answer 3

Recordemos la definición de factorial: $$m! = \prod_{k=1}^m k = 1 \times 2 \times 3 \times \dotsb \times m.$$

A partir de esto debería ser obvio que $ab \mid m!$ cualquier $1 \le a < b \le m$, ya que tanto $a$ $b$ aparecen como términos distintos en el producto.

En particular, vamos a $n$ ser un número compuesto, y deje $m = n-1$. Si $n$ no es el cuadrado de un primo, existen dos enteros $1 < a < b < n$ tal que $n = ab$ (puede que desee probar esto — no es difícil), y por lo tanto $n \mid (n-1)!$.

Lo que si $n$ es el cuadrado de un número primo, es decir, $n = p^2$ para algunos prime $p$? Si $p = 2$, tenemos un contraejemplo: $4 \nmid 3! = 6$.

Sin embargo, si $p > 2$,$2p < p^2 = n$, así que podemos optar $a = p$ $b = 2p$ que $2n \mid (n-1)!$, y por tanto también a $n \mid (n-1)!$.

Por último, el hecho de que el resultado no se cumple para cualquier prime $n$ sigue fácilmente desde el teorema fundamental de la aritmética, como la factorización prima de $(n-1)!$ no contendrá $n$ si es primo. (Estoy seguro de que hay más débiles de los lemas que podrían ser utilizados para probar esto, pero ¿por qué molestarse? El FToA hace de forma limpia y fácil). Por lo tanto, para los números enteros $n > 1$, $n \nmid (n-1)!$ si y sólo si $n$ es el primer o $4$.

(De hecho, el resultado tiene trivialmente para $n = 1$ demasiado, al menos según la definición habitual de $0! = 1$, pero que no se sigue el argumento anterior — $1$ no está compuesto, en el sentido necesario para el argumento.)

Answer 4

Vamos a suponer que $n>4$, ya que el $4\hspace{-3pt}\not|\,3!$.

Deje $p$ ser el más pequeño factor de $n$. Desde $n$ es compuesto, $p\le\sqrt{n}$.

Si $p=\sqrt{n}$, entonces a partir de la $n>4$, debemos tener $p>2$, de modo que $2p<p^2=n$. Por lo tanto, $p\le n-1$$2p\le n-1$, y por lo tanto, $2n=p\cdot2p\,|\,(n-1)!$

Si $p<\sqrt{n}$,$n/p>\sqrt{n}$. Por lo tanto, $p\le n-1$$n/p\le n-1$, y por lo tanto, $n=p\cdot n/p\,|\,(n-1)!$

En cualquier caso, $n|(n-1)!$

Answer 5

Desde $n|(n-1)!$ $(n-1)!\equiv0\pmod n$ son equivalentes, si usted puede probar uno, usted debe ser hecho.

Tomar su caso 2, por ejemplo. Usted dice "entonces a partir de la $a|n,b|n$, e $n|(n-1)!$..." Pero $n|(n-1)!$ es lo que se dispuso a probar y no te explícito acerca de por qué es verdad, que es el punto de prueba en el primer lugar.

Lo que yo creo que se es que $(n-1)!$ es el producto de todos los enteros positivos $\le n-1$, que incluye a $a$$b$. Cambiar el orden de la multiplicación y deje que el producto de todos los enteros $\le n-1$ excluyendo $a$ $b$ ser igual a una nueva constante $k$. Por lo $(n-1)!=kab=kn$. Por lo tanto, $n|(n-1)!$ o $(n-1)!\equiv0\pmod n$.

Caso 1 fue un poco más explícito, pero se trató de usar su conclusión para tratar de probar algo nuevo. Y te perdiste la brecha que Jonas comentario de puntos. Es posible que desee ser un poco más explícito acerca de por qué el producto es cero, así en lugar de simplemente afirmar que es.