# Techniques in solving the congruence modulo

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

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

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.