Prove that the integer $A= 3^{3n+3}- 36n - 27$ is divisible by $169$ for all positive integers $n$.

Question

$A=3^{3n+3}- 36n - 27$ is divisible by $169$

So, would the first step, or basic step, be n= alpha S(alpha)=T?

How would the set up for the second step, or inductive step, be?

Answer 1

Let your expression be $A_n=...$

Step 1: Show that $A_1$ is divisible by 169.

Step 2: Suppose that the statement is true for $A_n$. Find an expression for $A_{n+1}$ in terms of $n$. You want to show that $A_{n+1}$ and $A_n$ are related in a way that gives the multiple of 169.

Note that the expression for $A_n$ can be rewritten as $3^{3n+3}=A_n+26n+27$

Consider $A_{n+1}=3^{3(n+1)+3}-26(n+1)-27=3^{3n+3+3}-26n-26-27=3^3\times 3^{3n+3}-26n-53$

So $A_{n+1}=27\times (A_n+26n+27)-26n-53$

You have already supposeed that $A_n$ is a multiple of $169$ so rewrite $A_n=169m$

See where that takes you...

Answer 2

I found the claim surprising, so I checked for n = 0 (true) and n = 1 (false). If it had been true for n = 1 and at least n = 2, I would have made a table of $3^{3n+3}$ = $27^{n+1}$ modulo 169 and checked that the result grows by 36 (modulo 169) until the values repeat.

The values are: 27, 53, 79, 105, ... Looks suspiciously like growth by 26.

26 x 27 = 702 = 4 x 169 + 26. So indeed $3^{3n+3}$ modulo 169 grows by 26 when n grows by 1, so the correct theorem is $3^{3n+3} = 26n + 27$ (modulo 169).