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