# Modular arithmetic: congruence equation problem

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?

• well $60-59=1$...
– zwim
Jun 5, 2020 at 15:29

## 1 Answer

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