How to prove that for all natural $n$, $133|11^{n+2}+12^{2n+1}$

Question

How to prove that for every natural $n$, the number $$11^{n+2} +12^{2n+1}$$ is divisible by $133$?

I tried Induction method, so assuming that $$ n=k \implies A = (11^{k+2} +12^{2k+1} ) \pmod{133} \equiv 0 $$ Then trying to prove that $$ n=k+1 \implies B = (11^{k+3} +12^{2k+3} ) \pmod{133} \equiv 0 $$ For this I wanted to split $B$ into multiplication with at least one multiple of $A$. But no luck.

Any Ideas?

Answer 1

Given that $11^{k+2}+12^{2k+1}=133\lambda$, you can infer that $11^{k+2}=133\lambda-12^{2k+1}$.

Thus you have that $$11^{k+3}+12^{2k+3}= 11^{k+2}\cdot 11 +144 \cdot 12^{2k+1}=11\cdot 133\lambda -11\cdot 12^{2k+1} +144 \cdot 12^{2k+1} =11\cdot 133\lambda +12^{2k+1} \cdot (144-11)=11\cdot 133\lambda +133\cdot 12^{k+1} $$ which is divisible by 133

Answer 2

HINT

Note that $133 = 7 \times 19$ and both $7$ and $19$ are prime. Also recall that if $p,q$ are prime, and $n \in \mathbb{N}$, and $p|n$ and $q|n$ then $pq|n$.

Answer 3

$11,144$ are roots of the quadratic $$(n-11)(n-144)=n^2-155n+1584$$

Therefore your sequence $$a_n=121\times 11^n+12\times 144^n$$ satisfies the recursion $$a_{n+1}=155a_{n+1}-1584a_n$$

The initial values are $$a_0=133\quad a_1=3059$$ and both of these are divisible by $133$ so we are done.

Note: It wasn't necessary to exhibit the linear recursion as it was clear that there was one like that and that's all we needed.

Answer 4

Just calculate mod $133$:

$$11^{n+2}+12^{2n+1} = 121\cdot 11^n +12\cdot 144^n $$ $$\equiv 121\cdot 11^n + 12\cdot 11^n \equiv 133\cdot 11^n \equiv 0 \pmod{133}.$$

Answer 5

$\displaystyle 11^{k + 3} + 12^{2k + 3} = 11 \times 11^{k + 2} + \underbrace{\qquad 144\qquad}_{\displaystyle =\ 133 + 11} \times 12^{2k + 1} = 11\left(\color{red}{11^{k + 2} + 12^{2k + 1}}\right) + \color{red}{133} \times 12^{2k + 1}$