Oczywiście zakładamy, że [tex]n\in\mathbb{N}[/tex] cokolwiek to znaczy... dla [tex]n=0[/tex] działa podobnie dla [tex]n=1[/tex]. Potraktujmy to jako bazę indukcji i sprawdźmy, że jeśli [tex]3^n|2^{3^n}+1[/tex] to [tex]3^{n+1}|2^{3^{n+1}}+1[/tex]. Więc ustalmy [tex]n\in\mathbb{N}[/tex] dla którego [tex]3^n|2^{3^n}+1[/tex] i zauważmy, że
[tex]2^{3^{n+1}}+1=(2^{3^{n}})^3+1^3=(2^{3^n}+1)(( 2^{3^{n}} )^2-2^{3^{n}}+1)[/tex]
ponieważ [tex]3^n|2^{3^n}+1[/tex], a chcemy wykazać, że [tex]3^{n+1}|2^{3^{n+1}}+1[/tex] to wystarczy pokazać, że [tex]3 \ | \ ( 2^{3^{n}} )^2-2^{3^{n}}+1[/tex], bo pierwszy nawias już dzieli się przez [tex]3^n[/tex]. Zauważmy jednak, że
[tex]( 2^{3^{n}} )^2-2^{3^{n}}+1 = (3-1)^{2\cdot 3^n}-(3-1)^{3^n}+1=[/tex]
[tex]3\cdot (\text{bla bla bla})+(-1)^{2\cdot 3^n}-(-1)^{3^n}+1[/tex]
Co ważniejsze [tex](-1)^{2\cdot 3^n}-(-1)^{3^n}+1=3[/tex] zatem faktycznie drugi nawias dzieli się przez [tex]3[/tex]. Tym samym zostało wykazane, że [tex](2^{3^n}+1)(( 2^{3^{n}} )^2-2^{3^{n}}+1)[/tex] dzieli się przez [tex]3^{n+1}[/tex]. Formalnie powołujemy się na ZIM i wtedy cnd.
Można nawet zauważyć, że prawda jest mocniejsze twierdzenie bowiem na mocy twierdzenia Eulera i prostych własności funkcji [tex]\phi[/tex] można zapisać, że [tex]2^{3^n-3^{n-1}} \equiv 1 \mod 3^n[/tex] czyli [tex]2^{3^n} \equiv 2^{3^{n-1}} \mod 3^n[/tex]. Z tego mamy dalej, że [tex]2^{3^n}+1 \equiv 2^{3^{n-1}}+1 \mod 3^n[/tex], a ponieważ jak już wiemy [tex]2^{3^n}+1 \equiv 0 \mod 3^n[/tex] to prawdą jest też, że [tex]2^{3^{n-1}}+1 \equiv 0 \mod 3^n[/tex]. Zatem prawdą jest mocniejsze twierdzenie głoszące, że [tex](\forall n\in\mathbb{N}) 3^{n+1}| 2^{3^n}+1.[/tex]
