How to solve system of linear congruences without using inverse integers?

Question

Suppose I have a set of linear congruences with their modules being relatively prime. Is there an elementary way to solve these without using the inverse properties of modular integers?

Ex. Solving x congruent to 3mod17 x congruent to 10mod16 x congruent to 0mod15

I know the result, by brute force. I also know since the mod's are pair wise incongruent , that there exists a unique solution mod (15*16*17).

Answer 1

There is a possibility, but it is like shooting rockets on ants :)

Suppose, $a$ and $n$ are coprime.

Since we have $a^{\phi(n)} \equiv 1\ (\ mod\ n)$ , we could calculate

$$a^{\phi(n)-1}\equiv a^{-1}\ (\ mod\ n)$$

Answer 2

$x\equiv 3\pmod{17}\iff x=17k+3,\, k\in\Bbb Z$.

$17k+3\equiv 10\pmod{16}\iff 17k\equiv 7\pmod{16}$

$\iff k\equiv 7\pmod{16}\iff k=16m+7,\, m\in\Bbb Z$.

$x=17(16m+7)+3=272m+122$.

$272m+122\equiv 0\pmod{15}\iff 272m\equiv -2\pmod{15}$

$\iff 2m\equiv -2\pmod{15}\iff m\equiv -1\equiv 14\pmod{15}$

$\iff m=15c+14,\, c\in\Bbb Z$. $x=272(15c+14)+122=4080c+3930$.