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 ?
znaleźć największy dzielnik
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Fachowiec
- Posty: 2946
- Rejestracja: 20 gru 2013, 21:41
- Lokalizacja: Radom
- Otrzymane podziękowania: 1556 razy
- Płeć:
Re: znaleźć największy dzielnik
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\)
\(\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\)
-
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
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 ?
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 ?
-
- Fachowiec
- Posty: 2946
- Rejestracja: 20 gru 2013, 21:41
- Lokalizacja: Radom
- Otrzymane podziękowania: 1556 razy
- Płeć:
Re: znaleźć największy dzielnik
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\)
\(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\)
-
- Fachowiec
- Posty: 2946
- Rejestracja: 20 gru 2013, 21:41
- Lokalizacja: Radom
- Otrzymane podziękowania: 1556 razy
- Płeć:
Re: znaleźć największy dzielnik
Czyli \(\forall\)\(k \in N\) \(\\) liczba \(\\)\(3^{2^k}+1\) daje z dzielenia przez \(4\) resztę \(2\) .