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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum