Wykaż, że liczba n jest pierwsza

[Hayran]

Wykaż, że jeśli liczba \(\displaystyle{ 2^{2^n-1}-1}\)jest pierwsza to również liczba \(\displaystyle{ n}\) jest pierwsza.

[Premislav]

To chyba jest trywialne. Przez kontrapozycję: pokażemy, że jeżeli \(\displaystyle{ n}\) jest złożona, to
\(\displaystyle{ 2^{2^n-1}-1}\) też jest złożona. Mianowicie, jeżeli \(\displaystyle{ n}\) jest złożoną, to \(\displaystyle{ 2^n-1}\) jest złożoną: istotnie, jeśli \(\displaystyle{ p|n}\) i \(\displaystyle{ 1<p<n}\) i \(\displaystyle{ n=pq}\), to
\(\displaystyle{ 2^n-1=(2^p-1^p)(2^{q-1}+2^{q-2}+\dots+1)}\), a liczba
\(\displaystyle{ 2^p-1}\) jest większa od \(\displaystyle{ 1}\) (z monotoniczności \(\displaystyle{ f(x)=2^x}\))
i wobec tego analogicznie rozbijemy ze wzoru na różnicę k-tych potęg liczbę
\(\displaystyle{ 2^{2^n-1}-1}\)...