1
$\begingroup$

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, 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

1 Answers 1

5

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

  • 1
    @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.2011-10-31