# If $n$ is an odd pseudoprime , then $2^n-1$ is also odd pseudoprime

I have some problems understanding the following proof:

Definition: A composite number $n \in \mathbb{N}$ is called pseudo prime if $n \mid 2^{n-1}-1$ holds.

Theorem: If n is a odd pseudo prime number, then $2^n-1$ is also an odd pseudo prime number, too.

Proof: Let n be an odd pseudo prime number. Then we get $2^{n-1}-1=kn$ with $n \in \mathbb{N}$. It follows $2^{2^n-2}=2^{2kn}$ and further $2^{2^n-2}-1=(2^n)^{2k}-1$. We get $2^n-1 \mid 2^{2^n-2}-1$, but also $2^n-1 \mid 2^{2^n-1}-2$. Let $d \mid n$ with $1<d<n$, then it follows $2^d-1\mid 2^n-1$ and $1<2^d-1<2^n-1$. So $2^n-1$ is also an pseudo prime number.

Now my questions: What is the reason, that the author made this step: $2^{2^n-2}=2^{2kn}$, just to get rid of the "k"? The next step is also not clear: $2^{2^n-2}-1=(2^n)^{2k}-1$.

If anyone could explain the steps to me, I would be thankful. Greetings

-
$2^n-1$ is always odd when $n$ is a positive integer. So there are no odd pseudo primes according to your definition. – Henning Makholm Oct 27 '11 at 18:47
Sry, changed the topic. I don't have to proof that it's odd, it has to be an odd pseudo prime. But you're right ;) – ulead86 Oct 27 '11 at 18:51
No, he means that you wrote $2 | 2^n-1$ when you meant $n | 2^{n-1}-1$. I fixed it. – Thomas Andrews Oct 27 '11 at 18:57
ah, thanks a lot – ulead86 Oct 28 '11 at 8:53

This solution is essentially the same as the one quoted by OP, with some detail added and some removed. The most useful change is the introduction of $N$, which allows us to have one less level of exponentiation.

We have $2^{n-1}\equiv 1 \pmod{n}$. Let $N=2^n-1$. We first show that $N$ is composite. Since $n$ is composite, $n=ab$ for some $a>1$, $b>1$. Then $2^a-1$ is a non-trivial divisor of $2^n-1$.

Now we need to show that $2^{N-1} \equiv 1 \pmod{N}$. Since $n$ divides $2^{n-1}-1$, set $2^{n-1}-1=nk$. Multiply by $2$. We get $2^n-2=2nk$. But $2^n-2=N-1$, so $N-1=2nk$.

Thus $2^{N-1}=(2^n)^{2k}=(1+N)^{2k}\equiv 1 \pmod{N}$, which is the desired result.

Comment: One reason we let $N=2^n-1$ is that then the messy $2^{2^n-2}$ of the post becomes the understandable $2^{N-1}$, which is the object we need to compute modulo $N$ to show that $2^n-1$, that is, $N$, is a pseudo-prime to the base $2$.

-
Why do you multiply $2^{n-1}-1$ by 2? Is there any other reason then "getting to right form"? – ulead86 Oct 28 '11 at 8:53
@Daniel: Specifically, we want the exponent $N-1$ to be divisible by $n$. Wanted every step to be clear. – André Nicolas Oct 28 '11 at 15:10
Ah fine, got it. One more question: Why do we have to proof that N is composite? – ulead86 Oct 31 '11 at 16:47
@Daniel: A pseudo-prime to the base $2$ is defined to be a non-prime $N$ that satisfies the congruence $2^{N-1}\equiv 1\pmod{N}$, it is a non-prime kind of masquerading as a prime, in the sense that it passes the Fermat test with $a=2$. So we do have to check two things: (i) non-prime and (ii) passes the test. – André Nicolas Oct 31 '11 at 17:15
a thank you very much – ulead86 Oct 31 '11 at 17:16