# Explain this step in solving this system of linear congruences.

I'm looking at this example and it doesn't make sense to me.

We have to solve the following systems of linear congruences :

$x\equiv 1\pmod 5$

$x\equiv 2\pmod 6$

$x\equiv 3\pmod 7$

We take congruence no. 1 as $x=5t+1$.

We plug it into the second one :

$5t + 1\equiv 2\pmod 6$

• Now, how do we get from that to $t\equiv 5\pmod 6$ ?

Next, we make the $t = 6u + 5$

The equation now becomes $30u + 26$

We plug this into the third congruence :

$30u + 26\equiv 3\pmod 7$

• Now, how do we get from that to $u\equiv 6\pmod 7$ ?

$5t + 1 \equiv_6 2 \implies 5t \equiv_6 1$. The inverse of $5$ is $5$, since $5 \cdot 5 = 25 \equiv_6 1$, so multiply by the inverse on both sides to get $t \equiv_6 5$. Similarly, $30u + 26 \equiv_7 3 \implies 2u + 5 \equiv_7 3 \implies 2u \equiv_7 5$ and the inverse of $2$ is $4$, so $u \equiv_7 6$.
• What method did you use for calculating the inverse ? Won't the Euclidean algorithm method return -1 as the inverse of 5 ? – Objective-J Apr 20 '16 at 14:12