Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

6 Answers 6

up vote 32 down vote accepted

$$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$.
share|improve this answer

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

share|improve this answer
    
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.

share|improve this answer
    
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$.

share|improve this answer

Start with the base case

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

share|improve this answer

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

share|improve this answer
    
$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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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