I'm trying to prove what he title says. I've found that (i'll type it that way for the sake of using less code i.e using $\vert$ instead of the congruence symbol) $13 \vert 3^3 -1$ and that $13 \vert 4^3 +1$. I know by the congruence properties that $13 \vert 4^3 + 3^3$ However I don't know how to follow from there, I multiplied by $3^{102}$$4^{102}$ and got that $13 \vert 3^{102} 4^{105}+ 3^{105}4^{102}$ but I don't think this will help me with something. Any help will be appreciated.
$\endgroup$ 24 Answers
$\begingroup$$3^{105} = (3^{3})^{35} = (27)^{35} \equiv (1)^{35}(\bmod\; 13) = 1$
$4^{105} = (4^{3})^{35} = (64)^{35} \equiv (-1)^{35}(\bmod\; 13) = -1$
Adding both we have
$1+(-1)=0$
QED.
$\endgroup$ 3 $\begingroup$$$3^{105} + 4^{105} = (3^3)^{35} + (4^5)^{21} = 27^{35} + 1024^{21} \equiv 1^{35} + (-3)^{21} = 1 + (-1)(3^3)^7 \\ \equiv -1 + 1 = 0 \pmod {13}$$
$\endgroup$ $\begingroup$Following your way, it is sufficient to establish $$(3^3)^{35}+(4^3)^{35}$$ is divisible by $3^3+4^3$ which is evident from Proof of $a^n+b^n$ divisible by a+b when n is odd
$\endgroup$ $\begingroup$You can also say that if $n$ is a natural number and divisible by 3, say $n=3k$ with $k$ odd, then:
$$3^{n}+4^{n}=3^{3k}+4^{3k}=(3^{3})^{k}+(4^{3})^{k}=27^k+64^k\equiv 1^k+(-1)^k=0\,(\ {\rm mod}\ 13)$$
because: $\ 27\equiv 1 ({\rm mod}\ 13)$ and $\ 64\equiv -1 ({\rm mod}\ 13)$
$\endgroup$ 2
