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.





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?

Thank you for any advices!

  • $\begingroup$ 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$ $\endgroup$ – Peter Oct 19 at 16:10
  • 1
    $\begingroup$ Thanks for the hint. I solved it with The Chinese Remainder Theorem. I've got x≡1294(mod5005) and it's the proper number. $\endgroup$ – Mary Oct 19 at 16:40
  • $\begingroup$ 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. $\endgroup$ – 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}$$

  • 1
    $\begingroup$ 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! $\endgroup$ – Mary Oct 19 at 16:42
  • $\begingroup$ @Mary Appreciate it ! $\endgroup$ – The Demonix _ Hermit Oct 19 at 16:44
  • $\begingroup$ @Mary This system has special structure allowing us to reduce the work by half - see my answer. $\endgroup$ – 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}$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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