Remainder when 29 divides $3^{2002} + 7^{2002} + 2002$

Question

My attempt:

We note that-

$2002 \equiv 1$ (mod $29$)

$3^{2002}\equiv 3^{14}$ (mod $29$)

$7^{2002}\equiv 7^{14}$ (mod $29$) [From Fermat]

Now, how do I reduce $3^{14}$ and $7^{14}$?

Answer 1

Using Proof of $a^n+b^n$ divisible by $a+b$ when $n$ is odd

$$3^{2002}+7^{2002}=(3^2)^{1001}+(7^2)^{1001}$$ is divisible by $3^2+7^2$

Answer 2

To answer your original question, "Now, how do I reduce $3^{14}$ and $7^{14}$''

One approach would be (should you forget the theorem of a previous answer):

$$ 3^{14} \equiv (3^{3})^{4}(3^{2}) \equiv (-2)^{4}(9) \equiv -1 \pmod{29} $$

$$ 7^{14} \equiv (-9)^{7} \equiv (81)^{3}(-9) \equiv (-6)^{3}(-9) \equiv 1 \pmod{29}. $$

And so, your original number is divisible by $29.$