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?
 A: Here is a computational and machinery approach using GAP:
 gap> Z168:=Integers mod 168;;
      e:=Elements(Z168);;
      f:=2^(485);;
    for alpha in e do
        if 3373*alpha-f=Zero(Z168) then Print(alpha,"\n");
        fi;
    od;

The answer is
 ZmodnZObj( 80, 168 )

A: As $3373\equiv13\pmod{168}$ 
the problem immediately reduces to $13x\equiv2^{485}\pmod{168}$
So, $13x=2^{485}+168b=(2^{482}+21b)8$ for some integer $b$
$\implies 8|x,x=8y$(say)
So, the problem  reduces to $13y\equiv2^{482}\pmod{21}$
Now, $2^6=64\equiv1\pmod{21}\implies 2^{482}=(2^6)^{160}\cdot2^2\equiv4\pmod{21}$
$\implies13y\equiv4\pmod{21}$
As $13\cdot5-21\cdot3=2,13y\equiv2(13\cdot5-21\cdot3)\equiv130\pmod{21}$
As $(13,21)=1,y\equiv\frac{130}{13}\pmod{21}\equiv10$
$\implies x=8y\equiv? \pmod{21}$
A: 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}$.
A: First reduce 2^485(mod 168) to 32(mod 168).
Then solve 3373x = 32(mod 168) which becomes x = 80(mod 168).
