# System of Linear Congruences and Chinese Remainder Theorem

Is there a way to find the solution to $x \equiv 3$ (mod $4)$ and $x \equiv 10$ (mod $35$) without trial and error in the scope of elementary number theory? Is there a trivial solution you can immediately see from this? (How would you guess that case?) One solution is 115, but I got this from guessing.

EDIT: To clarify, let me give an example of a problem I did. I solved

$x \equiv 3$ (mod $4)$, $x \equiv 5$ (mod $21)$, and $x \equiv 7$ (mod $25)$ by solving the first two congruences first: $x \equiv 3$ (mod $4)$, $x \equiv 5$ (mod $21)$. I guessed that $x = 47$ would work in both by using the first congruence with trial and error. Would there have been an easier way to do this? From this, would there be a trivial answer to the original system provided?

• Can you clarify the question? I would think that Chinese Remainder Theorem is within the scope of elementary number theory. – John Brevik Nov 8 '17 at 16:38
• I edited the question with an example. – Dominated Convergence Theorem Nov 8 '17 at 16:52

Since $x \equiv 10 \pmod{35}$, then $x = 10 + 35a$ for some integer $a$. Substituting this into the first equation yields $$3 \equiv x = 10 + 35 a \equiv 2 + 3a \pmod{4} \implies 1 \equiv 3a \implies 3 \equiv a \, .$$ Then $a = 3 + 4b$ for some $b$, so $$x = 10 + 35a = 10 + 35(3 + 4b) = 115 + 140b$$ and varying $b \in \mathbb{Z}$ produces all possible solutions.
You have to perform the extended Euclidean algorithm to have a Bézout's relation between $4$ and $35$: $\;4u+35v=1$. Then $$\begin{cases}x\equiv 3\mod 4\\x\equiv 10\mod 35\end{cases}\iff x\equiv 10\cdot 4u+3\cdot 35v\mod 4\cdot 35$$