Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
$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
up vote 5 down vote accepted

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$.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.