How to figure out congruences involving large numbers?

Question

The one I'm stuck on now is:

$$3^{1996001} ≡ 2664001 \mod 3992003$$

Absolutely no idea how to get this! I could whittle it down if I knew the multiplicative order of $3$ modulo $3992003$, but I have no idea how to figure this out.

Thanks.

Answer 1

Here I'm supposing you can find out that the prime factorization of $3992003$ is $1997*1999$.

First we solve $3^{1996001} (\text{mod } 1997)$. Since 1997 is prime we have

$$3^{1996}\equiv 1 (\text{mod }1997).$$

Now $1996001 = 1996 . 1000 + 1$, so

$$3^{1996001} \equiv 3^{1996*1000+1} \equiv (3^{1996})^{1000}.3 \equiv 1^{1000}.3 \equiv 3 \text{ (mod }1997).$$

Similarly, we have

$$ 3^{1998} \equiv 1 \text{ (mod }1999),$$

and $1996001=999*1998-1$, so

$$3^{1996001} \equiv 3^{999*1998-1} \equiv (3*1998)^{999}.3^{-1} \equiv 3^{-1} \equiv -666 \text{ (mod }1999).$$

Now we want to solve the congruence problem:

$$\begin{align*}x &\equiv 3 &\text{ (mod 1997)}\\ x &\equiv -666 &\text{ (mod 1999)}\end{align*}$$

We need integers $a$ and $b$ such that $1997a+1999b=1$. We have

$$1999 = 1.1997 +2$$ $$1997 = 2.998 + 1$$

So

$$ 1 = 1997 - 2.998 = 1997 - (1999 - 1997).998 = 1997.999 + 1999(-998).$$

Now if $\alpha=1997.999$, $\beta=1999(-998)$, we have

$$\alpha \equiv 0 \text{ (mod 1997)},\ \ \beta \equiv 1 \text{ (mod 1997)},$$ $$\alpha \equiv 1 \text{ (mod 1999)},\ \ \beta \equiv 0 \text{ (mod 1999)},$$

therefore $(-666)\alpha + 3\beta$ is a solution for $x$ in the above system, and

$$ (-666)\alpha + 3\beta= -666*1997*999 + 3*1999*(-998) = -1334657004 \equiv 2664001 \text{ (mod 3992003)}$$