Showing that $2^{N-1}\equiv1\pmod N$ when $N=2^p-1$ for prime $p$

Question

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$

Answer 1

a) $2^p \equiv 1 \mod N$ because $2^p = N + 1$. When you reduce $\mod N$ (take the remainder when dividing by $N$), you are left with 1.

b) $N - 1 = 2^p - 2$

By Fermat's little theorem, $2^p \equiv 2 \mod p$:

$2^p - 2 \equiv 2 - 2 \equiv 0 \mod p$

c)

From a) we know that $2^p \equiv 1 \mod N$

From b) we know that $N - 1 \equiv 0\mod p$, therefore $N-1$ is a multiple of $p$.

Let $N-1 = kp$ for some integer $k$

$2^{N-1} = 2^{kp}$

$(2^p)^{k} \equiv 1^k \equiv 1 \mod N$