Fie \( p>3 \) un numar prim, iar \( n=\frac{2^{2p}-1}{3} \). Sa se arate ca \( n \) divide \( 2^n-2 \).
Vojtech Jarnik, 2002 Categoria I
Pentru un anumit n acesta divide 2^n-2
Moderators: Laurian Filip, Filip Chindea, maky, Cosmin Pohoata
-
Cezar Lupu
- Site Admin
- Posts: 612
- Joined: Wed Sep 26, 2007 2:04 pm
- Location: Bucuresti sau Constanta
- Contact:
Pentru un anumit n acesta divide 2^n-2
An infinite number of mathematicians walk into a bar. The first one orders a beer. The second orders half a beer. The third, a quarter of a beer. The bartender says “You’re all idiots”, and pours two beers.
-
Filip Chindea
- Newton
- Posts: 324
- Joined: Thu Sep 27, 2007 9:01 pm
- Location: Bucharest
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 \).
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 \).
Life is complex: it has real and imaginary components.