<s>[INST] Mersenne numbers congruent to two Prove that $2^{2^n-1} = 2 \pmod{2^n - 1}$ given that $2^n = 2 \pmod n$.
How would I go about proving that? I started by saying let $m = 2^n - 1$
Then, $2^n = 1 \pmod{m}$.
So I need to prove $2^m = 1 \pmod m$. I'm not sure how to proceed.
 [/INST] Observe that $2^n \equiv 1 \pmod{ 2^n-1} $.
Given that $2^n \equiv 2 \pmod{n}$, we know that $2^n - 1 \equiv 1 \pmod {n}$, or that $2^n -1 = kn + 1 $ for some integer $k$.
Thus, $2^{ 2^n -1 } = 2^{kn + 1} \equiv 2 \pmod{2^n-1}$.
</s>