0

We have the following congruence equation:

$$10x \equiv 8 \mod (59)$$

I was requested to solve this using the Euclidean method. First I noticed the $gcd$ of $10$ and $59$ is $1$, which means the equation will have a solution (for $1$ divides any integer). I know I'm now suppose to find that $1=10s+59t$. And this is the part I'm having trouble with: what are the values of $s$ and $t$ and how do I find them?

lafinur
  • 3,322

1 Answers1

1

Well, the Euclidean method would note:

$59 = 5*10 + 9$

$10 = 9 + 1$

So $1 = 10 - 9 = 10- (59 - 5*10)=6*10 +(-1)*59$.

$s=6$ and $t = -1$ is a solution.

.....

So $6*10\equiv 1 \pmod{59}$ and $10^{-1}\equiv 6\pmod {59}$ and $10x\equiv 8\pmod{59}\implies 6*10x \equiv 6*8\pmod{59}\implies x\equiv 48 \pmod{59}$.

fleablood
  • 124,253