# Thread: 3^105+4^105 divisible with 91, not with 11

1. ## 3^105+4^105 divisible with 91, not with 11

Prove that the number 3^105+4^105 is divisible with 91 but not with 11.

2. ## Re: 3^105+4^105 divisible with 91, not with 11

Hello, Garas!

I have half of it . . .

$\displaystyle \text{Prove that the number }\,N \:=\:3^{105}+4^{105}\,\text{ is divisible by 91, but not by 11.}$
$\displaystyle \text{Theorem: }\:\text{If }n\text{ is odd, then }a^n + b^n\text{ can be factored.}$

. . . . . . . . $\displaystyle a^n + b^n \;=\;(a+b)\left(a^{n-1} - a^{n-2}b + a^{n-3}b^2 + \hdots - ab^{n-2} + b^{n-1}\right)$

$\displaystyle N \;=\;3^{105} + 4^{104}$

n . $\displaystyle =\;(3^3)^{35} + (4^3)^{35}$

n . $\displaystyle =\;\underbrace{[3^3 + 4^3]}\,\bigg[(3^3)^{34} - (3^3)^{33}(4^3) + (3^3)^{32}(4^3)^2 - \hdots - (3^3)(4^3)^{33} + (4^3)^{34}\bigg]$
n . $\displaystyle =\quad\;\; 91\,\bigg[(3^3)^{34} - (3^3)^{33}(4^3) + (3^3)^{32}(4^3)^2 - \hdots - (3^3)(4^3)^{33} + (4^3)^{34}\bigg]$

Therefore, $\displaystyle N$ is divisible by 91.

3. ## Re: 3^105+4^105 divisible with 91, not with 11

What are the remainders when powers of 3 are divided by 11?

$\displaystyle \begin{array}{r|cccccccccc}\text{Power of 3}&3&9&27&81&243&729&2187&6561&19683&59049\\ \text{Remainder}&3&9&5&4&1&3&9&5&4&1\end{array}$

Looks like there's a pattern there! Now do the same thing for powers of 4:

$\displaystyle \begin{array}{r|cccccccc}\text{Power of 4}&4&16&64&256&1024&4096&16384&\ldots\\ \text{Remainder}&4&5&9&3&1&4&5&\ldots\end{array}$

Similar pattern, repeating in batches of five.

Try to prove why this pattern occurs, then notice that at the 105th stage the sum of the remainders is not 0.