The Math Forum

Ask Dr. Math - Questions and Answers from our Archives
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 
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

[Privacy Policy] [Terms of Use]

Math Forum Home || Math Library || Quick Reference || Math Forum Search

Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.