How do I prove that $3$ divides $14^{2n}-1$ by induction?

Question

How do I solve this?

Prove that $3$ divides $14^{2n} -1$ for all $n = 0,\,1,\,2,\,3,\,\ldots$

My calculations are:

Let $n=1$ then $3|14^{2*1}-1 \implies 3|196-1 \implies 3|195$ which is true

Now $n = k$ and assume $3|14^{2k}-1$

let $n = k + 1$

$3|14^{2(k+1)}-1 \implies 3|14^2*14^{k+1}-1$

and $3|14^2-1$ so $3|14^2*14^{k+1}-1$

which makes $3 | 14^{2n}$ true.

I tried starting with $n = 0$ as it's the smallest base but I couldn't get it to work.

Answer 1

You can certainly start with $n=0$ and save you a small calculation: $14^0-1=0$, and $3|0$.

I think your justification of the inductive step is a bit off. What you need to do is assume that $14^{2k}-1$ is a multiple of 3, and deduce that $14^{2(k+1)}-1$ is a multiple of 3.

So, if $14^{2k}-1=3h$, you have \begin{align} 14^{2(k+1)}-1&=196\times 14^{2k} -1=196\times 14^{2k}-196+196-1\\ \ \\ &=196(14^{2k}-1)+195=196\times 3h+3\times63=3(196h+63), \end{align} a multiple of 3. Then induction implies that $14^{2n}-1$ is a multiple of 3 for all $n\in\mathbb N$.

Answer 2

If $3|14^{2k}-1$ then $14^{2k}-1=3n$ for some integer $n$. This implies $14^{2k}=3n+1$. Use this to find $14^{2(k+1)}-1=14^2\cdot 14^{2k} - 1$; you should then be able to show that it is divisible by 3.

Answer 3

$\begin{align}{\bf Hint}\qquad\qquad\qquad\qquad\,\ \color{#c00}{14^{\large 2}} &=\,\ \color{#c00}{1\! +\! 3k}\\ 14^{\large 2N} &=\,\ 1\! +\! 3j\\ \Rightarrow\, 14^{\large 2(N+1)}\! = \color{#c00}{14^{\large 2}} 14^{\large 2N} &= (1\!+\!3j)(\color{#c00}{1\!+\!3k}) = 1\!+\!3n,\ {\rm for}\ \ n = j\!+\!k\!+\!3jk \end{align}$

---

Said mod $\,3\!:\ 14^{\large 2}\!\equiv 1\equiv 14^{\large 2N}\!\Rightarrow\, 14^{\large 2(N+1)}\equiv 14^{\large 2} 14^{\large 2N}\!\equiv 1\,$ by the Congruence Product Rule

Or, $ $ equivalently, $\ \left[14^{\large 2}\equiv 1\right]^{\large N}\!\Rightarrow\, 14^{\large 2N}\!\equiv 1^{\large N}\equiv 1\ $ by the Congruence Power Rule, which is an inductive extension of the Product Rule. Thus, using modular arithmetic simplifies the induction to an utterly trivial induction $\ 1^{\large N}\!\equiv\, 1$.