Solve $x\equiv 1\pmod{5}, x\equiv 2\pmod{6}, x\equiv 3\pmod{7}$

Question

Solve $x\equiv 1\pmod{5}, x\equiv 2\pmod{6}, x\equiv 3\pmod{7}$

First I can see $x=5t+1, t\in Z$. Then they insert this into the second equation, which is $5t+1\equiv 2(mod6)$, which leads to $t\equiv 5mod6$. Then they get $t=6u+5$, I'm confused how they got to $t=6u+5$ from $5t+1$. Also if anyone has any strategies to prove these type of problems where there's an $x$ that has different moduluses.

Answer 1

If $ t \equiv 5 \pmod{6}$, that is equivalent to saying that "t leaves a reminder of 5 when divided by 6", which is equivalent to $t = 6u + 5$.

---

Brute force typically works for Chinese Remainder Theorem. Just push it through.

---

In this case, you may make the observation that $x + 4 \equiv 0 \pmod{5}, \pmod{6}, \pmod{7}$, hence $ x+4 \equiv 0 \pmod{210}$.

Answer 2

See Chinese reminder theorem (existence constructive proof paragraph) for a general method.

Answer 3

x % 5 = 1 = -4

x % 6 = 2 = -4

x % 7 = 3 = -4

This means x % LCM(5, 6, 7) = -4 x % 210 = -4

Therefore x = 210t - 4 (-4, 206, ...)

Answer 4

Yes - like your other question - it is easy by CCRT since it is equivalent to $\,x\equiv -4\,$ for all moduli.

More generally this idea works for linearly related values and moduli: $ $ if $\,(a,b) = 1\,$ then

$$\left\{\,x\equiv d\!-\!ck\!\!\!\pmod{b\!-\!ak}\,\right\}_{k=0}^{n}\!\!\iff\! x\equiv \dfrac{ad\!-\!bc}a\!\!\!\pmod{{\rm lcm}\{b\!-\!ak\}_{k=0}^n}\quad \ $$

OP is case $\,\left\{\,x \equiv 3-k\pmod{7-k}\,\right\}_{k=0}^2\!\!\iff\! x\equiv \dfrac{1(3)-7(1)}1\equiv -4\pmod{210}$