2
$\begingroup$

$$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?

$\endgroup$
11
$\begingroup$

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}$.

$\endgroup$
  • $\begingroup$ good answer (+1) $\endgroup$ – what'sup Sep 5 '13 at 16:12
4
$\begingroup$

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 )
$\endgroup$
  • $\begingroup$ @amWhy: Thanks my missed friend, Amy. I was not on a good mood to get involved in problems. I feel better today. :) $\endgroup$ – mrs Sep 8 '13 at 5:48
  • $\begingroup$ I'm glad you feel better! ;-) $\endgroup$ – amWhy Sep 8 '13 at 12:44
2
$\begingroup$

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}$

$\endgroup$
0
$\begingroup$

First reduce 2^485(mod 168) to 32(mod 168).

Then solve 3373x = 32(mod 168) which becomes x = 80(mod 168).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.