Matematyka.pl

Treść zadania:
Znaleźć największą potęgę 2 dzielącą liczbę \(\displaystyle{ 3^{2^k}-1}\).

Wiem, że poprawną odpowiedzią jest \(\displaystyle{ 2^{k+2}}\), ale niestety, potrafię udowodnić tylko \(\displaystyle{ 2^{k+1}}\).
Co trzeba dołożyć do tw. Eulera, żeby uzyskać poprawną odpowiedź?

Skorzystamy tutaj z tzw LTE (Lifting The Exponent). Odpowiednią teorię można sobie łatwo wygooglać (pierwszy link). Pisząc pokrótce, jeśli oznaczymy \(\displaystyle{ v_{p}(n)}\) jako największą potęgę liczby \(\displaystyle{ p}\) dzielącą liczbę \(\displaystyle{ n}\), to możemy wysunąć szereg przydatnych zależności.

W szczególności wiemy, że jeśli mamy dwie liczby nieparzyste \(\displaystyle{ x}\) i \(\displaystyle{ y}\) takie, że \(\displaystyle{ 4|x-y}\), to zachodzi:


\(\displaystyle{ v_{2}(x^n - y^n) = v_{2}(x - y) + v_{2}(n)}\)

Sprawdźmy, czy jak podstawimy \(\displaystyle{ x=3}\), \(\displaystyle{ y=1}\), \(\displaystyle{ n=2^k}\), to będzie fajnie. Niestety \(\displaystyle{ 4}\) nie dzieli \(\displaystyle{ 3-1}\), wiec mamy skuchę. Ale nic straconego, bo jeśli zauważymy, że \(\displaystyle{ 3^{2^{k}} = 3^{2 \cdot 2^{k-1}} = 9^{2^{k-1}}}\), to możemy się pokusić o podstawienie \(\displaystyle{ x=9}\), \(\displaystyle{ y=1}\), \(\displaystyle{ n=2^{k-1}}\).
Skoro \(\displaystyle{ 9-1=8}\) jest podzielne przez \(\displaystyle{ 4}\), to możemy zatrzeć ręce i zabrać się do zwieńczenia naszego niecnego dzieła. Podstawmy już do wcześniejszego wzorku nasze fajne liczby:

\(\displaystyle{ v_{2}(x^n - y^n) = v_{2}(9^{2^{k-1}} - 1) = v_{2}(9 - 1) + v_{2}(2^{k-1}) = v_{2}(8) + v_{2}(2^{k-1})}\).

Nie ma wątpliwości, że \(\displaystyle{ v_{2}(8) = 3}\) oraz \(\displaystyle{ v_{2}(2^{k-1}) = k-1}\). Wobec tego \(\displaystyle{ v_{2}(9^{2^{k-1}} - 1) = k+2}\). Eureka! Dobrnęliśmy do końca. Prostszego rozwiązania niestety nie widzę, ale sądzę, że takowe istnieje.

\(\displaystyle{ 3^{2^k}-1=(3^{2^{k-1}})^2-1=(3^{2^{k-1}}+1)(3^{2^{k-1}}-1)=...}\)
robimy to k razy z nawiasem w którym jest minus, zostanie:
\(\displaystyle{ (3^{2^{k-1}}+1)(3^{2^{k-1}}+1)(3^{2^{k-2}}+1)...(3^{2^0}+1)(3^{2^0}-1)}\)

Teraz mamy k czynników, każdy parzysty, a przedostatni to 4. Dodatkowo należałoby pokazać, że wszystkie czynniki oprócz czwórki są podzielne tylko przez 2 (a nie przez 4), wynika to stąd, że \(\displaystyle{ 3^{2n}\equiv_49^n\equiv_4 1}\) dla \(\displaystyle{ n>0}\)

edit: co do posta wyżej, zamiast 9 można też rozważyć \(\displaystyle{ -3}\)

Dzięki za odpowiedzi
Nie wiem po co się pchałem od razu w tw. Eulera, chyba bałem się, że przy takim rozkładzie będę miał jakieś brzydkie czynniki. Zadanie zdecydowanie łatwiejsze niż się początkowo zdawało.