Find the greatest common divisor of $2^{2004}-1$ and $2^{2002}-1$. Find the greatest common divisor of $2^{2004}-1$ and $2^{2002}-1$. 
Using Euclidean algorithm:
$$2^{2004}-1=4(2^{2002}-1)+3$$
$$2^{2002}-1=x\cdot 3+y$$
The solution manual says that $2^{2002}-1$has the remainder $0$ when divided by $3$, that is $y=0$ so GCD is $3$. But how do I find that remainder?

We have,
$2^{2002} -  1$
$= (2^4)^{500}.2^2 - 1$
Now $2^4 \equiv 1 (\mod 3)$
From above,
$= (1)^{500} .2^2 - 1$
$= 1.2^2 - 1$
$= 4 - 1 = 3$
Divisible by 3.
