divide

Question

Es muy fácil probar$p\mid n^p-n$ para p = 3,5,7, falla para p = 9 porque $$ (n +1) ^ 9- (n +1) = n ^ 9 +9n ^ 8 +36n ^ 7 +84n ^ 6 +126n ^ 5 +126n ^ 4 +84 n ^ 3 +36n ^ 2 +8n $$ y$84= 2²\times 3\times7$. ¿Es cierto para cualquier$p$ prime? He verificado muchos números primos, pero no tengo idea para el caso general.

Answer 1

Sí. Esto se conoce como el pequeño teorema de Fermat. Esto dice$$a^p \equiv a \mod p$ $

Esto da$a^p-a \equiv 0 \mod p$, o$p \mid a^p-a$.

---

Hay una generalización conocida como el teorema de Euler-Fermat. Esto dice$$a^{\varphi(m)} \equiv 1 \mod m$ $

iff$\gcd(a,m)=1$. Porque tenemos

ps

iff$\varphi(9)=6$.

Answer 2

En primer lugar, bien hecho, si usted ha descubierto por ti mismo. De hecho, el resultado es cierto para cualquier prime, y es conocido, en la forma $n^{p-1}\equiv 1 \bmod p$ (donde $n$ no es un múltiplo de a $p$), como de Fermat poco teorema. Es un gran resultado.

Usted puede ser que desee pensar de probarlo usted mismo. En lo que sigue, a menos que se indique lo contrario o evidente, las cifras no son divisibles por $p$ y congruencias se toman modulo $p$.

En primer lugar, supongamos $a$ $b$ no son equivalentes modulo $p$, a continuación muestran que la $na$ $nb$ no son equivalentes.

Entonces deducir que los números de $n, 2n, 3n \dots (p-1)n$ son distintos modulo $p$, y por lo tanto equivalente a los números $1,2,3\dots p-1$ en un cierto orden.

Ahora a ver qué pasa si se multiplica el primer set, y compararlo con lo que se obtiene al multiplicar el segundo set.

Este teorema está relacionado con todo tipo de otras cosas interesantes, y también se podría tratar de la prueba demostrando que el coeficiente binomial $\binom pr$ es divisible por $p$$1\le r \lt p$. Cómo ir de allí, voy a dejar que descubrir por ti mismo, si puedes.

Answer 3

Voy a ofrecer el estándar de la prueba de Fermat poco teorema de la inducción en $n$.

Deje $P(n)$ denotar la declaración de $p\mid n^p-n$.

Claramente $p\mid 0^p-0$ para cualquier prime $p$, lo $P(0)$ mantiene.

Suponga $P(k)$ es cierto para algunos $k\in\mathbb Z_{\ge 0}$. Entonces por el teorema del Binomio:

$$(k+1)^p-(k+1)=k^p-k+\binom{p}{p-1}k^{p-1}+\binom{p}{p-2}k^{p-2}+\cdots+\binom{p}{1}k,$$

que es divisible por $p$ porque $p\mid \binom{p}{k}=\frac{p!}{(p-k)!k!}$ para cualquier $1\le k\le p-1$. $P(k+1)$ tiene demasiado.

Por otro clásico de la prueba de ver la Marca de Bennet respuesta. La sugerencia al final de su respuesta, las sugerencias de arriba, a la inducción de la prueba.

Answer 4

Sí, esto es sólo para los números primos, como otros han dicho. Una muy fáciles de prueba se encuentra utilizando la teoría de grupo si usted está familiarizado con él en absoluto.

Suponga $p$ es primo. A continuación, considere el grupo $U(p)$, el grupo multiplicativo de los números enteros $x\leq p$ tal que $\gcd(x,p)=1$. Este grupo tiene orden de $\varphi(p)=p-1$ donde $\varphi$ es de Euler del Phi de la función. Ahora considere el $a\in U(p)$. Porque el orden de un elemento que divide al orden del grupo, tenemos

$$a^{p-1}=a^{\varphi(p)}=a^{|U(p)|}=1$$

Todo esto está dentro del grupo de $U(p)$, sin embargo esto no implica

$$a^{p-1}\equiv 1\pmod p$$

o, equivalentemente,

$$p\:|\:a^{p-1}-1$$

por lo tanto,

$$p\:|\:a\left(a^{p-1}-1\right)=a^p-a$$

QED

Answer 5

Deje$K=\Bbb Z/p\Bbb Z$ con$p$ prime. Entonces$K$ es un campo y$(K^*,\times)$ es un grupo multiplicativo con$p-1$ elementos. En particular (según el teorema de Lagrange) el orden de cada elemento de este grupo divide$p-1$. Luego, para todo$x$ en$K$; $x^{p-1}=1$, por lo que$x^p=x$ pero esta igualdad también es valide para$x=0$. Esto significa que para todo$n$ en$\Bbb Z$; $n^p=n$ mod$p$, o ese$p$ divide$n^p-n$.