Proof by induction that $ 169 \mid 3^{3n+3}-26n-27$

Solution 1:

Hint $\ $ Conceptually, the induction is simply the first two terms of BT = Binomial Theorem:

${\rm mod}\,\ 26^2\!:\ \color{#c00}{(1\!+\!26)^{n+1}}\!\equiv 1\!+\!(n\!+\!1)26\equiv \color{#0a0}{26n\!+\!27}\,\Rightarrow\, 13^2\mid26^2\mid \color{#c00}{27^{n+1}}\!\color{#0a0}{-\!26n\!-\!27}$

Remark $ $ For completeness, below is the simple inductive proof of the first two terms of BT.

$\begin{align}{\rm mod}\,\ \color{#c00}{a^2}\!:\,\ (1+ a)^{\large n}\ \, \ \ \equiv&\,\ \ 1 + na\qquad\qquad\,\ \ \ \ \ {\rm i.e.}\ \ P(n)\\ \Rightarrow\ \ (1+a)^{\color{}{\large n+1}}\! \equiv &\ (1+na)(1 + a)\quad\ \ \ \ {\rm by}\ \ 1+a \ \ \rm times\ prior\\ \equiv &\,\ \ 1+ na+a+n\color{#c00}{a^2},\, \ \text{but }\ \color{#c00}{a^2\equiv 0}\ \ \rm so\\[1pt] \equiv &\,\ \ 1\!+\! (n\!+\!1)a\qquad\ \ \ \ \ \ {\rm i.e.}\ \ P(\color{}{n\!+\!1}) \end{align}$

Generalization $ $ Using the above idea it is easy to generalize, e.g. from this answer

$\!\begin{align}\rm{\bf Theorem}\ \ \forall n\in\Bbb N\!:\ d\mid f(n) = a^n\! + b\:\!n + c &\rm \iff d\mid \color{blue}{(a\!-\!1)^2},\, \color{brown}{a\!+\!b\!-\!1},\, \color{darkorange}{1\!+\!c}\\ &\rm \iff d\mid f(0),\,f(1),\,f(2)\end{align}$

Solution 2:

This is what you should have done instead: $$\begin{align}27\cdot3^{3n+3}-26n-27-26&=27(3^{3n+3}-26n-27)+27\cdot26n+27\cdot27-26n-27-26\\&=27\cdot169m+26\cdot26n-26\cdot26\end{align}$$

Here's the proof more clearly without unnecessary variables: $$\begin{align}13^2&\mid3^{3(n+1)+3}-26(n+1)-27\\13^2&\mid27\cdot3^{3n+3}-26n-27-26\\13^2&\mid27(3^{3n+3}-26n-27)+26\cdot26n+26\cdot27-26\\13^2&\mid13^2\cdot4n+13^2\cdot4\end{align}$$ You use the induction hypothesis in the 3rd row.

Solution 3:

I'm not sure if you are mixing up what is given and what is to be proved - perhaps you are just not writing your working very clearly. For the induction step you have to assume that $$3^{3n+3}-26n-27=169x$$ for some integer $x$, and then you have to prove that $$3^{3n+6}-26n-27-26$$ is $169$ times some integer (not necessarily $x$, just some integer). The best way to do this would be to note that by assumption $$3^{3n+3}=169x+26n+27\ ,$$ and therefore the required expression can be written $$\eqalign{3^{3n+6}-26n-27-26 &=3^3(3^{3n+3})-26n-27-26\cr &=27(169x+26n+27)-26n-27-26\cr &=27\times169x+(27\times26-26)n+(27^2-2\times27+1)\ .\cr}$$ Remembering that $169=13^2$, can you see why this is $169$ times an integer? For the "nicest" proof, see if you can do it without lots of calculations, and in particular without using a calculator.

Solution 4:

The same, but using modules.

Let's prove by induction that $3^{3n+3} - 26n - 27 \equiv 0 \pmod {169}$

Working with module $169$:

• Base case. If $n = 1$, then $3^3 - 27 \equiv 0$.

• Induction. Let fix an integer $m \geq 0$ and supose that (induction hypothesis): $$3^{3m+3}-26m -27 \equiv 0 \pmod{169}$$ or, with other words: $$3^{3m+3} \equiv 27 + 26m \pmod{169}$$ We want to prove that $$3^{3m+6}-26(m+1) -27 \equiv 0 \pmod{169}$$

Prove:

$$\begin{align}3^{3m+6}-26(m+1)-27&\equiv 3^3 \cdot 3^{3m+3} - 26m - 26 -27\\ &\equiv 27 \cdot 3^{3m+3} - 26m -26-27\quad(*)\\ &\equiv 27(27+26m) - 26m - 26 -27\\ &\equiv (702-26)m + (729-27-26)\\ &\equiv 4\cdot 169m + 4 \cdot 169\\ &\equiv 0m + 0 \\ &\equiv 0 \end{align}$$

We have applied induction hypothesis at $(*)$.

So, as we have proved that $3^{3n+3} - 26n - 27 \equiv 0 \pmod {169}$, then, $169 | 3^{3n+3} - 26n - 27$.