Chinese remainder theorem, can't figure it out!

Question

x mod 5 = 3

x mod 7 = 5

x mod 11 = 7

How to determine x? I've been searching on YouTube, but they're giving examples in different ways, for example

x ≡ 1(mod 3)

I don't understand it, is it the same as x mod 3 = 1? Thanks, Im still new and quite slow at math, I'm trying to understand it still

Answer 1

Chinese Reminder Theorem says that there exist one solution $\mod M= m_1 \cdot \dots m_n$ of the system

$$\cases{x \equiv b_1 \mod m_1 \\ x \equiv b_2 \mod m_2 \\ \dots \\ x \equiv b_n \mod m_n}$$

and the solution is of the form $$x=b_1M_1M_1'+ \dots + b_nM_nM_n'$$ where $$ M_i= \frac{m_1 \cdot \dots m_n}{m_i}$$ and $M_i$' is the inverse of $M$, so $$M_i'M_i \equiv 1 \mod m_i$$

Answer 2

They are not quite the same. In the notation $x \bmod{3} = 1,$ the "mod" is acting as a function. When you write $x \bmod 3$ it means "least nonnegative residue of $x$ modulo 3,", so the only answers can be $0, 1,$ or $2.$

In the notation $x \equiv 1 \pmod{3},$ the "mod" is a modifier of the "$\equiv$," so it's not a function here, but part of the congruence equivalence relation.

That said, there's very little difference in the end. But we can have $x \equiv 4 \pmod{3}$, but $x \bmod{3} \ne 4.$

To solve a CRT problem, there are two methods. One is outlined in another answer. Another way is to work through it, one congruence at a time. The first congruence says $x \equiv 3 \pmod{5}$ which means $x = 5k+3$ for some integer $k$. Plug this into the second congruence:

$$x \equiv 5 \pmod{7}$$

$$5k+1 \equiv 5 \pmod{7}$$

$$k\equiv 5 \pmod{7}$$

So $k=7n+5$ for some integer $n$. That means $x=5(7n+1)+5 =35n + 10.$ Put this in the last congruence and repeat. You'll get $x=385m+$something and "something" is the final answer.

Answer 3

$\,a \equiv b\!\pmod{\! n}\ $ means $\,n\mid a-b,\,$ i.e. $\,a-b = nq\,$ for some integer $q$

$\,a = (b \bmod n)\ $ means the above and $\,0 \le a < n\,$

since $ \ b \bmod n\,\ $ denotes the remainder left after dividing $\,b\,$ by $\,n\,$

---

In your system note $\ 3\equiv \color{#c00}{-2}\pmod{\!5},\,\ 5\equiv\color{#c00}{-2}\pmod{\!7},\ $ which yields

$$\begin{align} x\equiv\color{#c00}{-2}\!\!\!\pmod{\!5,7}\iff&\ 5,7\mid x\!+\!2\\[.2em] \iff&\ \ \ 35\mid x\!+\!2,\ \ {\rm by}\ \ 35 = {\rm lcm}(5,7)\\[.2em] \iff&\ \ \ x\equiv -2 \!\!\pmod{\!35}\end{align}\!$$

Combining the above solution $\bmod 35\,$ with the final congruence $\ x\equiv\color{#0a0}7\pmod{11}\,$ yields

$35\mid x\!+\!2\,\Rightarrow\, x\!+\!2\bmod 35\cdot 11 = 35\left[\dfrac{x\!+\!2}{35}\bmod{11}\right]\equiv 35[-1]\,$ by $\ \dfrac{\color{#0a0}7\!+\!2}{35}\equiv\dfrac{-2}2\pmod{\!11}$

So we obtain $\ x\!+\!2\equiv -35\,\Rightarrow\, x\equiv -37\equiv 348\pmod{\!385},\ \ 385 = 35\cdot 11$

Remark $ $ Notice that using the relation mod (vs. operation) allowed us to switch from the canonical (least non-negative) remainders $3,5$ to a congruent constant negative residue $\color{#c00}{-2},\,$ so the system simplifies to one where the RHS all have the same value, i.e. $\,x\equiv \color{#c00}{-2}\,$ for both moduli. This constant case system requires only $\rm lcm\,$ (vs. full CRT), i.e. we only need to know that basic fact $\,a,b\mid n\iff {\rm lcm}(a,b)\mid n\,$ in order to solve the equivalent system $\,x\equiv \color{#c00}{-2}\,\pmod{5,7}.\,$ See CCRT = Constant case CRT for more on this (which is equivalent to the uniqueness direction of CRT, i.e. we could have invoked uniqueness vs. using $\rm{lcm}$ above).