1. ## Solving linear congruence

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:

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

$\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 ?

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 remainder
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$
This theorem shows how many solutions there are to a congruence.

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$

2. ## Re: Solving linear congruence

5t = 1 (6)

multiply by 5

25t = 5 (6)

therefore

t = 5 (6)

since 25 = 1 (6)

3. ## Re: Solving linear congruence

Originally Posted by Idea
5t = 1 (6)

multiply by 5

25t = 5 (6)

therefore

t = 5 (6)

since 25 = 1 (6)
thank you my friend. The problem is solved.

To give more information on the method, I post this example from A friendly introduction to number theory 2nd Ed, J. Silverman P53

Solve $4x\equiv3 \left(\bmod19\right)$

Multiply both sides by 5:

$\Rightarrow 20x\equiv15\left(\bmod19\right)$

We know that

$20\equiv1\left(\bmod19\right)$

$\Rightarrow 20x\equiv x\left(\bmod 19\right)$

Thus the solution is

$x\equiv15\left(\bmod19\right)$