Pruebalo $14322\mid n^{31} - n$

Question

Im tratando de probar que $ 14322 \mid n^{31} - n $, $ \forall n \in \mathbb{Z}$

Mi pensamiento era volver a escribir $n^{31} - n$ que una tiene $$ 2(n-1)\sum{i=0}^{n} i \sum{k=0}^{14} n^k \sum_{j=0}^{14} (-1)^kn^k $ $ pero esto no (en mi opinión) contribuye a mucho.

He intentado asumir que era falsa y luego tratar de obtener una contradicción.

decir que $n^{31}-n=q\cdot 14322 + r$, $0<r a="" contradicci="" evidente.="" llegar="" luego="" ninguna="" no="" q="" una="" veo="" y="">¿Consejos?

</r>

Answer 1

El método habitual para resolver este problema es el uso de Fermat Poco Teorema: $$14322=2\cdot3\cdot7\cdot11\cdot 31 $$

y demostrar que $n^{31}-n$ es divisible por cada uno de los prime en este factorización

---

Editar Como notado en el comentario que nos ha $n^{p}-1$ divide $n^{pq}-1$

• Fermat implica que $11$ divide $n^{11}-n$, y como $n^{10}-1$ divide $n^{30}-1$ $n^{11}-n$ divide $n^{31}-n$ por lo tanto $11$ divide $n^{31}-n$
• Como $n^{6}-1$ divide $n^{30}-1$ y, a continuación, $n^{7}-n$ divide $n^{31}-n$ le da la divisibilidad por $7$ y usted puede hacer lo mismo para los demás

Answer 2

Si usted no sabe aritmética modular, a continuación, puede utilizar poco de Fermat y el siguiente

$\ \ p\mid n^p\!-\!n\mid n^{31}\!-\!n\,$ $\,n^{\large \color{#c00}{p-1}}\!-\!1\mid n^{\color{#c00}{30}}\!-\!1\,$ $\,\color{#c00}{p\!-\!1\mid 30}\,$ todos los $\, p\mid 14322=2\cdot3\cdot7\cdot11\cdot 31$

De lo contrario, la dirección fácil $\,\color{#90f}{(\Leftarrow)}\,$ de la siguiente teorema se aplica.

Teorema $ $ (Korselt del Carmichael Criterio) $\ $ $\rm\:1 < e,n\in \Bbb N\:$ hemos

$$\rm \forall\, a\in\Bbb Z\!:\ n\mid a^e\!-a\ \iff\ n\ \ is\ \ squarefree,\ \ and \ \ \color{#c00}{p\!-\!1\mid e\!-\!1}\ \, for\ all \ primes\ \ p\mid n\quad $$

Prueba de $\ \ \color{#90f}{(\Leftarrow)}\ \ $ Desde un squarefree natural que divide a otro naturales iff todos sus los factores primos de hacer, sólo necesitamos mostrar $\rm\: p\mid a^e\!-\!a\:$ para cada uno de los prime $\rm\:p\mid n,\:$ o que $\rm\:a \not\equiv 0\:\Rightarrow\: a^{e-1}\equiv 1\ \ ( mod\ p),\:$, lo que, desde el $\rm\:p\!-\!1\mid e\!-1,\:$ sigue de $\rm\:a \not\equiv 0\:\Rightarrow\: \color{#c00}{a^{p-1} \equiv 1}\ \ ( mod\ p)\:$ a poco de Fermat, es decir,

$$\rm \color{#c00}{e\!-\!1 = (p\!-\!1)}k\ \Rightarrow\ a^{\large e-1} \equiv (\color{#c00}{a^{\large p-1}})^{\large k}\equiv \color{#c00}1^{\large k}\equiv 1\!\!\!\pmod p \qquad\qquad $$

---

$(\Rightarrow)\ \ $ Que $\rm\: n\mid a^e\!-\!a\:$ todos los $\rm\:a\in\Bbb Z,\:$ debemos mostrar

$$\rm (1)\ \ n\,\ is\ squarefree,\quad and\quad (2)\ \ p\mid n\:\Rightarrow\: p\!-\!1\mid e\!-\!1$$

$(1)\ \ $ Si $\rm\,n\,$ no squarefree, a continuación, $\rm\,1\neq \color{#0a0}{a^2}\!\mid n\mid \color{#0a0}{a^e}\!-\!a \Rightarrow\: a^2\mid a\:\Rightarrow\!\Leftarrow$ $\rm\: (note\ \ e>1\: \Rightarrow\: \color{#0a0}{a^2\mid a^e})$

$(2)\ \ $ Deje $\rm\ a\ $ ser un generador del grupo multiplicativo de a $\rm\:\Bbb Z/p.\:$ Por lo tanto $\rm\ a\ $ orden $\rm\:p\!-\!1.\:$ $\rm\:p\mid n\mid a\,(a^{e-1}\!-\!1)\:$ pero $\rm\:p\nmid a,\:$ $\rm\: a^{e-1}\!\equiv 1\,\ ( mod\ p),\:$ por lo tanto $\rm\:e\!-\!1\:$ debe ser divisible por $\rm\:p\!-\!1,\:$ el orden de $\rm\,\ a\,\ (mod\ p)$.

Answer 3

Una manera de resolver esto es descomponer el polinomio $n^{31}-n$ directamente, teniendo en cuenta que el $x-1\mid x^q-1$:

$$\begin{align}n^{31}-n&=n(n^{30}-1)\\ &=n(n^{10}-1)(n^{20}+n^{10}+1)\\ &=n(n^6-1)(n^{24}+n^{18}+n^{12}+n^6+1)\\ &=n(n^2-1)(n^{28}+n^{26}+\dots+1)\\ &=n(n-1)(n^{29}+n^{28}+\dots+1) \end{align}$$

Desde $14322=2\cdot3\cdot7\cdot11\cdot 31$, se puede utilizar de Fermat Poco Teorema sobre todos los valores de $2,3,7,11,31$ con los términos de $n^2-n,n^3-n,n^7-n,n^{11}-n, n^{31}-n$. Tenga en cuenta que nosotros no necesitamos de un factor de $n^5$ a cuenta de todos estos divisibilidad condiciones, ya que los $p\mid n$ es el único momento en el $n$ factor es necesaria en $n(n^{p-1}-1)$, lo que significa que cuando se $14322\mid n$, obtenemos $14322\mid n^{31}-n$ el $n$ factor, y al $(14322,n)\lt 14322$ todos los factores de $14322$ que no están presentes en $n$ aparecen en $n^{30}-1$.