Największa potęga dwójki

[mint18]

Dla danej liczby naturalnej \(\displaystyle{ n}\) wyznaczyć maksymalną potęgę dwójki dzielącą liczbę \(\displaystyle{ 7^n-1}\).

[wielkireturner]

Określmy funkcję \(\displaystyle{ f \left( \frac{n}{w}\right)}\), która przyjmuje wartość \(\displaystyle{ 1}\) dla \(\displaystyle{ n}\) podzielnego przez \(\displaystyle{ w}\) i wartość \(\displaystyle{ 0}\) dla \(\displaystyle{ n}\) niepodzielnego przez \(\displaystyle{ w}\) ( \(\displaystyle{ w,n \in N}\)).
Niech \(\displaystyle{ X}\) oznacza liczbę niepodzielną przez \(\displaystyle{ 2}\).
Liczbę \(\displaystyle{ 7^{n}-1}\) można zapisać w postaci \(\displaystyle{ 6 \cdot (7^{1}+1)^{f( \frac{n}{2})} \cdot (7^{2}+1)^{f( \frac{n}{4})} \cdot (7^{4}+1)^{f( \frac{n}{8})} \cdot (7^{8}+1}) ^{f( \frac{n}{16})} \cdot ... \cdot X}\)
Jak doszedłem do tej postaci, podam jak najszybciej, ale jest to nieco długie. Na razie jak z tej postaci wynika podzielność przez potęgi \(\displaystyle{ 2}\) dla danego \(\displaystyle{ n}\). Otóż: każdy z kolejnych czynników w nawiasie poza \(\displaystyle{ X, 6, (7^{1}+1)}\) nie dzieli się przez \(\displaystyle{ 4}\), a dzieli się przez \(\displaystyle{ 2}\), co wynika z kongruencji. Zatem otrzymaliśmy poszukiwaną zależność.

Dowód wzoru:
\(\displaystyle{ 7^{n}-1 = 6 \cdot ( 7^{n-1}+7^{n-2}+...+1)}\)
Stąd widzimy, że dla n nieparzystych występuje tylko podzielność przez \(\displaystyle{ 2}\). Załóżmy więc, że \(\displaystyle{ n=2k, k \in N}\). Wówczas:
\(\displaystyle{ 6 \cdot ( 7^{n-1}+7^{n-2}+...+1) = 6 \cdot ( 7^{2k-1}+7^{2k-2}+...+1) = 6 \cdot (7+1) \cdot (7^{2k-2}+7^{2k-4}+...+1)}\)
Liczba wyrazów w ostatnich nawiasach jest równa \(\displaystyle{ k}\), a każdy wyraz jest niepodzielny przez \(\displaystyle{ 2}\), zatem by wyrażenie w nawiasie było podzielne przez \(\displaystyle{ 2}\), \(\displaystyle{ k=2p,p \in N}\)
Założymy od razu również, że \(\displaystyle{ p =2r}\), by płynnie przejść do następnego przekształcenia.
\(\displaystyle{ 6 \cdot (7+1) \cdot (7^{2k-2}+7^{2k-4}+...+1) = 6 \cdot (7+1) \cdot (7^{4p-4}+7^{4p-8}+... + 1) = 6 \cdot (7+1) \cdot (7^{2}+1) \cdot (7^{8r-4}+7^{8r-8}+...+1) = 6 \cdot (7+1) \cdot (7^{2}+1) \cdot (7^{4}+1) \cdot ...}\)
I stąd wynika wzór powyżej.

[Medea 2]

Funkcja \(\displaystyle{ f}\) to po prostu \(\displaystyle{ \chi_\NN}\). Udało Ci się pokazać, że \(\displaystyle{ \textrm{ord}_2(7^n-1) = \textrm{ord}_2(n) + 1 + 2 \chi_{2\ZZ}(n)}\) - to tak gdyby ktoś się zastanawiał, jak wygląda zwarta postać odpowiedzi.

[bakala12]

Z LTE łatwo mamy:
\(\displaystyle{ v_{2}\left(7^{n}-1\right)=\begin{cases} 1, \quad 2 \nmid n \\ 3+v_{2}\left(n\right), \quad 2|n \end{cases}}\)