znaleźć największy dzielnik

[tukan]

Witam,
Znaleźć największy dzielnik będący potęgą dwójki. Ma dzielić liczbę \(3^{2^k}-1\).
I rozpisałem pierwsze przykłady (w sensie małe) i wychodzi na to, że \(2^{k+2}\) dobrze rokuje.

Więc zabrałem się do indukcji i się udało.

Dla \(k = 1\) mamy, że \(3^2 -1 = 8\). Faktycznie \(2^{1+2}\) dzieli \(8\). Co więcej jest to największa liczba, która to dzieli (większa potęga dwójki nie może dzielić ósemki.

Teza indukcyjna będzie taka: \(2{k+3}|3^{2^{k+1}} - 1\)

Rozpiszę trochę:
\(3^{2^{k+1}} - 1 = 3^{2^k \cdot 2 } - 1= 3^{2^k +2^k} - 1 = 3^{2^k} \cdot 3^{2^k} - 1\\
= 3^{2^k}(3^{2^k} - 1) + (3^{2^k} - 1) = (3^{2^k} -1)(3^{2^k} + 1) \\
= 3^{2^k}-1)(3^{2^k}-1+2) = (3^{2^k}-1)(3^{2^k}-1) + 2(3^{2^k}-1)\)
Z założenia indukcyjnego \((3^{2^k}-1)\) dzieli się przez \(2^{k+2}\). A przemnożone przez dwa dzieli się przez \(2^{k+3}\)
Czyli 2gi składnik spełnia tezę. Pierwszy też (to jest założenie podniesione do kwadratu).
Ostatecznie więc mamy spełnioną tezę.

Czy to jest ok ?

[Panko]

Wydaje się ,że kluczem do innego podejścia jest :

\(\forall k \in N\) \(\\)\(\\)\(3^{2^k} \equiv -1\)\(\\)\((\)\(mod\) \(\\)\(2\)\()\)
bo liczba \(3^{2^k} +1\) jest parzysta , a już dla \(k=1\) nie ma podzielności przez \(2^2\)

Wtedy : \(3^{2^k}-1=( 3^{2^{k-1}}-1 )( 3^{2^{k-1}}+1 )= ( 3^{2^{k-2}}-1 )( 3^{2^{k-2}}+1 )( 3^{2^{k-1}}+1 )\)\(= ( 3^{2^{k-3}}-1 ) ( 3^{2^{k-3}}+1 ) ( 3^{2^{k-2}}+1 )( 3^{2^{k-1}}+1 )=\).... \(=( 3^{2^1} -1)( 3^{2^1}+1) \cdot( 3^{2^2}+1) \cdot .... ( 3^{2^{k-2}}+1 )( 3^{2^{k-1}}+1 )=\)

Stąd każdy składnik postaci \(2|3^{2^{i}}+1\) i jest tych dwójek \(k-1\) , oraz \(2^3= 3^{2^1} -1\).
Stąd \(2^3 \cdot 2^{k-1}|3^{2^k}-1\) czyli \(2^{k+2}|3^{2^k}-1\)

Że nie ma podzielności przez \(2^{k+3}\) , wystarczy pokazać jedno konkretne \(k\)

[tukan]

Wnioskuję, że mam wszyskto ok ;D

Twoje rozwiązanie jest eleganckie, ale jednej rzeczy nie rozumiem.

Skąd wiesz, że każdy z nawiasów \(3^{2^i} + 1\) dzieli się tylko raz przez dwójkę ?
A może dzieli się także przez wyższe potęgi dwójki ? (co by podbiło wynik).

Bo nie wynika to wcale z:
\(3^{2^k}\equiv -1 (\mod 2)\)
Bo to mówi tylko tyle, że \(3^{2^i} + 1\) jest parzyste.

Skąd więc taki wniosek ?

[Panko]

To wynika np. z TW Eulera
\(n=2^{k+1}\) \(\\) , \(\\)wtedy \(\phi (n)= 2^{k+1}-2^k=2^k\)

Oraz \((3,2)=1\)\(\\) \(\\)\(\So\)\(\\)\(3^{2^k} \equiv 1\)\((\)\(mod\)\(\\)\(2^{k+1}\)\()\)

Stąd \(3^{2^k} +1 \equiv 1 +1\)\((\)\(mod\)\(\\)\(2^{k+1}\)\()\)
Czyli \(\forall\) \(k \in N\) \(\\)\(\\) \(3^{2^k} +1 \equiv 2\)\(\\)\((\)\(mod\)\(\\)\(2^{k+1}\)\()\)

Czyli po prostu żadna z liczb \(3^{2^k} +1\) nie dzieli się przez \(4=2^2\) , bo dla \(k \ge 1\) jest \(2^{k+1} \ge 2^2\)

[tukan]

Czyli, że chodzi o to, że mamy przystawanie "tej" liczby do dwójki (a nie do zera) modulo liczba podzielna przez 4

O to chodzi ?

[Panko]

Czyli \(\forall\)\(k \in N\) \(\\) liczba \(\\)\(3^{2^k}+1\) daje z dzielenia przez \(4\) resztę \(2\) .