problema puteri, cmmdc

ionut317 · Mesaj de **ionut317** » 16 Sep 2018, 21:36

$x= 2^{2^{i}} + 1$

$y= 2^{2^{j}} + 1$

Demonstrati ca (x, y) =1 ; i si j sunt numere naturale nenule si diferite

PhantomR · Mesaj de **PhantomR** » 17 Sep 2018, 00:23

Fie $p$ un numar prim care divide $x$ si $y$ . Cum $x,y$ sunt impare rezulta $p\neq 2$ . Incercam sa ajungem la contradictia $p=2$ .

Presupunem ca $i>j$ , celalalt caz tratandu-se analog.

Avem $p|x-y=2^{2^j}(2^{2^i-2^j}-1)$ . Daca $p|2^{2^j}$ , rezulta $p|2$ , de unde $p=2$ , fals. Deci $p|2^{2^i-2^j}-1$ . Notam $k=2^i-2^j$ si avem $0<k<2^i$ si $p|2^k-1$ .

Observam ca $2^{2^i}-1=(2^{2^{i-1}}-1)(2^{2^{i-1}}+1)=(2^{2^{i-2}}-1)(2^{2^{i-2}}+1)(2^{2^{i-1}}+1)=$
$=...=(2^k -1)(2^k+1)...(2^{2^{i-1}}+1)$ , deci $p|2^{2^i}-1$ (1).

Din $(1)$ si din faptul ca $p|x=2^{2^i}+1$ , prin adunare deducem $p|2^{2^i+1}$ , deci $p|2$ adica $p=2$ , contradictie.

Asadar, nu exista niciun numar prim $p$ care divide $x$ si $y$ , adica $(x,y)=1$ .

NOTA: Din antepenultimul paragraf al demonstratiei deducem ca daca un numar (nu neaparat prim) $a|2^{2^i}-1$ pentru un $i\geq 1$ , atunci $a|2^{2^z}-1,\forall z\geq i$ .

Mesaj de **ghioknt** » 23 Sep 2018, 20:53

PhantomR scrie: ↑
17 Sep 2018, 00:23

Presupunem ca $i>j$ , celalalt caz tratandu-se analog.

Observam ca $2^{2^i}-1=(2^{2^{i-1}}-1)(2^{2^{i-1}}+1)=(2^{2^{i-2}}-1)(2^{2^{i-2}}+1)(2^{2^{i-1}}+1)=$
$=...=(2^k -1)(2^k+1)...(2^{2^{i-1}}+1)$ , deci $p|2^{2^i}-1$ (1).

Nu înțeleg cum, pe al doilea rând, apare factorul $(2^k-1);$ pe primul rând exponenții lui 2 sunt, la rândul lor, puteri ale lui 2, în timp ce acel $k=2^i-2^j$ nu este întotdeauna o putere a lui 2.

Voi folosi următoarea afirmație ușor de probat: dacă 2 numere dau la împărțirea cu d>1 restul 1, atunci și produsul lor da la împărțirea cu d dă tot restul 1 cu consecința, dacă un numar natural dă restul 1 la împărțirea cu d, atunci orice putere a sa dă același rest, 1.
Fie d un divizor comun al celor două numere: $x=kd,\;y=2^{2^j}+1=ld$ . Deducem
$2^{2^{j+1}}=(ld-1)^2=l^2d^2-2ld+1=md+1$ , deci avem un număr care dă restul 1 la împărțirea cu d.
$kd=2^{2^i}+1=2^{2^{j+1}\cdot 2^{i-j-1}}+1=(md+1)^{2^{i-j-1}}+1=nd+1+1=nd+2$ .
De aici concluzia că d este un divizor al lui 2. Cum 2 nu poate fi, rămâne d=1.

PhantomR · Mesaj de **PhantomR** » 23 Sep 2018, 23:15

ghioknt scrie: ↑
23 Sep 2018, 20:53

PhantomR scrie: ↑
17 Sep 2018, 00:23

Presupunem ca $i>j$ , celalalt caz tratandu-se analog.

Observam ca $2^{2^i}-1=(2^{2^{i-1}}-1)(2^{2^{i-1}}+1)=(2^{2^{i-2}}-1)(2^{2^{i-2}}+1)(2^{2^{i-1}}+1)=$
$=...=(2^k -1)(2^k+1)...(2^{2^{i-1}}+1)$ , deci $p|2^{2^i}-1$ (1).
Nu înțeleg cum, pe al doilea rând, apare factorul $(2^k-1);$ pe primul rând exponenții lui 2 sunt, la rândul lor, puteri ale lui 2, în timp ce acel $k=2^i-2^j$ nu este întotdeauna o putere a lui 2.

Adevarat.. atunci 'demonstratia' mea e gresita. Ma bucur ca mi-a spus cineva, chiar asteptam un feedback. Am avut iluzia ca puterea scade si nu doar exponentul puterii lui $2$ de la putere..

Forum AniDeȘcoală.ro

problema puteri, cmmdc

problema puteri, cmmdc

Re: problema puteri, cmmdc

Re: problema puteri, cmmdc

Re: problema puteri, cmmdc