elementary number theory - Solve congruence equation $3373x equiv 2^{485} pmod{168}$

$$3373x \equiv 2^{485} \pmod{168}$$

Uhm...I don't even know how to start.

$GCD(3373,168)=1$, so solution exists.

Usually I would use extended Euclidean algorithm and get the outcome, but it would require multiplying by $2^{485}$ later, so...well, is there some easier way?

Answer

First of all, $168=2^3\cdot3\cdot7$, so you want to solve the three congruences:

$3373x\equiv2^{485} \pmod 8 \\ 3373x\equiv2^{485} \pmod 3 \\ 3373x\equiv2^{485} \pmod 7$

The first of these three is really $3373x\equiv_8 0$, which just implies $x\equiv_8 0$

For the second, $3373\equiv_3 1$, and any odd power of $2$ is congruent modulo $3$ to $2$, so we have $x\equiv_32$

Thirdly, $3373\equiv_76$, and $2^3\equiv_71 \Rightarrow 2^{485}\equiv_72^2=4$. Thus, we have $6x\equiv_74$, or $x\equiv_73$

Finally, we use the Chinese Remainder Theorem to find a number satisfying:

$x\equiv_80 \\ x\equiv_32 \\ x\equiv_73$

In this way, we obtain $x\equiv 80 \pmod {168}$.