¿Cómo puedo demostrar que $n^7 - n$ es divisible por $42$ para cualquier número entero $n$ ?

Question

Puedo ver que esto funciona para cualquier número entero $n$ pero no puedo entender por qué esto funciona, o por qué el número $42$ tiene esta propiedad.

Answer 1

Problemas como éste aparecen con frecuencia aquí. Hay un par de enfoques estándar. Uno es utilizar El pequeño teorema de Fermat que dice que si $p$ es un número primo, entonces $n^p-n$ es divisible por $p$ para todos $n$ .

Desde $42=2\times 3\times 7$ lo que tenemos que hacer es comprobar que 2, 3 y 7 se dividen $n^7-n$ No importa lo que suceda. $n$ es.

Que el 7 lo haga se desprende directamente del pequeño teorema de Fermat.

El teorema también asegura que 3 divide a $n^3-n$ . Ahora: $$n^7-n=n(n^6-1)=n((n^2)^3-1)=n(n^2-1)(n^4+n^2+1)=(n^3-n)(n^4+n^2+1),$$ por lo que 3 divide efectivamente $n^7-n$ .

Finalmente, $n$ y $n^7$ siempre tienen la misma paridad, por lo que $n^7-n$ está en paz.

---

En realidad podemos argumentar sin el pequeño teorema de Fermat en este caso. Un enfoque que sólo requiere paciencia es el siguiente: Se trata de factorizar el polinomio $x^7-x$ y luego analizar el resultado cuando $x=n$ es un número entero. (Este es un truco que Bill Dubuque sugiere a veces en sus soluciones).

Lo tenemos: $x^7-x=x(x^6-1)=x(x^3+1)(x^3-1)=x(x+1)(x^2-x+1)(x-1)(x^2+x+1)$ . Cuando $x=n$ tenemos $$ n^7-n=(n-1)n(n+1)(n^2-n+1)(n^2+n+1). $$ Ahora analizamos esto primo por primo, como antes. Obsérvese que uno de los $n$ y $n-1$ es siempre par, por lo que el producto es par. Además, de 3 números consecutivos, como $n-1,n,n+1$ , uno es siempre divisible por 3, por lo que sólo queda verificar la divisibilidad por 7.

Podemos suponer que $n=7k+b$ donde $b=\pm2$ o $\pm3$ ya que de lo contrario $(n-1)n(n+1)$ es un múltiplo de 7. En ese caso, $n^2\equiv 4$ o $2\pmod 7$ y una de $n^2+n$ , $n^2-n$ es $\equiv 6\pmod 7$ Así que $(n^2-n+1)(n^2+n+1)$ es un múltiplo de 7.

La desventaja de este enfoque sobre el anterior, por supuesto, es la necesidad de analizar diferentes casos. El pequeño teorema de Fermat nos permite analizar todos los casos simultáneamente, lo que típicamente (como aquí) resulta en un enfoque mucho más rápido.

---

Si te sientes cómodo con el método de la inducción, esto nos da una forma de verificar la divisibilidad por 7 que no está exenta de cierta elegancia (la divisibilidad por 2 y 3 probablemente se aborda mejor como antes). Nótese que $(-n)^7-(-n)=-(n^7-n)$ por lo que también podemos suponer que $n\ge 0$ . Si $n=0$ es obvio que 7 divide $n^7-n$ .

Supongamos entonces que $7|n^7-n$ y argumentar que $7|(n+1)^7-(n+1)$ . Para ello, en realidad ampliar $(n+1)^7$ utilizando el teorema del binomio: $$ (n+1)^7=n^7+7n^6+{7\choose 2}n^5+{7\choose 3}n^4+\dots+1.$$ La cuestión es que $${7\choose k}=\frac{7!}{k!(7-k)!}$$ es obviamente divisible por 7 siempre que $k\ne0,7$ por lo que (módulo 7) tenemos que $(n+1)^7-(n+1)\equiv (n^7+1)-(n+1)=(n^7-n)$ . Ahora invocamos la hipótesis de inducción, que precisamente dice que este último es divisible por 7, y ya está.

Por supuesto, exactamente el mismo argumento inductivo nos da una prueba del pequeño teorema de Fermat: $p|n^p-n$ para cualquier $p$ primo y un número entero cualquiera $n$ .

Answer 2

Es un caso especial de la siguiente forma global del pequeño Fermat. $ $ Para $\rm\, a,k,n\in\mathbb N$ con $\rm\ a,k > 1$

$\rm\qquad d\ |\ n^k\! -\! n\ $ para todos $\rm\:n\:$ $\rm \iff\ d\:$ es libre de cuadrados, y $\rm\ p\!-\!1\ |\ k\!-\!1\ $ para todos los primos $\rm\:p\:|\:d$

Así que para $\rm\: a = 42 = 2\cdot 3\cdot 7\ $ deducimos: $\rm\ \ 42\ |\ n^k\!-n\ $ para todos $\rm\,n\! \iff\! 6\ |\ k\!-\!1,\,$ Por ejemplo $\rm\,k\!=\!7$ .

Para la prueba sencilla y la discusión posterior, véase El criterio de Korselt para los números de Carmichael (aquí sólo necesitamos la dirección fácil $(\Leftarrow))$ o ver mi 2009/04/10 sci.math post .

---

Esta es otra variación útil:

Teorema $\ $ Supongamos que $\ m\in \mathbb N\ $ tiene la factorización primaria $\:m = p_1^{e_{1}}\cdots\:p_k^{e_k}\ $ y supongamos que para todo $\,i,\,$ $\ \color{#0a0}{e_i\le e}\ $ y $\ \phi(p_i^{e_{i}})\mid f.\ $ Entonces $\ m\mid \color{#0a0}{a^e}(a^f-1)\ $ para todos $\: a\in \mathbb Z.$

Para $\,m = 2\cdot 3\cdot 7\,$ tenemos $\,e_i=1,\,$ $\,\phi(p_i^{e_i}) = 1,2,6\mid f\!=\!6,\,$ así que $\,m\mid a(a^6-1)$ para todos $\,a\in \Bbb Z$

Puede encontrar muchos ejemplos esclarecedores en otras preguntas aquí, por ejemplo, a continuación

$\qquad\qquad\quad$ $24\mid a^3(a^2-1)$

$\qquad\qquad\quad$ $40\mid a^3(a^4-1)$

$\qquad\qquad\quad$ $88\mid a^5(a^{20}\!-1)$

$\qquad\qquad\quad$ $6p\mid a\,b^p - b\,a^p$

Answer 3

Enfoque polinómico combinatorio

Desde $$ \begin{align} n^7-n &=5040\binom{n}{7}+15120\binom{n}{6}+16800\binom{n}{5}+8400\binom{n}{4}+1806\binom{n}{3}+126\binom{n}{2}\\ &=42\left[120\binom{n}{7}+360\binom{n}{6}+400\binom{n}{5}+200\binom{n}{4}+43\binom{n}{3}+3\binom{n}{2}\right] \end{align} $$ Por lo tanto, tenemos que para todo $n\in\mathbb{Z}$ , $$ 42\mid n^7-n $$

---

Enfoque del pequeño Fermat

El pequeño teorema de Fermat dice $$ n^7\equiv n\pmod7 $$ y como $7\equiv1\pmod2$ $$ n^7\equiv n\pmod3 $$ y como $7\equiv2\pmod1$ $$ n^7\equiv n\pmod2 $$ Así, $$ n^7\equiv n\pmod{42} $$

Answer 4

Hay muchas formas equivalentes de demostrarlo.

Primero observe que $42$ divide un número si $2,3$ y $7$ divide el número.

(Ya que $42 = 2 \times 3 \times 7$ y $\gcd(2,3) = \gcd(3,7) = \gcd(2,7) = 1$ )

Divisibilidad por $2$ :

Claramente, $2|(n^7-n)$ desde $n^7$ y $n$ son de la misma paridad.

De forma equivalente, se podría argumentar que $2|(n^2-n)$ directamente del pequeño Teorema de Fermat. (Esto es una exageración del Pequeño Teorema de Fermat).

Divisibilidad por $3$ :

$n^7-n = n(n^6-1) = n(n^2-1)(n^4+n^2+1)=n(n+1)(n-1)(n^4+n^2+1)$ .

$3|n$ o $3|(n-1)$ o $3|(n+1)$ y por lo tanto $3|(n^7-n)$ .

De forma equivalente, se podría argumentar que $3|(n^3-n)$ directamente del pequeño Teorema de Fermat.

Divisibilidad por $7$ :

Tenga en cuenta que $n$ puede ser $7k$ o $7k \pm 1$ o $7k \pm 2$ o $7k \pm 3$ .

Si $n=7k$ o $n=7k \pm 1$ Desde entonces, hemos terminado de nuevo. $7|n$ o $7|(n+1)$ o $7|(n-1)$ y por lo tanto $7|(n^7-n)$ .

Si $n=7k \pm 2$ entonces $n^2 = (7k \pm 2)^2 = 7m + 4$ y $n^4 = (7m+4)^2 = 7l+2$ . Por lo tanto, $n^4 + n^2 + 1 = 7l+2 + 7m + 4 + 1 = 7(l+m+1)$ y por lo tanto $7|(n^4 + n^2 + 1) \Rightarrow 7|(n^7-n)$ .

Si $n=7k \pm 3$ entonces $n^2 = (7k \pm 3)^2 = 7m + 2$ y $n^4 = (7m+2)^2 = 7l+4$ . Por lo tanto, $n^4 + n^2 + 1 = 7l+4 + 7m + 2 + 1 = 7(l+m+1)$ y por lo tanto $7|(n^4 + n^2 + 1) \Rightarrow 7|(n^7-n)$ .

Por lo tanto, $7|(n^7-n)$ .

De forma equivalente, se podría argumentar que $7|(n^7-n)$ directamente del pequeño Teorema de Fermat.

Por lo tanto, tenemos que $2|(n^7-n)$ y $3|(n^7-n)$ y $7|(n^7-n)$ , $\forall n \in \mathbb{N}$ .

Por lo tanto, $42|(n^7-n)$ , $\forall n \in \mathbb{N}$ .

Answer 5

Como $42=2.3.7$ . Por lo tanto, tenemos que comprobar que $n^7-n$ es divisible por $2,3$ y 7. Para la divisibilidad por $2$ por el pequeño teorema de Fermat, $n^2=n\pmod 2 \implies {(n^2)}^3.n=n^4\pmod 2=n^2\pmod 2=n\pmod 2 \implies n^7-n=0\pmod2$ . Para la divisibilidad por 3, $n^3=n\pmod 3\implies n^7=n^3\pmod 3=n\pmod 3 \implies n^7-n=0\pmod 3$ . Para la divisibilidad por 7, $n^7=n\pmod 7 \implies n^7-n=0\pmod 7$ . Estas relaciones implican que $42|(n^7-n)$ .