Daca \( 2^{n} \)+1=pq, n>0, aratati ca p-1 si q-1 se divid cu aceeasi putere a lui 2.
problema la puterea a doua!
Moderators: Bogdan Posa, Laurian Filip
problema la puterea a doua!
-
Marius Dragoi
- Thales
- Posts: 126
- Joined: Thu Jan 31, 2008 5:57 pm
- Location: Bucharest
Observam ca \( p,q \) sunt impare. Atunci avem:
\( p=2^ak+1 \) si \( q=2^br+1 \) unde \( a,b \geq 1 \) iar \( k,r \) impare.
Observatie! \( a,b,k,r \in N \).
Din ipoteza avem: \( 2^n+1=(2^ak+1)(2^br+1) \Rightarrow 2^n=2^{a+b}kr+2^ak+2^br \)
Fie \( a \leq b \) atunci \( \Rightarrow 2^n=2^a(2^bkr+k+2^{b-a}r)\Rightarrow 2^{n-a}=2^bkr+k+2^{b-a}r \)
cum \( 2^{n-a}, 2^bkr \) sunt pare , iar \( k \) este impar \( \Rightarrow 2^{b-a}r \) este impar \( \Rightarrow b-a=0 \Rightarrow a=b \).
Asadar avem: \( p-1=2^ak \) iar \( q-1=2^ar \). qed
\( p=2^ak+1 \) si \( q=2^br+1 \) unde \( a,b \geq 1 \) iar \( k,r \) impare.
Observatie! \( a,b,k,r \in N \).
Din ipoteza avem: \( 2^n+1=(2^ak+1)(2^br+1) \Rightarrow 2^n=2^{a+b}kr+2^ak+2^br \)
Fie \( a \leq b \) atunci \( \Rightarrow 2^n=2^a(2^bkr+k+2^{b-a}r)\Rightarrow 2^{n-a}=2^bkr+k+2^{b-a}r \)
cum \( 2^{n-a}, 2^bkr \) sunt pare , iar \( k \) este impar \( \Rightarrow 2^{b-a}r \) este impar \( \Rightarrow b-a=0 \Rightarrow a=b \).
Asadar avem: \( p-1=2^ak \) iar \( q-1=2^ar \). qed
Politehnica University of Bucharest
The Faculty of Automatic Control and Computers
The Faculty of Automatic Control and Computers