# Thread: linear congruences

1. ## linear congruences

Find the least nonnegative solution of each system of congruences below

x=1mod7
x=4mod6
x=3mod5

2. $x \equiv 1 \ (\text{mod } 7) \iff x = 1 + 7k_{1} \ \ k_{1} \in \mathbb{Z}$

$x \equiv 4 \ (\text{mod } 6)$
........ $\begin{array}{rcll} \iff 1 + 7k_{1} & \equiv & 4 & \ (\text{mod } 6) \\ 7k_{1} & \equiv & 3 & (\text{mod } 6) \\ 7k_{1} & \equiv & 21 & (\text{mod } 6) \\ k_{1} & \equiv & 3 & (\text{mod } 6) \\ k_{1} & = & 3 + 6k_{2} & k_{2} \in \mathbb{Z} \end{array}$

So: $x = 1 + 7k_{1} = 1 + 7(3 + 6k_{2}) = 22 + 42k_{2}$ (So far, x satisfies the first two congruences)

$x \equiv 3 \ (\text{mod } 5)$
........ $\begin{array}{rcll} \iff 22 + 42k_{2} & \equiv & 3 & (\text{mod } 5) \\ 42k_{2} & \equiv & -19 & (\text{mod } 5) \\ 42k_{2} & \equiv & -84 & (\text{mod }5) \\ k_{2} & \equiv & -2 & (\text{mod }5) \\ k_{2} & \equiv & 3 & (\text{mod }5) \\ {\color{red}k_{2}} & = & 3 + 5k_{3} & k_{3} \in \mathbb{Z} \end{array}$

So: $x = 22 + 42{\color{red}k_{2}} = \hdots$

3. Originally Posted by bigb
Find the least nonnegative solution of each system of congruences below

x=1mod7
x=4mod6
x=3mod5
$x\equiv 1 ~ (7)$
$x\equiv 3 ~ (5)$
Is equivalent to,
$x \equiv 8 ~ (7)$
$x\equiv 8 ~ (5)$
These combine to,
$x\equiv 8 ~ (35)$

Thus, we have the system,
$x\equiv 4 ~ (6)$
$x\equiv 8 ~ (35)$

This is equivalent to,
$x\equiv 4 + 6(24) ~ (6)$
$x\equiv 8 + 35(4) ~ (35)$

Thus,
$x\equiv 148 ~ (6)$
$x\equiv 148 ~ (35)$

This combines into,
$x\equiv 148 ~ (210)$