What is the remainder? What is the remainder when $7^{2002}+3^{2002}+2002$ is divided by $29$ ?
I tried out the problem using congruent modulo but cannot help my cause.
 A: Hint: $7^2 + 3^2 = 2 \cdot29$.
A: These kind of problems can always be solved in a similar matter. The goal is to find powers that are congruent $1$ or $-1$ modulo $29$. So you start with $7$ and calculate it's powers modulo $29$:
$$\begin{align*}
7^1&\equiv 7\\
7^2&\equiv 7\cdot 7\equiv 49 \equiv 20\\
7^3&\equiv 20\cdot 7\equiv 140\equiv 24\\
7^3&\equiv 24\cdot 7\equiv 168\equiv 23\\
7^3&\equiv 23\cdot 7\equiv 161\equiv 16\\
&\vdots\\
7^7&\equiv 25\cdot 7\equiv 175\equiv 1
\end{align*}$$
The same for powers of $3$ gives you $3^{14}\equiv 28\equiv -1$. Since $1^k\equiv 1$ and $(-1)^{2k}\equiv 1$ for all $k\in\mathbb Z$, you can reduce the exponent of $7$ modulo $7$ (i.e. $2002\equiv 0\mod 7$) and the exponent of $3$ modulo $28$ (i.e. $2002\equiv 14\mod 28$ and $3^{14}\equiv -1\mod 29$). Now you are left with $1-1+2002$. All you need to do is calculate the remainder of $2002$.
If you know a little number theory you can even use Fermat's little theorem $a^{p-1}\equiv 1\mod p$ to begin with and reduce all exponents modulo $28$, or only try divisors of $28$ to find smaller exponents giving $1$ or $-1$.
A: Every element in $Z_{29}$ has order DIVIDING 28 (Multiplicative order). $2002\cong 1 \mod 29$. Does that help?
A: You have $2002 \equiv 14$ modulo $28 = \varphi(29)$. Recall Euler's theorem: $$7^{2002} \equiv 7^{14} = 7^{(29 - 1)/2} = \Big( \frac{7}{29}\Big) = 1,$$ since $7 \equiv 36 = 6^2$ is a square mod $29$. 
On the other hand, $3$ is not a square mod $29$, since $$\Big( \frac{3}{29} \Big) = \Big( \frac{29}{3} \Big) = \Big( \frac{2}{3} \Big) = -1$$ using quadratic reciprocity. 
In all, you get $$7^{2002} + 3^{2002} + 2002 \equiv 1 + (-1) + 2002 \equiv 2002 \equiv 1 \; (\bmod 29).$$
