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, nmasanta Sep 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.

  • 1
    $\begingroup$ A solution is $a=81$. So, there is a solution. $\endgroup$ – 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}.$$

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


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