Number theory textbook exercise $11^{n+2} + 12^{2n + 1}$

Question

I have been stuck on proving the equation $11^{n+2} + 12^{2n+1}$ is divisible by $133$ for all positive counting integers $N$. The proof should ideally use induction and I'm not sure how to proceed through the inductive step

It's asking something like this problem: Show that this expression is divisible by $133$ [more info in desc.]

but I'm not sure how the modulo are derived equal and I would like to use induction.

Answer 1

Induction Step:

$11^{n+2} + 12^{2n+1} = 133*k$

and

$11^{(n+1)+2} + 12^{2(n+1) + 1} =$

$11^{(n+2)+1} + 12^{(2n+1) + 2}=$

$11^{n+2}*11 + 12^{2n+1}*144 =$

$11^{n+2}+ 12^{2n+1}*11 + 12^{2n+1}*133 =$

$(11^{n+2} + 12^{2n+1})*11 + 12^{2n+1}*133 =$

$[133*k]*11 + 12^{2n+1}*133 = $

$133 \times (11k + 12^{2n+1})$.

....

If you want to be slick an look like a magician take the above and do it backwards:

$11^{n+2} + 12^{2n+1} = 133*k$

$(11^{n+2} + 12^{2n+1})11 = 133*(11k)$

$11^{n+3} + 12^{2n+1}*11 = 133*(11k)$

$11^{n+3} + 12^{2n+1}*11 + 12^{2n+1}*133 = 133*(11k) + 133*12^{2n+1}$

$11^{n+3} + 12^{2n+1}(11 + 133) = 133(11k + 12^{2n+1})$

$11^{n+3} + 12^{2n+1}*144 = 133(11k + 12^{2n+1})$

$11^{n+3} + 12^{2n+1}*12^2 = 11^{n+3} + 12^{2n+3} = 133(11k + 12^{2n+1})$

$11^{(n+2) + 1} + 12^{2(n+1) + 1} = 133(11k + 12^{2n+1})$

Answer 2

Note that $11\cdot 12 =132 \equiv -1 \pmod {133}$. They also use $144 \equiv 11 \pmod {133}$. That should get you through the chain in the linked question.

To do an inductive proof, note that for $n=1$ we have $11^3+12^3=3059 \equiv 0 \pmod {133}$. Then assume it is true for $k$, and we have $$11^{k+2}+12^{2k+1}\equiv 0 \pmod {133}\\ 11^{k+3}+12^{2k+3}=11\cdot 11^{k+2}+144\cdot 12^{2k+1}\\\equiv 11\cdot(11^{k+2}+12^{2k+1})\equiv 0 \pmod {133}$$

Answer 3

The induction step $n \rightarrow n+1$ without modular arithmetic may look as follows:

• Induction hypothesis (IH): $133 | (11^{n+2} + 12^{2n+1}) \Leftrightarrow 11^{n+2} + 12^{2n+1} = 133 \cdot k$ for a $k \in \mathbb{N}$
• Induction step: $$11^{n+3} + 12^{2n+3} = 11\cdot 11^{n+2} + 144\cdot 12^{2n+1}= 11\cdot 11^{n+2} + (133+11)\cdot 12^{2n+1} $$ $$= 133\cdot 12^{2n+1} + 11(11^{n+2} + 12^{2n+1}) \stackrel{IH}{=} 133\cdot 12^{2n+1} + 133 \cdot k$$

Answer 4

Like

Prove by induction that $3^{3n+1} + 2^{n+1}$ is divisible by 5

or

Proving that $64$ divides $3^{2n+2}+56n+55$ by induction,

If $P(m)=11^{m+2}+12^{2m+1}$

$$P(n+1)-11P(n)=12^{2n+1}(12^2-11)$$ which is divisible by $133$

Or $P(m+1)-12^2P(m)=11^{n+2}(11-12^2)$ which is divisible by $133$

In either case,

$133|P(n+1)\iff133|P(n)$ as $(11,133)=(12,133)=1$

Answer 5

Without induction, consider mod $133$: $$\begin{align}11^{n+2} + 12^{2n+1}&\equiv 121\cdot 11^{n} + 12\cdot 144^{n}\equiv \\ &\equiv (-12)\cdot 11^n+12\cdot 11^n\\ &\equiv 0 \pmod{133}.\end{align}$$