Prove that the number 3^105+4^105 is divisible with 91 but not with 11.
Hello, Garas!
I have half of it . . .
$\displaystyle \text{Theorem: }\:\text{If }n\text{ is odd, then }a^n + b^n\text{ can be factored.}$$\displaystyle \text{Prove that the number }\,N \:=\:3^{105}+4^{105}\,\text{ is divisible by 91, but not by 11.}$
. . . . . . . . $\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.
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.