I got this question on a previous exam and I got it wrong. I've gone back through it several times since then, but I can't seem to get it. I would really like to know how to do it, so if someone could give me a step by step walk through (answers included), I would really appreciate it! Thanks! The question is the following:
Let $p$ be an odd prime number and $N=2^{p}-1$. The goal of this problem is to show that $2^{N-1}$ is equivalent to $1 \mod N$, namely that $N$ passes the Fermat primality test for $a=2$. [Note: This doesn't mean that N is necessarily prime. For example, if $p=11$, $N=2047=23*89$ and if $p=23$, then $N=8388607=47*178481$.] Then, do the following:
a) Explain why $2^p$ is equivalent to $1 \mod N$ is true
b) Show that $N-1$ is equivalent to $0 \mod p$
c) Use parts a and b to show that $2^{N-1}$ is equivalent to $1 \mod N$