Dowód podzielności dwóch potęg.

[Freddy Eliot]

Witajcie.
Mam problem z tym zadaniem:
Udowodnić, że \(\displaystyle{ 2^n}\) nie dzieli \(\displaystyle{ 3^n+1}\) dla dowolnej liczby całkowitej \(\displaystyle{ n>1.}\)
Próbowałam \(\displaystyle{ 3^n+1}\) rozbić przy pomocy wielomianu Newtona, ale nie wiele mi to pomogło.
Moglibyście rzucić jakiś pomysł?

Przepraszam, zapomniałam dodać 1.
W tym wypadku można udowodnić, że \(\displaystyle{ 3^n+1}\) dzieli się przez \(\displaystyle{ 2}\).

[octahedron]

Jeśli \(\displaystyle{ 2^n}\) dzieli \(\displaystyle{ 3^n}\), to również \(\displaystyle{ 2}\) dzieli. A łatwo pokazać, że tak nie jest.

[Vax]

Rozumiem, że miało być \(\displaystyle{ 2^n \nmid 3^n+1}\) dla dowolnego całkowitego \(\displaystyle{ n>1}\) ?

Załóżmy nie wprost, że dla pewnego \(\displaystyle{ n}\) teza nie zachodzi, ale wtedy dostajemy \(\displaystyle{ 3^n \equiv -1\pmod{4} \iff (-1)^n \equiv -1\pmod{4}}\), czyli \(\displaystyle{ n}\) jest nieparzyste, dodatkowo:

\(\displaystyle{ (*)3^n \equiv -1\pmod{2^n}/^2 \Rightarrow 3^{2n} \equiv 1\pmod{2^n}}\)

Niech \(\displaystyle{ t = ord_{2^n} 3}\), wówczas na mocy twierdzenia Eulera:

\(\displaystyle{ t \mid 2^{n-1}}\), stąd \(\displaystyle{ t = 2^k , k \ge 0}\), oraz z \(\displaystyle{ (*)}\) (\(\displaystyle{ n>1}\) więc \(\displaystyle{ -1 \not\equiv 1\pmod{2^n}}\)):

\(\displaystyle{ t \mid 2n \ \wedge \ t \nmid n}\)

Jednak skoro \(\displaystyle{ t}\) jest potęgą dwójki, a \(\displaystyle{ n}\) jest nieparzyste, to musi być \(\displaystyle{ t=2}\), skąd \(\displaystyle{ 3^2 \equiv 1\pmod{2^n} \iff 8 \equiv 0\pmod{2^n}}\), czyli \(\displaystyle{ n \le 3}\) i sprawdzamy ręcznie, że dla \(\displaystyle{ n=2 , n=3}\) teza zachodzi.