Find the solution of congruence equation $56x=23(mod93)$ between $0≤x<93$ using Euclidean algorithm.

Question

I have no idea how to do it. Hope somebody can explain how to solve it.

Answer 1

Notice that $56$ and $93$ are relatively prime, so $56$ has a multiplicative inverse in $\Bbb Z_{93}$. Hence, there exists $u\in\Bbb Z_{93}$ such that $56u\equiv 1\mod 93$, and thus $x\equiv 23u\mod 93$. You can find $u$ through the equation $56u+93v=1$, which is from Bezout's lemma due to the fact that $\gcd(56,93)=1$.

Notice that $56\cdot 5=280$ and $93\cdot 3=279$, so $56\cdot 5+93\cdot -3=1$. Hence, $u=5$ is the multiplicative inverse of $56$ in $\Bbb Z_{93}$. Thus, $$x\equiv 23\cdot 5\mod 93\implies x\equiv 115\mod 93\implies x\equiv 22\mod 93$$

Answer 2

$$ \gcd( 93, 56 ) = ??? $$

$$ \frac{ 93 }{ 56 } = 1 + \frac{ 37 }{ 56 } $$ $$ \frac{ 56 }{ 37 } = 1 + \frac{ 19 }{ 37 } $$ $$ \frac{ 37 }{ 19 } = 1 + \frac{ 18 }{ 19 } $$ $$ \frac{ 19 }{ 18 } = 1 + \frac{ 1 }{ 18 } $$ $$ \frac{ 18 }{ 1 } = 18 + \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccccc} & & 1 & & 1 & & 1 & & 1 & & 18 & \\ \frac{ 0 }{ 1 } & \frac{ 1 }{ 0 } & & \frac{ 1 }{ 1 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 5 }{ 3 } & & \frac{ 93 }{ 56 } \end{array} $$ $$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 1 \\ \frac{ 1 }{ 1 } & \mbox{digit} & 1 \\ \frac{ 2 }{ 1 } & \mbox{digit} & 1 \\ \frac{ 3 }{ 2 } & \mbox{digit} & 1 \\ \frac{ 5 }{ 3 } & \mbox{digit} & 18 \\ \frac{ 93 }{ 56 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 93 \cdot 3 - 56 \cdot 5 = -1 $$

In particular, $$ 56 \cdot 5 \equiv 1 \pmod {93} $$