¿Cuál es la conexión entre Fermat Poco y Teorema "de Fermat Mentirosos"?

Question

Sé que Fermat Poco Teorema establece que si $p$ es el primer y $1 < a < p$, $a^{p-1} \equiv 1 ($mod $p)$.

También sé que una de Fermat Mentiroso es cualquier $a$ tal que $a^{n-1} \equiv 1 ($mod $n$), al $n$ es compuesto.

Creo que estos dos puntos podrían ser relevantes para una pregunta estoy tratando de resolver, que me pide para demostrar que si $n = 2^p -1$ donde $p$ es primo, entonces $2^{n-1} \equiv 1$(mod $n)$.

Sin embargo, no estoy seguro exactamente de cómo utilizar la información que he reunido para formar una explicación. Alguna ayuda se agradece!

Answer 1

En general, la forma en que Fermat mentirosos aparecer es la siguiente: si $x$ ha multiplicativo orden de $a$ modulo $n$, e $a \mid n-1$, luego $$x^a \equiv 1 \pmod n \implies (x^a)^{(n-1)/a} \equiv 1 \pmod n \implies x^{n-1} \equiv 1 \pmod n.$$ In particular, in the case of Carmichael numbers, $\phi(n) \mediados de los n-1$, so we always have $\mediados de los n-1$ whenever $\gcd(x,n)=1$.

Si $n = 2^p-1$,$2^p \equiv 1 \pmod n$, lo cual nos dice que $2$ ha multiplicativo orden de $p$ modulo $n$. (En general, nos gustaría saber que $2$ ha multiplicativo orden de algunos divisor de $p$, pero aquí $p$ es primo.) Llegaremos $2^{n-1} \equiv 1 \pmod n$ si $p \mid n-1$.

Pero $p \mid n-1$ es decir que $p \mid 2^p-2$, que es precisamente la afirmación de Fermat poco teorema: $2^p \equiv 2 \pmod p$. Así que tenemos la garantía de que $p \mid n-1$, e $$2^{n-1} = (2^p)^{(n-1)/p} \equiv 1^{(n-1)/p} = 1 \pmod n.$$