podzielność przez potęgi 3

[binaj]

Udowodnić lemat:

\(\displaystyle{ 3^r|2^m-1 \Rightarrow 3^{r-1}|m}\)

[Wasilewski]

Z twierdzenia Eulera mamy podzielność:
\(\displaystyle{ 3^{r} \mid 2^{2\cdot 3^{r-1}}-1}\)
Rząd 2 modulo \(\displaystyle{ 3^{r}}\) musi być parzysty, zatem jest postaci \(\displaystyle{ 2\cdot 3^{k}}\). Teraz indukcyjnie pokaż, że \(\displaystyle{ 3^{k} \nmid 2^{2\cdot 3^{k-2}}-1}\), co będzie oznaczało, że rząd jest równy \(\displaystyle{ 2\cdot 3^{r-1}}\).
Mam nadzieję, że nic mi się nie pomyliło.

[binaj]

Rząd 2 modulo \(\displaystyle{ 3^{r}}\) musi być parzysty, zatem jest postaci \(\displaystyle{ 2\cdot 3^{k}}\).

a dlaczego nie może być postaci: \(\displaystyle{ 2 \cdot q \cdot 3^k}\) gdzie q jest liczbą niepodzielną przez 3?

edit: pospieszyłem się, oczywiste, że rząd dzieli \(\displaystyle{ 2 \cdot 3^r}\), więc nie ma tam żadnych q

dzięki

[pawelsuz]

Może to głupie pytanie, ale mógłby mi ktoś powiedzieć, dlaczego ta indukcja bedzie oznaczało to, co napisał Wasilewski?

[Wasilewski]

Skoro \(\displaystyle{ 3^{k} \mid 2^{2 \cdot 3^{k-1}} - 1}\) oraz \(\displaystyle{ 3^{k} \nmid 2^{2\cdot 3^{k-2}} - 1}\), to \(\displaystyle{ k}\) jest najwyższym wykładnikiem, dla którego zachodzi podzielność \(\displaystyle{ 3^{k} \mid 2^{2\cdot 3^{k-1}} - 1}\), stąd rząd modulo \(\displaystyle{ 3^{k}}\) jest nie mniejszy niż \(\displaystyle{ 2\cdot 3^{k-1}}\). Z twierdzenia Eulera mamy jednak wniosek, że ten rząd jest nie większy niż \(\displaystyle{ 2\cdot 3^{k-1}}\), czyli tyle jest właśnie równy.

[pawelsuz]

Wielkie dzięki!