Associated Topics || Dr. Math Home || Search Dr. Math

### Show 2^(N-1) Congruent to 1(mod N)

```Date: 02/25/2003 at 15:51:24
From: Justin
Subject: Algebra theory

I need to show that if N = 2^p - 1, p prime, then 2^(N-1) is congruent
to 1(mod N).

I was trying to show that if N = 2^p - 1 is prime, then 2^p is
congruent to 1(mod N) by starting with N-1=kp for some number k and
THEN 2^(N-1) is congruent to (2^p)^k which is congruent to 1, but I
can't figure out what to do next. Please help.
```

```
Date: 02/26/2003 at 06:31:43
From: Doctor Jacques
Subject: Re: Algebra theory

Hi Justin,

By Fermat's "Little theorem," we know that:

2^p = 2 (mod p)

and, therefore, n = 1 (mod p), which is equivalent to saying that p
divides (n-1).

We also know, by hypothesis, that

2^p = 1 (mod N)

Can you continue from here?

Please feel free to write back if you are still stuck.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/