Ur choice. Use either induction or congruences......

What we are essentially solving is the equation: $3^{2002} + 7^{2002} + 2002 \equiv u \pmod{29}$ so that $u$ is as small as possible and still a natural number. One can attack each term separately.

• $2002 = 29*60 + 1$ $\Rightarrow$ $2002 \equiv 1 \pmod{29}$

• $3^{2002}\ = 9^{1001} = 81^{500}*9$ , notice that $81 \equiv 23 \pmod{29}$ and therefore $81^{500}*9 \equiv 23^{500}*9 \pmod{29}$

• With the same principle as above: $7^{2002} = 49^{1001}, 49 \equiv 20 \pmod{29} \Rightarrow 49^{1001} \equiv 20^{1001} \pmod{29}$ . Now notice that $20^{1001} = 400^{500}*20, 400 \equiv 23 \pmod{29} \Rightarrow 400^{500}*20 \equiv 23^{500}*20 \pmod{29}$

Substituting each term with its equivalent in $\Zeta_{29}$ we get:

$3^{2002} + 7^{2002} + 2002 \equiv u \pmod{29} \leftrightarrow \\ 23^{500}*9 + 23^{500}*20 + 1 \equiv u \pmod{29} \leftrightarrow \\ 23^{500}(9 + 20) + 1 \equiv u \pmod{29} \leftrightarrow \\ 23^{500}(29) + 1 \equiv u \pmod{29}$

As the leftmost term is multiple of 29 the remainder is the right term. Therefore $u$ and the answer is $1$