1. ## 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?

2. ## Re: 2-pseudoprime!

First note that $\displaystyle m = 2^n - 1$ implies that $\displaystyle 2^n \equiv 1 (\bmod. m)$ , thus in fact $\displaystyle 2^r \equiv 2^{ r \bmod n} (\bmod. m)$ for any $\displaystyle r\in \mathbb{Z}$ (because adding - or substracting- $\displaystyle n$'s to the exponent won't change the result)

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