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

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

  • 0
    Why do you multiply $2^{n-1}-1$ by 2? Is there any other reason then "getting to right form"?2011-10-28
  • 1
    @Daniel: Specifically, we want the exponent $N-1$ to be divisible by $n$. Wanted every step to be clear.2011-10-28
  • 0
    Ah fine, got it. One more question: Why do we have to proof that N is composite?2011-10-31
  • 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