4
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.