Find the greatest common divisor of $2^{2004}-1$ and $2^{2002}-1$.

Question

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?

Answer 1

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.