# 2-pseudoprime!

• Nov 14th 2011, 04:43 PM
hashshashin715
2-pseudoprime!
A number m is called a 2-pseudoprime if

(a) m is composite, and

(b) 2^(m -1) == 1 mod m (where == is the congruent sign, the triple horizontal bars)

(it's pseudo because it looks like Fermat's little theorem.

I need to show that if n is a pseudoprime then m = [2^n] - 1 is also a 2-pseudoprime.

I have shown that m is composite, now how do I go about showing the other condition? I tried playing around with the mod stuff, but I bring it down to something like this:

if (2^n - 2) / n is an integer then show that ([2^2^n] - 4) / (2^n - 1) is also an integer. But I'm stuck proving this too. Any help?
• Nov 20th 2011, 05:32 AM
PaulRS
Re: 2-pseudoprime!
First note that $m = 2^n - 1$ implies that $2^n \equiv 1 (\bmod. m)$ , thus in fact $2^r \equiv 2^{ r \bmod n} (\bmod. m)$ for any $r\in \mathbb{Z}$ (because adding - or substracting- $n$'s to the exponent won't change the result)

But now, by hypothesis $2^{n-1} \equiv 1 (\bmod. n)$ thus $2^n \equiv 2 (\bmod. n)$ ... (Wink)