2
$\begingroup$

How can the congruence ${x}^{17389}\equiv43927 \pmod{64349}$ be solved? I read that the first step is to solve the congruence $17389d\equiv1 \pmod{63840}$.

I think $d$ is a number such that $17289d≡1 \pmod{63840}$. I beg for help on the procedure to find $d$.

Also another problem I would much like to understand is how to to obtain the value of $x$ above where $x$ is given by $x\equiv{43927}^{d}$.

$\endgroup$
  • $\begingroup$ How $$64349,63840 $$ are related? $\endgroup$ – lab bhattacharjee May 23 '14 at 18:39
  • 1
    $\begingroup$ I'd start with the fact that $64349 = 229 \cdot 281$, and solve it separately for each of those (prime!) moduli. $\endgroup$ – NovaDenizen May 23 '14 at 18:51
1
$\begingroup$

Let's raise both sides to the power $d$. Then you have $$x^{17389d}=43927^d\pmod{64349}$$

The second piece of the puzzle is Euler's theorem, which states that $$x^{\phi(64349)}\equiv 1\pmod{64349}$$ or $$x^{63840}\equiv 1\pmod{64349}$$

Now, if we choose $d$ to satisfy $17389d\equiv 1\pmod{63840}$, then $17389d=k63840+1$ for some integer $k$, and we have $$x^{13389d}=(x^{63840})^kx^1\equiv x^1\equiv 43927^d\pmod{64349}$$


The procedure to find $d$ is as follows. Use the Euclidean algorithm repeatedly on $17389$ and $63840$, then back-substitute to find a solution to $$17389d+63840c=1$$ Then $d$ will be the number you seek.

| cite | improve this answer | |
$\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.