If $n$ is pseudo prime to $2 \in Z_n$, then $N = 2^n -1$ is a pseudo-prime to $2 \in Z_N$.

Question

If $n$ is pseudo prime to $2 \in Z_n$, then $N = 2^n -1$ is a pseudo-prime to $2 \in Z_N$.

Attempt: By definition, $n$ being a pseudoprime to $2$ in $Z_n$ means $2^{n-1} - 1 = nk$ for some integer $k$. I am not sure where to go with this.

Answer 1

Set $N:=2^n-1$. HINT: $$2^{n-1} \equiv_n 1 \ \implies \ 2^n \equiv_n 2$$ $$\implies n|(2^n -2) \implies n|(N-1)$$ $$\implies (2^n-1)|(2^{N-1}-1)$$ $$\implies N|(2^{N-1}-1) \implies 2^{N-1} \equiv_{N} 1.$$