(i) Note that 3³= 2 x 13 + 1, therefore 3³ – 1 is a multiple of 13.

This means that if k is a multiple of 3 (say k = 3m), 3^k – 1 is a multiple of 13, because we can factorise:

3^3m – 1 = (3³)^m – 1 = (3³ – 1) ((3³)^m-1 - (3³)^m-2 + (3³)^m-3 - … (-1)^m-2 3³ + (-1)^m-1 )

If k is not a multiple of 3, then k = 3m + r, where r = 1 or r = 2.

Case 1: k = 3m + 1

3^{3m + 1} – 1 = 3(3^3m – 1) + 2 = 3 x (a multiple of 13) + 2, so 3^{3m + 1} – 1 is two more than a multiple of 13.

Case 2: k = 3m + 2

3^{3m + 2} – 1 = 9(3^3m – 1) + 8 = 3 x (a multiple of 13) + 8, so 3^{3m + 2} – 1 is eight more than a multiple of 13.

So 3^k – 1 is a multiple of 13 if and only if k is a multiple of 3.

(ii)

Using the same approach as in (i), we can examine three cases, as k will always be either 3m, 3m + 1 or 3m + 2 for some value of m.

Case 1: k = 3m

3^3m + 1 = (3^3m – 1) + 2 = (a multiple of 13) + 2, so 3^3m + 1 is two more than a multiple of 13.

Case 2: k = 3m + 1

3^{3m + 1} + 1 = 3(3^3m – 1) + 5 = 3 x (a multiple of 13) + 5, so 3^{3m + 1} + 1 is five more than a multiple of 13.

Case 3: k = 3m + 2

3^{3m + 2} + 1 = 9(3^3m – 1) + 10 = 3 x (a multiple of 13) + 10, so 3^{3m + 2}+ 1 is ten more than a multiple of 13.

So 3^k + 1 is never a multiple of 13.

Challenge 281: Two Thirteen Things