Solving a Number Theory Problem Using Fermat's Little Theorem

[ehrenfest]

Homework Statement

http://math.stanford.edu/~vakil/putnam07/07putnam2.pdf

I am working on number 2.
So I want to find 2^70 + 3^70 mod 13.
I can use Fermat's Little Theorem to reduce the exponent to 10, but I do not know what to do next...

Homework Equations

The Attempt at a Solution

 

[morphism]

2^2 = 4 and 3^2 = 9

and 4^5 + 9^5 = (4+9)*something.

 

[ehrenfest]

4^5 + 9^5 = (4+9)*something.

Is that true? Where does that come from?

 

[morphism]

You know how there's a formula for a^n - b^n? Well, there's also one for a^n + b^n when n is odd. (a^n + b^n = a^n - (-b)^n.)

 

[ehrenfest]

I see. Thanks.