# Chinese Remainder Theorem

Printable View

• October 31st 2008, 02:39 PM
aaronrj
Chinese Remainder Theorem
I'm trying to find all solutions to this system of congruences:

x = 1(mod 2) (sorry, I'm using = instead of the logical equivalence)
x = 2(mod 3)
x = 3(mod 5)
x = 4(mod 11)

2 * 3 * 5 * 11 = 330

M1 = m / 2 = 165 (3 * 5 * 11)
M2 = m / 3 = 110 (2 * 5 * 11)
M3 = m / 5 = 66 (2 * 3 * 11)
M4 = m /11 = 30 (2 * 3 * 5) (I think this is where my problem is)

165 = 1(mod 2)
110 = 1(mod 3)
66 = 1(mod 5)
30 = 8(mod 11)

x = 1 * 165 * 1 + 2 * 110 * 2 + 3 * 66 * 1 + 4 * 30 * 8 = 1763

1763 = 113(mod 330)

x = 113 holds up for the first three congruences, but fails on the 4th.

Could someone please point out where I'm going wrong? I have no problem solving the system with the first three congruences, but every time I add the fourth and try to solve it, I run into problems.
• November 1st 2008, 01:27 AM
Opalg
I have noticed that people who use these mechanical algorithms for problems of this sort often end up with the wrong answer. I'm sure that the formulas work if they are used correctly, but in practice they seem to invite arithmetic mistakes. So I prefer to avoid the formulas and use more common-sense methods.

In this case, if you can deal with the first three congruences then you know that $x\equiv23\!\!\!\pmod{30}$, and you want to combine this with $x\equiv4\!\!\!\pmod{11}$. The first of those congruences looks simpler if you add 7 to both sides, to get $x+7\equiv0\!\!\!\pmod{30}$. By good fortune, the second congruence also looks simpler if you add 7 to both sides, to get $x+7\equiv0\!\!\!\pmod{11}$. So x+7 is a multiple of both 11 and 30, and therefore it is a multiple of 330. Therefore $x\equiv-7\equiv323\!\!\!\pmod{330}$.
All times are GMT -8. The time now is 06:01 AM.
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 5, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9320366382598877, "perplexity_flag": "head"}