Question

what is the best way to prove 7^k + 2^(2k+1) is always divisible by 3

Answer 1

\[7^{k} + 2^{2k+1}\]
I've been trying by induction, but can't quite get it.Any help much appreciated

Answer 2

first i show that for n =1 its true i.e 7 + 2^3 = 15, divisible by 3
then assume true for k, it should be true for
\[7^{k+1} + 2^{2(k+1)+1)}\]
however what to do next?

Answer 3

first, the base case:

k = 1: 7^1 + 2^(2+1) = 7 + 8 = 15, which is divisible by 3

now assume 7^k + 2^(2k+1) is divisible by 3

ie for some integer b, 7^k + 2^(2k + 1) = 3b

now we need to show that for some arbitrary integer d:

7^(k+1) + 2^(2(k+1) + 1) = 3d

7^(k+1) + 2^(2(k+1) + 1) = 7*7^k + 2^(2k+1+2)

= 7*7^k + 4*2^(2k+1)

= 3*7^k + 4*7^k + 4*2^(2k+1)

= 3*7^k + 4[7^k + 2^(2k+1)]

= 3*7^k + 4*3b

= 3*7^k + 12b

= 3[7^k + 4b]

Since 7^k is an integer, and 4b is an integer, then 7^k + 4b is integer

hence we have proven that 7^(k+1) + 2^(2(k+1) + 1) = 3d, for some
arbitrary integer d

completes our proof of induction

Answer 4

\[7\equiv 1\enspace\,(mod\enspace3)\quad\Rightarrow\quad 7^k\equiv 1^k\enspace\,(mod\enspace3)\quad\Rightarrow\quad 7^k\equiv 1\enspace\,(mod\enspace3)\]
\[2^2\equiv 1\enspace\,(mod\enspace3)\quad\Rightarrow\quad 2^{2k}\equiv 1^k\enspace\,(mod\enspace3)\quad\Rightarrow\quad 2^{2k}\equiv 1\enspace\,(mod\enspace3)\]
\[\Rightarrow\quad 2^{2k+1}\equiv 2\enspace\,(mod\enspace3)\]
Finally,
\[7^k+2^{2k+1}\equiv 1+2\equiv 0\enspace(mod\enspace 3)\]
proof without induction

Answer 5

fantastic - thanks for the help

Answer 6

yeah, nikvist's proof is very elegant if you want to use modular arithmetic