Hello guys

I got a system of linear congruences, having some trouble in solving it.

$x\equiv1\left(\bmod5\right)$

$x\equiv2\left(\bmod6\right)$

$x\equiv3\left(\bmod7\right)$

By the following theorem:

$x\equiv1\left(\bmod5\right)$$a,b\in INTEGER \Rightarrow a\equiv b \bmod m \Leftrightarrow a=b+km$ where $k\in INTEGER$

$\Rightarrow x=5t+1 \equiv 2 \left(\bmod6\right)$ where $t\in INTEGER$

which can be easily solved to show that

$t\equiv5\left(\bmod6\right)$

Using the above theorem, we write

$t=6u+5$ where $u\in INTEGER$

$\Rightarrow x=5(6u+5)+1=30u+26$

-----------------------------------

I am really having difficulty understanding how to get from

$\Rightarrow x=5t+1 \equiv 2 \left(\bmod6\right)$

to

$t\equiv5\left(\bmod6\right)$

My first attempt to solve it was to consider $x=5t+1 \equiv 2 \left(\bmod6\right)$ as a linear Diophantine equation and solve it using the Euclidean algorithm:

$5t+1-6y=2$

$\Rightarrow 5t-6y=1$

$\Rightarrow 6 = 5 \cdot 1 + 1$

$\Rightarrow 5 \cdot 1 = 1 \cdot 5$

This gives $gcd(5,6)=1$ which isn't that helpful really ?

Thanks for your advice guys.

EUCLIDEAN ALGORITHM

Let $r_{0}=a , r_{1}=b \in INTEGER$ such that $a\geq b > 0 $

If the division algorithm is successively applied to obtain

$r_{j}=r_{j+1}\cdot q_{j+1} + r_{j+2}$ where $0<r_{j+2}<r_{j+1}$ for $j=0,1,2,...,n-2$ and $r_{n+1}=0$

then $\left(a,b\right)=r_{n}$, the last non-zero remainderThis theorem shows how many solutions there are to a congruence.DIVISION ALGORITHM

$a,b\in INTEGER$ st. $b>0$ $\Rightarrow$ there exist unique $q,r\in INTEGER$ such that $a=bq+r$ with $0\leq r <b$

Let $a,b,m \in INTEGERS $ such that $ m>0 , \left(a,m\right)=d $

$NOT \left(d \mid b\right) \Rightarrow ax=b \left(\bmod m\right)$ has no solutions

$d \mid b \Rightarrow ax=b \left(\bmod m\right)$ has $d$ incongruent solutions modulo $m$