1 of 4

# Showing that 2^(N-1) is is equivelent to 1 mod N

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 primer 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 M 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