I was working on training for higher levels of mathematics olympiads and the problem was an application of the Euler-Fermat theorem, yet it left one computing: $2^{10}+3^{10} \bmod 13$ after having used reductions with $\phi(13)=12$ on both exponents. We end up wanting to prove: $$ 2^{10}+3^{10}\equiv 0 \bmod 13$$ One can solve this by the method of repeated squares, but looking at the numbers, one has: $2^2+3^2\equiv 0$, and $-2\equiv 10 \bmod \phi(13)$.
In general, I was wondering: if $\gcd(a,c)=\gcd(b,c)=1$, when does it hold that $$ a^n+b^n\equiv a^{\phi(c)-n}+b^{\phi(c)-n} \bmod c? $$ If this is the case, one has $2+a^{\phi(c)-n}\ast b^n+b^{\phi(c)-n}\ast a^n\equiv 0\bmod c$, but even though I looked into this, I was not able to determine more. Any help on this?
The general formula you have is $$a^n\equiv a^{n\bmod\varphi(c)}\mod c$$ For the problem at hand, you have $\;a^{10}\equiv a^{-2}\equiv(a^{-1})^2\mod 13$ for any $a$ not divisible by $13$.
Specifically, as $2^{-1}\equiv7$ and $3^{-1}\equiv -4$, you obtain $$2^{10}+3^{10}\equiv7^2+(-4)^2\equiv10+3 \mod 13.$$