matematikk.net

Vis at $7 \mid 4^{3k+1}+2^{3k+1}+1$, der $k \in \mathbb{N}$

Induksjon:
[tex]P_1:\: 7|4^4+2^4+1=256+16+1=259+14=7\cdot 39[/tex], som stemmer (kunne forsåvidt brukt [tex]P_0:\: 7|7[/tex]).
Antar [tex]P_k: 7|4^{3k+1}+2^{3k+1}+1[/tex], og må med det bevise [tex]P_{k+1}:\: 7|4^{3(k+1)+1}+2^{3(k+1)+1}+1[/tex].

Vet altså at [tex]4^{3k+1}+2^{3k+1}\equiv _7 -1[/tex], og må bevise at kongruensen beholdes når eksponentene økes med tre.
[tex]4^{3(k+1)+1}+2^{3(k+1)+1}=2^{3k+4}(2^{3k+4}+1)=8\cdot 2^{3k+1}(8\cdot 2^{3k+1}+1)\equiv 2^{3k+1}(7\cdot 2^{3k+1}+2^{3k+1}+1)\equiv 2^{3k+1}(2^{3k+1}+1)\equiv -1[/tex]
som var det vi ville vise.

Ser bra ut det der! Fin løsning.

Alternativt:
La $x=2^{3k+1}$. Da er $x^2=4^{3k+1}$ og vi ser da på kongruenslikningen $x^2+x+1 \equiv 0 \pmod 7$.
Videre er $2^{3k+1}=2 \cdot 8^k$, og $8 \equiv 1 \pmod 7 \enspace \Longrightarrow \enspace 8^k \equiv 1^k \equiv 1 \pmod 7 \enspace \Longrightarrow \enspace x\equiv 2 \cdot 8^k \equiv 2 \pmod 7$.
Og da følger det at $x^2 \equiv 2^2 \equiv 4 \pmod 7$.
Og kongruenslikningen blir $x^2+x+1 \equiv 4+2+1 \equiv 7 \equiv 0 \pmod 7 \enspace \Longrightarrow \enspace 7 \mid 4^{3x+1} + 2^{3x+1} + 1 \enspace \forall x \in \mathbb{N} \enspace \enspace \blacksquare$