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

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.

• You are not asking the same question. The link you gave has a different question. Further, the statement you wrote is incorrect too. It is not divisible if you take n=1 (I don't know about the rest though!). – Ankit Kumar Oct 25 '18 at 5:56
• I apologize I made a couple edits to clarify and corrected to the right question – Arnold Joseph Oct 25 '18 at 5:59

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})$$

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$$

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}

• deserves an upvote! – Maged Saeed Oct 25 '18 at 12:48
• I'm not very familiar with congruence. How did you go from the second congruence to the the third one? – Arnold Joseph Oct 25 '18 at 14:58
• $121\equiv 133-12\equiv -12 \pmod{133}$ and $144\equiv 133+11\equiv 11 \pmod{133}$. – farruhota Oct 25 '18 at 16:03

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}$$

Like

or

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$$