# Solving the congruence system and checking the answer

I have a congruence system to solve, that I actually tried to solve. The problem is that I'm not sure that I did it right, because at the end I cannot find a proper number that will be working fine for all of the equations.

$$x≡6(mod7)$$

$$x≡7(mod13)$$

$$x≡4(mod5)$$

$$x≡7(mod11)$$

At the end I have a equation like:

$$x=7k+6 = 7(13y+1)+6 = 91y+13 = 455z-806 = 455(11b+813/455) = 11b + 7$$

So at the end there is this nice reduction of 455. I thought it was a good sign that I did everything properly. Neverthless, whichever $$b$$ I can think of, the answer is not right for all of the congruences above. I tried $$n = 0, 1, 2, 3, ... 10 (x=7, 18, 19, 29, 40, 51 ...)$$ and I cannot find a proper answer. How to easily deal with such tasks?

• In this case (pairwise coprime numbers), you can find a unique value modulo the product of the numbers (because of the chinese remainder theorem). Here you get $1294$ modulo $5005$ – Peter Oct 19 at 16:10
• Thanks for the hint. I solved it with The Chinese Remainder Theorem. I've got x≡1294(mod5005) and it's the proper number. – Mary Oct 19 at 16:40
• And the comment for anyone who will look for similar problem: youtube.com/watch?v=zIFehsBHB8o - there is a great tut on how to solve these kind of equations with the Chinese Remainder Theorem. – Mary Oct 19 at 16:45

$$x \equiv\, 6 \mod 7 \implies x = 7a+6 \quad\color{red}{\text{ (1.)}}$$

From $$\color{red}{\text{(1.)}}$$

$$x \equiv\, 7 \mod 13 \implies 7a+6\equiv 7 \mod13 \implies a = 13b+2 \quad\color{blue}{\text{ (2.)}}$$

From $$\color{blue}{\text{ (2.)}}$$

$$x \equiv\, 4 \mod 5 \implies 91b+20\equiv 4 \mod5 \implies b = 5c+4 \quad\color{green}{\text{ (3.)}}$$

From $$\color{green}{\text{ (3.)}}$$

$$x \equiv\, 7 \mod 11 \implies 455c+384\equiv 7 \mod11 \implies c = 11d+2 \quad\color{orange}{\text{ (4.)}}$$

Using all the congruence , we arrive at :

\begin{align}x & = 7a+6 = 7(13\,b+2)+6 = 7(13(5\,c +4) +2)+6 = 7(13(5(11\,d+2)+4)+2)+6\\ x & = \color{navy} {\boxed{5005\,d +1294}} \end{align}

• Thanks! In the meantime I managed to solve this with the hint from @Peter (Chinese Remainder Theorem) and I've got x≡1294(mod5005). You answer is really crucial for me, because now I can check what I did wrong the first time. Big thanks to you! – Mary Oct 19 at 16:42
• @Mary Appreciate it ! – The Demonix _ Hermit Oct 19 at 16:44
• @Mary This system has special structure allowing us to reduce the work by half - see my answer. – Bill Dubuque Oct 19 at 18:26

How to easily deal with such tasks?

This system is very easy since two pairs of congruences have constant values $$7$$ and $$-1$$.

$$x\equiv 7 \pmod {11\ \&\ 13}\iff x\ \equiv\ \color{#0a0}7\ \pmod{\color{#0a0}{11\cdot 13}}\$$ by CCRT = Constant case of CRT

$$x\equiv -1 \pmod {5\ \&\ 7}\ \iff x\equiv \color{#90f}{-1}\pmod{5\cdot 7\!=\!\color{#90f}35}\$$ as above, so solving these two by CRT

$$\!\!\bmod \color{#90f}{35\!:\ {-}1}\equiv x \equiv \color{#0a0}{7+11\cdot 13}k\equiv 7\!+\!3k\!\iff\! 3k\equiv -8\equiv 27\!\iff\! k\equiv 9\!\iff\! \color{#c00}{k = 9\!+\!35n}$$

So we conclude: $$\, x \equiv 7+11\cdot 13\color{#c00}k \equiv 7+11\cdot 13(\color{#c00}{9+35n})\equiv \bbox[5px,border:1px solid #c00]{1294 + 5005n}$$

Remark  This optimization is frequently handy, e.g. for your YouTube system we have

$$x\equiv -2\pmod{5\ \&\ 8}\iff x\equiv -2\pmod{\!40}\iff x = \color{#0a0}{-2+40k}$$

$$\!\!\bmod 7\!:\,\ 1\equiv x\equiv \color{#0a0}{-2+40k}\equiv -2-2k\iff 2k\equiv 4\iff k\equiv 2\iff \color{#c00}{k = 2+7n}$$

We conclude $$\ x\equiv -2 + 40\color{#c00}k\equiv -2+40(\color{#c00}{2+7n})\equiv \bbox[5px,border:1px solid #c00]{78+280n}$$