1
$\begingroup$

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?

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

There are two ways of solving a system of congruences presented in this post. Here is how you can solve your system by solving each equation successively, as in the second answer in the linked post.

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.