Thread: Pseudoprimes #2

Let p be prime, prove that if (2^p)-1 is a composite number, then m=(2^p)-1 is a pseudoprime.

n = 2^p -1 == (denotes congruent)

2^(p-1) == 1modp by fermats little theorem

since p is an odd prime.

p|(2^(p-1)-1)

so p|n-1

n = 2^p -1|2^(n-1) -1

2^(n-1) == 1mod n

and 2^n == 2 mod n, so n is a pseudoprime