Another Number Theory question.

[Nottom]

I need to show that (2^p)-1 is a (Fermat)pseudoprime to the base 2. Given p is prime and (2^p)-1 is composite.

Any help?

[lightw1thoutheat]

i have heard a number of diff psuedoprime definitions. is this the one your using: n is a pseudoprime to the base b if b^(n-1)=1 mod n?.,

or is it: n is pseudoprime to base b if b^((n-1)/2)= (b/n) mod n where (b/n) is the jacobi sumbol?

[Nottom]

[ QUOTE ]
n is a pseudoprime to the base b if b^(n-1)=1 mod n?.,

[/ QUOTE ]

this one

[AlphaWice]

Let x = (2^p)-1.

We need 2^(x-1) = 1 mod x. Notice (x-1) = 0 mod p. So write x-1 = pk, some integer k. Then we need 2^(pk) - 1 = 0 mod ((2^p) - 1). (*)

Finally, (2^(pk) - 1) = ((2^p)-1)(2^(pk-p) + 2^(pk-2p) + ... + 1), so (*) is true.

[Nottom]

[ QUOTE ]
Notice (x-1) = 0 mod p

[/ QUOTE ]

Why is this true?