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

Printable View

- Apr 27th 2009, 09:05 AMjboitePseudoprimes #2
Let p be prime, prove that if (2^p)-1 is a composite number, then m=(2^p)-1 is a pseudoprime.

- Apr 29th 2009, 01:13 PMhtata123
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