I know that Fermat's Little Theorem states that if $p$ is prime and $1 < a < p$, then $a^{p-1} \equiv 1 ($mod $p)$.
I also know that a Fermat Liar is any $a$ such that $a^{n-1} \equiv 1 ($mod $n$), when $n$ is composite.
I feel that these two points could be relevant to a question I'm trying to solve, which asks me to show that if $n = 2^p -1$, where $p$ is prime, then $2^{n-1} \equiv 1$(mod $n)$.
However, I'm not sure exactly how to use the information I have gathered to form an explanation. Some help would be appreciated!
Answer
In general, the way that Fermat liars appear is as follows: if $x$ has multiplicative order $a$ modulo $n$, and $a \mid n-1$, then $$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) \mid n-1$, so we always have $a \mid n-1$ whenever $\gcd(x,n)=1$.
If $n = 2^p-1$, then $2^p \equiv 1 \pmod n$, which tells us that $2$ has multiplicative order $p$ modulo $n$. (In general, we'd only know that $2$ has multiplicative order some divisor of $p$, but here $p$ is prime.) We'll get $2^{n-1} \equiv 1 \pmod n$ if $p \mid n-1$.
But $p \mid n-1$ is saying that $p \mid 2^p-2$, which is precisely the statement of Fermat's little theorem: $2^p \equiv 2 \pmod p$. So we are guaranteed that $p \mid n-1$, and $$2^{n-1} = (2^p)^{(n-1)/p} \equiv 1^{(n-1)/p} = 1 \pmod n.$$
No comments:
Post a Comment