0

My question is how to show solve problems as such:

$$x \ mod \ 3= 0$$ $$x \ mod \ 5= 2$$ $$x \ mod \ 15 = ?$$

By trial and error I found that x can be 27, and hence answer is 12. But how can I solve similar questions without trial and error?

errorist
  • 315

2 Answers2

1

There's a formula to know: as a by-product of a Bézout's identity $\;3u+5v=1$, the inverse isomorphism of the canonical isomorphism of the Chinese remainder theorem: \begin{align} \mathbf Z/15\mathbf Z&\longrightarrow\mathbf Z/3\mathbf Z\times \mathbf Z/5\mathbf Z \\ x\bmod 15&\longmapsto (x\bmod 3,x\bmod 5) \end{align} is given by: \begin{align} \mathbf Z/15\mathbf Z&\longleftarrow\mathbf Z/3\mathbf Z\times \mathbf Z/5\mathbf Z \\ 3ub+5va\bmod 15&\longleftarrow (a\bmod3,b \bmod 5) \end{align}

An obvious Bézout's relation is here $\;2\cdot 3-5=1$, so the solution is $$x\equiv 3\cdot 2\cdot 2-5\cdot 0=12\mod 15.$$

Bernard
  • 175,478
0

Write $x=5a+2 = 3b$. Then $3|5a+2$ and since we have always $3|3a$ we deduce that $3|(5a+2)-3a = 2(a+1)$. By Euclid lemma we have $3|a+1$ so $a+1=3c$. So $$ x = 5(3c-1)+2 = 15c-3 \equiv 12 \pmod{15} $$

nonuser
  • 90,026