Prove that $133$ divides $11^{n+1} + 12^{2n−1}$ for all $n > 1$?

Question

I have tried this question so hard but still stuck here. It seems like easily provable if all $n$ are all positive numbers but in this question, the $n$ is bigger than $1$.

original question : prove that for all n>1, 133 | (11^(n+1) + 12^(2n - 1))

Thanks for all the answers. but this question is from a Math class handout and the solution is supposed to be gained through Strong Induction. Are there any thoughts on that? Thank you guys so much.

Answer 1

Let $n=m+1$. Then we are looking at $11^{m+2}+12^{2m+1}$.

Note that $11^{m+2}=11^2 \cdot 11^{m}=121\cdot 11^m\equiv -12 \cdot 11^m\pmod{133}$.

Also, $12^{2m+1}= 12 (144)^m\equiv 12\cdot 11^m\pmod{133}$.

This completes the proof.

The congruence also holds at $n=1$.

Answer 2

$\displaystyle {\rm mod}\ i^2\!+\!i\!+\!1\!:\ \color{#c00}{(i\!+\!1)^{2n-1}}\!\equiv \frac{(i^2\!+\!2i\!+\!1)^n}{i\!+\!1}\equiv \frac{i^n}{i\!+\!1}\equiv\frac{i\cdot i^{n}\ \ \ }{i\,(i\!+\!1)}\equiv\frac{\color{#0a0}{i^{n+1}}}{-1\ }\Rightarrow\, \color{#0a0}{i^{n+1}}\!+\!\color{#c00}{(i\!+\!1)^{2n-1}}\!\equiv 0$

Answer 3

Alternatively, let

$$S = 11^{n + 1} + 12^{2n-1}$$ $$\implies12S = 132\cdot11^n + 144^n$$

Then, we have $$\begin{align}12S &\equiv -1\cdot11^n + 11^n \pmod{133}\\ &\equiv 0 \pmod {133}\end{align}$$

Since $133 | 12S$ but $GCD(12, 133) = 1$, then it is necessary that $133 | S$. This is in fact a generalization of Euclid's Lemma: If $a$ and $b$ are coprime and $a$ divides the product $bc$, then $a$ divides $c$.

Answer 4

For $n=1$

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

So, its true for $n=1$

Let us assume it is true for $n=k$

$\implies 11^{k+1}+12^{2k-1}=133s$

for some integer $s$

$\implies 12^{2k-1}=133s-11^{k+1}$

$\implies 12^{2k+1}=144(133s-11^{k+1})$

Now for $n=k+1$

$11^{k+2}+12^{2k+1}$

$=11^{k+2}+144(133s-11^{k+1})$

$=11^{k+2}+144*133s-144*11^{k+1}$

$=11^{k+1}(11-144)+133*144s$

$=11^{k+1}(-133)+133*144s$

$=133(144s-11^{k+1})$

Which is a multiple of 133 , so its true for $n=k+1$

Thus by mathematical inducton it is true for all $n\in \mathbb N$