Podzielność przez potęgę dwójki

[Bran]

Udowodnij, że \(\displaystyle{ 2^n \nmid 3^n + 1}\) dla wszystkich naturalnych \(\displaystyle{ n>1.}\)

[Gosda]

Dla nieparzystych \(n\) lemat 2 z pracy "

\(\displaystyle{ v_2(3^n + 1^n = v_2(3 + 1) = 2 < n}\)

[Premislav]

Dla \(\displaystyle{ n}\) parzystego jest nawet \(\displaystyle{ 3^{n}+1\equiv 2\pmod{8}}\), więc nie zachodzi nawet podzielność przez cztery. Ciekawiej jest dla nieparzystego. Tutaj niestety nie poradziłem sobie bez twierdzenia Eulera. Mamy \(\displaystyle{ \varphi\left(2^{n}\right)=2^{n-1}}\) i \(\displaystyle{ \NWD(2,3)=1}\), więc z twierdzenia Eulera jest \(\displaystyle{ 3^{2^{n-1}}\equiv 1\pmod{2^{n}}}\). Stąd łatwo płynie wniosek, że jeśli \(\displaystyle{ r}\) jest rzędem \(\displaystyle{ 3}\) modulo \(\displaystyle{ 2^{n}}\), to \(\displaystyle{ r}\) dzieli \(\displaystyle{ 2^{n-1}}\).
Przypuśćmy nie wprost, że dla pewnego nieparzystego \(\displaystyle{ n}\) jest \(\displaystyle{ 3^{n}+1\equiv 0\pmod{2^{n}}}\), wówczas łatwo dostajemy
\(\displaystyle{ 3^{2n}\equiv 1\pmod{2^{n}}}\), czyli \(\displaystyle{ r|2n}\), ale skoro mamy również \(\displaystyle{ r|2^{n-1}}\) i \(\displaystyle{ n}\) jest nieparzyste, to \(\displaystyle{ r=1}\) lub \(\displaystyle{ r=2}\), ale to jest nieprawdą dla \(\displaystyle{ n>2}\).

[Janusz Tracz]

\(\displaystyle{ v_2(3^n + 1^n)= v_2(3 + 1) = 2 < n}\)

Trzeba jeszcze poczynić dwa stosunkowo proste ale ważne spostrzeżenia:

\(\displaystyle{ 1)}\) Dla nieparzystego \(\displaystyle{ n}\) mamy \(\displaystyle{ v_2(n)=0}\).

\(\displaystyle{ 2)}\) Zachodzi równoważność \(\displaystyle{ a|b \Leftrightarrow (\forall p) v_p(a) \le v_p(b) }\).

[a4karo]

Wspomagam Premislava

\(\displaystyle{ 3^{2n+1}+1=9^n\cdot 3+1=(8+1)^n\cdot 3+1=3(8k+1)+1=24k+4}\)
a to się nie dzieli przez `8`