Question

For any odd integer n, show that 3 divides 2ⁿ+1.

That is 2 to the nth power, not 2 times n

Answer 1

Using Mathematical Induction

2^n +1 is divisible by 3 for all odd integers n >= 1

Base Case:

Let n = 1,

LHS = 2^1 + 1 = 3

3 is divisible by 3.

The statement is true for n = 1.

Let the statement be true for k'th odd integer = (2k-1)

That is, 2^(2k-1) + 1 is divisible by 3.

=> 2^(2k-1) + 1 = 3p

=> 2^(2k-1) = 3p - 1

Consider the statement for (k+1)'th odd integer = (2k+1)

LHS = 2^(2k+1) + 1 = 2^(2k-1 + 2) + 1 = 2^(2k-1) * 2^2 + 1 = (3p-1)*4 + 1 = 3p*4 + 3 = 3*(4p + 1)

3*(4p + 1) is divisible by 3.

=> 2^(2k+1) + 1 is divisible by 3

The statement is true for (k+1)'th odd integer,

The statement is true for all odd integers n >=1