0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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!). $\endgroup$ – Ankit Kumar Oct 25 '18 at 5:56
  • $\begingroup$ I apologize I made a couple edits to clarify and corrected to the right question $\endgroup$ – Arnold Joseph Oct 25 '18 at 5:59
0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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$$
$\endgroup$
2
$\begingroup$

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

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

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.