Show that $11^{n+1}+12^{2n-1}$ is divisible by $133$.

Solution 1:

$$11^{(n+1)+1} + 12^{2(n+1)-1} = 11 \cdot 11^{n+1} + 144 \cdot 12^{2n-1} = 11 \left(11^{n+1} + 12^{2n-1}\right) + 133 \cdot 12^{2n-1}$$

• $11 \left(11^{n+1} + 12^{2n-1}\right)$ is divisible by 133 by the induction hypothesis.
• $133 \cdot 12^{2n-1}$ is clearly a multiple of $133$.

Solution 2:

In fact, we can prove a stronger result and the proof is easier. The result we will prove is that $$x^2+x+1 \text{ divides }x^{n+1} + (x+1)^{2n-1}$$ for all $n \in \mathbb{N}$. Setting $x=11$ gives the result, you are looking for.

The proof follows immediately from the remainder theorem since $(x^2+x+1) = (x-\omega)(x-\omega^2)$, where $\omega$ is the complex cube-root of unity.

(Remember that $(x-a)$ divides $f(x)$ if and only if $f(x) = 0$)

Plugging in $\omega$ in $x^{n+1} + (x+1)^{2n-1}$ gives us $$\omega^{n+1} + (\omega+1)^{2n-1} = \omega^{n+1} + (-\omega^2)^{2n-1} = \omega^{n+1} - \omega^{4n-2} = \omega^{n+1} - \omega^{3n} \omega^{n-2}\\ =\omega^{n+1} - 1 \times \omega^{n-2} = \omega^{n-2} \left( \omega^3 - 1\right) = 0$$

This gives us that $(x- \omega)$ divides $x^{n+1} + (x+1)^{2n-1}$.

Similarly, plugging in $\omega^2$ in $x^{n+1} + (x+1)^{2n-1}$ gives us $$\omega^{2n+2} + \left( \omega^2 + 1 \right)^{2n-1} = \omega^{2n+2} + (-\omega)^{2n-1} = \omega^{2n+2} - \omega^{2n-1}\\ = \omega^{2n-1} \left( \omega^3 - 1\right) = 0$$ This gives us that $(x- \omega^2)$ divides $x^{n+1} + (x+1)^{2n-1}$.

Hence, $(x-\omega)(x-\omega^2) = x^2 + x + 1$ divides $x^{n+1} + (x+1)^{2n-1}$.

Setting $x=11$ gives us the result you want i.e. $11^2 + 11 + 1 = 133$ divides $11^{n+1} + 12^{2n-1}$.

Note that the above result can also be proved by inducting on $n$.