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

Problem taken from a paper on mathematical induction by Gerardo Con Diaz. Although it doesn't look like anything special, I have spent a considerable amount of time trying to crack this, with no luck. Most likely, due to the late hour, I am missing something very trivial here.

Prove that for any integer $n$, the number $11^{n+1}+12^{2n-1}$ is divisible by $133$.

I have tried multiplying through by $12$ and rearranging, but like I said with meager results. I arrived at $11^{n+2}+12^{2n+1}$ which satisfies the induction hypothesis for LHS, but for the RHS I got stuck at $12 \times 133m-11^{n+1}-11^{n+3}$ or $12^2 \times 133m-12 \times11^{n+1}-11^{n+3}$ and several other combinations none of which would let me factor out $133$.

-
Answers below are great, but isn't this proof formulated incorrectly? This is only true for the natural numbers, not integers, since $11 + 12^{-1} < 133$ –  Dancrumb May 29 '12 at 13:22
@Dancrumb I've copied the problem 'as is' from the paper, but it does indeed seem that what the author meant was "for any positive integer", so you're right! –  Milosz Wielondek May 29 '12 at 14:31

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

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

-
Interesting approach! How did you come up with the hypothesis, i.e. that $x^2+x+1 \text{ divides }x^{n+1} + (x+1)^{2n-1}$? It's not something that strikes me as acutely obvious :S –  Milosz Wielondek May 30 '12 at 11:01
@Milosz $11$ and $12$ are adjacent numbers and the $133$ is the what we get by setting $n=1$ i.e. $133 = 12^2 - 11$. Hence, if we want to generalize and replace $11$ by $x$, then $12$ becomes $x+1$ and $133 = (x+1)^2 - x = x^2 + x + 1$. –  user17762 May 30 '12 at 15:41

You had $12^2\cdot 133m-12\cdot11^{n+1}-11^{n+3}$? Then you were very close. Next note that $$-12\cdot11^{n+1}-11^{n+3}=-12\cdot 11^{n+1}-11^2\cdot 11^{n+1}=-(12+11^2)\cdot 11^{n+1}=-133\cdot 11^{n+1}$$ is a multiple of $133$.

$133$ is special here because $133=12^2-11 =11^2+12 = 11\cdot 12+1$. This generalizes to $m^2+m+1 = (m+1)^2-m = m(m+1)+1$, and $m^{n+1}+(m+1)^{2n-1}$ is divisible by $m^2+m+1$ when $m$ is an integer and $n$ is a positive integer.

-
If I may ask, why did you feel it was necessary to CW this? –  mixedmath May 29 '12 at 8:11
It wasn't necessary, I just felt like it. Feel free to edit. –  Jonas Meyer May 29 '12 at 15:48

We try to explain how to arrive mechanically at a calculation that works.

Let $P_{k}=11^{k+1} +12^{2k-1}$. Suppose that we know that $133$ divides $P_n$. We want to show that $133$ divides $P_{n+1}$.

If this is true, then $133$ must divide $aP_{n+1}-bP_n$ for any integers $a$ and $b$. Moreover, if we can find integers $a$ and $b$ such that $133$ divides $aP_{n+1}-bP_{n}$, with $a$ relatively prime to $133$, then we will know that $133$ divides $P_{n+1}$.

After all the semi-abstraction, let's do the details. We are looking at $$a\left(11^{n+2} +12^{2n+1}\right) -b\left(11^{n+1}+12^{2n-1}\right),\tag{1}$$ and want to choose $a$ and $b$ so that the expression $(1)$ is simple (and $a$ is relatively prime to $133$). There are two obvious choices that simplify $(1)$ a lot. These are $a=1$, $b=11$ and $a=1$, $b=12^2$. Each gives very pleasant cancellation.

Either choice works nicely. Let's use $a=1$, $b=12^2$. Then expression $(1)$ is equal to $$11^{n+2}-(144)11^{n+1}.$$ But this simplifies to $$11^{n+1}(11-144),$$ which certainly is divisible by $133$, so we are finished.

Remark: The above calculations were motivated by the Euclidean algorithm for calculating greatest common divisors, though one does not need to know this to use the procedure effectively. Note that versions of the procedure can be used in a mechanical way for any problem with the same basic structure.

Added: Marvis has given a nice argument using cube roots of unity that the polynomial $1+x+x^2$ divides $x^{n+1}+(1+x)^{2n-1}$. That can also be done by induction, with an argument that is insensitive to the underlying integral domain. In the language of the post above, choose $a=1$ and $b=(1+x)^2$. Then $$a\left(x^{n+2}+(1+x)^{2n+1}\right)-b\left(x^{n-1}+(1+x)^{2n-1}\right)$$ simplifies to $-(1+x+x^2)$, which is clearly divisible by $1+x+x^2$.

-

For $n=1$,

$11^2+12^1=133$ is divisible by $133$.

Move from $k=n$ to $k=n+1$.

\eqalign{ & {11^{n + 2}} + {12^{2n + 1}} = 11 \cdot {11^{n + 1}} + {12^2} \cdot {12^{2n - 1}} = 11 \cdot {11^{n + 1}} + \left( {133 + 11} \right) \cdot {12^{2n - 1}} \cr & 11 \cdot {11^{n + 1}} + 133 \cdot {12^{2n - 1}} + 11 \cdot {12^{2n - 1}} = 11 \cdot \left( {{{11}^{n + 1}} + {{12}^{2n - 1}}} \right) + 133 \cdot {12^{2n - 1}} \cr}

Thus it is true for all $n$.

-

could it be done by brute force ??

i mean you replace on every equation 'n' by $n=133k+m$ where k is an integer and 'm' rns $m=1,132$ and check that for every integer 'm' then $133k+m$ divides $11^{n-1}+12^{2n-1}$

-
$133k+m$ divides $11^{n-1}+12^{2n-1}$? You mean when $k=1$ and $m=0$ and $n$ is a positive integer? –  Jonas Meyer May 29 '12 at 17:30