# Chinese Remainder Theorem to find possible element [closed]

the question is find all possible integers a which satisfy the following system of congruences

$$a = 3 \mod 6$$

$$a = 4 \mod 7$$

$$a = 6 \mod 15$$

but I find $$a = 3 \mod 6$$ is $$105n= 3n \mod 6$$ and their $$\gcd$$ is $$3$$ not $$1$$ so in this question is it no solutuion?

## closed as off-topic by Daniele Tampieri, John B, José Carlos Santos, Leucippus, nmasantaSep 12 at 2:14

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please provide additional context, which ideally explains why the question is relevant to you and our community. Some forms of context include: background and motivation, relevant definitions, source, possible strategies, your current progress, why the question is interesting or important, etc." – Daniele Tampieri, John B, José Carlos Santos, Leucippus, nmasanta
If this question can be reworded to fit the rules in the help center, please edit the question.

• A solution is $a=81$. So, there is a solution. – Crostul Sep 11 at 9:19

It is simpler to transform this system of congruences into the equivalent system with pairwise coprime moduli: $$\begin{cases} x\equiv 1 \mod 2, \\ x\equiv 0\mod 3, \\ x\equiv 4 \mod 7,\\ x\equiv 1\mod 5. \end{cases}$$ Let's find the solutions of the last two congruences. Starting from a Bézout's relation between the moduli: $$\;3\cdot 5-2\cdot 7=1$$, we deduce instantly that $$x\equiv 4\cdot3\cdot 5-1\cdot2\cdot 7=46\equiv 11\mod 35.$$ We could proceed in the same way for the other two moduli, but it is faster to observe first that, among these solutions, $$x$$ has to be odd by the first congruence, so $$\;x\equiv 11\bmod 70$$, and ultimately as the second congruence is $$x\equiv 0\bmod3$$, Bézout's relation $$\;70-23\cdot 3=1$$ yields $$x\equiv 11\cdot(-23\cdot 3)=-759\equiv \color{red}{81\bmod 210}.$$

• Actually it is not simpler to make that transformation since it obfscates the innate structure which can by exploited by CCRT - see my answer. – Bill Dubuque Sep 11 at 16:38
• Quite ingenious to use the constant case! (+1) – Bernard Sep 11 at 16:46
• why not use $6=-3\cdot -2$ ? – Roddy MacPhee Sep 11 at 19:11
• Usually, the moduli are taken among positive integers. – Bernard Sep 11 at 19:18
• I'm not a purist. – Roddy MacPhee Sep 11 at 19:33

By CCRT: $$\ a\equiv -3\pmod{\!6\ \&\ 7}\iff a\equiv \color{#c00}{-3\pmod{\!42}}$$

$$\!\bmod 15\!:\,\ 6 \equiv a\equiv \color{#c00}{-3\!+\!42j}\equiv -3-3j\iff 3j\equiv -9\, \smash[t]{\overset{\large \div 3}\iff}\color{#0a0}{\bmod 5\!:\,\ j\equiv} -3\equiv\color{#0a0}2$$

Hence we infer $$\ a = -3\!+\!42(\color{#0a0}{2\!+\!5n}) =\, \bbox[5px,border:1px solid #c00]{81+ 210n}$$