Solutie elementara. Sa observam ca
\( 2^{2p} \equiv 4^p \equiv 1^p \equiv 1 \pmod{3} \), deci
\( n \in \mathbb{N}^{\ast} \). Evident este suficient ca
\( 2^{n-1} \equiv 1 \pmod{n} \).
Pe de alta parte,
\( 2^{2p} \equiv 1 \pmod{n} \). Sa aratam ca
\( 2p | n - 1 \), si astfel ridicand la puterea corespunzatoare obtinem ceea ce este necesar. Insa
\( 2p | n - 1 \) se reduce la
\( 6p | 2^{2p} - 4 \), si mai departe echivalent cu
\( 3p | 2^{2p - 1} - 2 \). Dar
\( p | 4^{p - 1} - 1 \) (mica teorema a lui Fermat), iar
\( 4^{p - 1} \equiv 1 \pmod{3} \) din aceleasi motive ca mai sus. Cum
\( (3, p) = 1 \), concluzionam
\( 3p | 4^{p - 1} - 1 | 2^{2p - 1} - 2 \), ceea ce trebuia aratat.
Remarci. Deoarece
\( n = \frac{2^{2p} - 1}{3} = (2^p - 1) \cdot \frac{2^p + 1}{3} \) iar
\( \frac{2^p + 1}{3} \in \mathbb{N}_2 \) pentru
\( p > 3 \) prim, am demonstrat ca exista o infinitate de numere compuse
\( n \) pentru care
\( n | 2^{n-1} - 1 \), relatie verificata si de numerele prime însele. Aceasta proprietate se numeste pseudoprimalitate Fermat în baza
\( 2 \). Generalizarea problemei o constituie faptul ca numerele (compuse)
\( \frac{a^{2p} - 1}{a^2 - 1} \), pentru
\( a \ge 2 \) iar
\( p \) un prim impar care nu divide
\( a^2 - 1 \), sunt toate pseudoprime în baza
\( a \) - solutia desfasurandu-se, în linii mari, exact ca mai sus. Aceste idei mai pot fi puse în discutie
aici.
O alta latura o povestii o constituie faptul ca toate acestea nu erau, evident, cunoscute in secolul XVII - cand se credea ca asa-numita
Teorema chineza era adevarata.
Se poate demonstra insa ca si
Numerele Fermat compuse sunt pseudoprime in baza
\( 2 \) - fapt care s-ar putea specula ca l-a condus pe Fermat la afirmatia sa ca toate ar reprezenta numere prime.
Revenind, nu mai este totusi atat de "straightforward" demonstratia faptului ca
\( n | 2^{n-1} + 1 \Rightarrow n = 1 \) (desi metodele nu depasesc cadrul elementar, de liceu). Un rezultat clasic ceva mai facil stipuleaza
\( n | 2^n - 1 \Rightarrow n = 1 \).