Here's an alternative to find the least non-negative solution for a system of congruences.

Let's use the example from class:

$x \equiv 3 \mod{10}$

$x \equiv 4 \mod{7}$

$x \equiv 2 \mod{9}$

Then for the first congruence we have

$x = 10a + 3$, $a \in \mathbb{Z}$

Use substitution

$10a + 3 \equiv 4 \mod{7}$

$10a \equiv 1 \mod{7}$

$a \equiv 5 \mod{7}$

$a = 7b + 5$, $b \in \mathbb{Z}$

Substitute for a

$x = 10a + 3$

$x = 10(7b + 5) + 3$

$x = 70b + 53$

Use substitution for the last congruence

$70b + 53 \equiv 2 \mod{9}$

$70b \equiv -51 \mod{9}$

$70b \equiv -6 \mod{9}$

$b \equiv 3 \mod{9}$

$b = 9c + 3$, $c \in \mathbb{Z}$

Substitute for b

$x = 70b + 53$

$x = 70(9c + 3) + 53$

$x = 630c + 263$

Therefore, our smallest non-negative solution is $x = 263$

Note that the product of the modulars $(10) * (7) * (9) = 630$ and $263$ is in between $0$ and $630$

and our solution from class $(7 * 9)(7)(3) * (10 * 9)(-7)(4) * (10 * 7)(4)(2) \equiv 263 \mod{630}$ .