Solving a system of simultaneous congruences using the Chinese Remainder Theorem.
\nAn explore mode question which allows you to write a solution straight away, or break it down into steps.
\nAfter solving a system of three congruences, you can ask for a new problem with more congruences.
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "", "advice": "", "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "extensions": ["working-out"], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true, "j": false}, "constants": [], "variables": {"rs": {"name": "rs", "group": "Unnamed group", "definition": "random(1..n-1) for: n of: ns", "description": "The remainders for each of the congruences.
", "templateType": "anything", "can_override": false}, "ys": {"name": "ys", "group": "Unnamed group", "definition": "prod(ns)/n for: n of: ns", "description": "$(\\prod n_i) / n_i$
", "templateType": "anything", "can_override": false}, "num_rows": {"name": "num_rows", "group": "Unnamed group", "definition": "3", "description": "The number of congruences.
", "templateType": "anything", "can_override": false}, "ns": {"name": "ns", "group": "Unnamed group", "definition": "iterate(\nons -> ons + [random(x for: x of: n_range where: not some(gcd(g,x)>1 for: g of: ons))], [], num_rows)[-1]", "description": "Three coprime numbers between 30 and 100.
", "templateType": "anything", "can_override": false}, "n_range": {"name": "n_range", "group": "Unnamed group", "definition": "5 .. 15#1", "description": "The range of numbers to pick from.
", "templateType": "range", "can_override": true}, "zs": {"name": "zs", "group": "Unnamed group", "definition": "mod(modular_inverse(n,y),n) for: [y,n] of: zip(ys,ns)", "description": "$y_i^{-1} \\mod n_i$
", "templateType": "anything", "can_override": false}, "solution": {"name": "solution", "group": "Unnamed group", "definition": "mod(sum(r*y*z for: [r,y,z] of: zip(rs,ys,zs)),prod(ns))", "description": "The lowest solution to the congruences.
", "templateType": "anything", "can_override": false}, "congruences_latex": {"name": "congruences_latex", "group": "Displayed text", "definition": "latex(safe(\"\\\\begin{align}\\n\")+\njoin(\"x \\\\equiv \"+r+\" &\\\\mod \"+n for: [r,n] of: zip(rs,ns), \" \\\\\\\\\\n\")+\nsafe(\"\\n\\\\end{align}\"))", "description": "", "templateType": "anything", "can_override": false}, "congruences_in_words": {"name": "congruences_in_words", "group": "Displayed text", "definition": "html(\"The modulus under consideration. Used when solving the first congruence.
", "templateType": "anything", "can_override": false}, "r": {"name": "r", "group": "Ungrouped variables", "definition": "rs[0]", "description": "The remainder under consideration. Used when solving the first congruence.
", "templateType": "anything", "can_override": false}, "solutions": {"name": "solutions", "group": "Unnamed group", "definition": "mod(solution, prod(ns[0..i])) for: i of: 1..num_rows", "description": "Solutions to each of the first $i$ congruences.
", "templateType": "anything", "can_override": false}, "two_congruences_table": {"name": "two_congruences_table", "group": "Displayed text", "definition": "table([n, ns[0]*n + rs[0], mod(ns[0]*n+rs[0], ns[1])] for: n of: 0..ns[1], [\"$n$\", safe(\"$\\\\var{ns[0]}n + \\\\var{rs[0]}$\"), \"Remainder after division by {ns[1]}\"])", "description": "", "templateType": "anything", "can_override": false}, "first_congruence_expression": {"name": "first_congruence_expression", "group": "Unnamed group", "definition": "substitute([\"nn\": ns[0], \"r\": rs[0]], expression(\"nn*n+r\"))", "description": "", "templateType": "anything", "can_override": false}, "had_help": {"name": "had_help", "group": "Ungrouped variables", "definition": "false", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["n", "r", "had_help"], "variable_groups": [{"name": "Unnamed group", "variables": ["num_rows", "n_range", "ns", "rs", "ys", "zs", "solution", "solutions", "first_congruence_expression"]}, {"name": "Displayed text", "variables": ["congruences_latex", "congruences_in_words", "two_congruences_table"]}], "functions": {"extendedgcd": {"parameters": [["a", "number"], ["b", "number"]], "type": "list", "language": "javascript", "definition": "let state = [a,b,1,0,0,1];\nwhile(state[1] > 0) {\n let [x,y,s1,s2,t1,t2] = state;\n let r = x%y;\n let q = (x-r)/y;\n state = [y,r,s2,s1-q*s2, t2, t1-q*t2];\n}\n\nreturn state;"}, "modular_inverse": {"parameters": [["a", "number"], ["b", "number"]], "type": "number", "language": "jme", "definition": "extendedgcd(a,b)[4]"}, "copy": {"parameters": [["el", "html"]], "type": "html", "language": "javascript", "definition": "return el[0].cloneNode(true);"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "information", "useCustomName": true, "customName": "Prompt", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Write the number", "rawLabel": "Write the number", "otherPart": 1, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}, {"label": "Get some help", "rawLabel": "Get some help", "otherPart": 2, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Can you find a number that:
\n{congruences_in_words}
"}, {"type": "numberentry", "useCustomName": true, "customName": "Write a number satisfying the congruences", "marks": "60", "scripts": {}, "customMarkingAlgorithm": "satisfied_congruences:\n map(([n,r]) -> \n feedback(\"The remainder on dividing {studentNumber} by {n} is {mod(studentNumber,n)}.\");\n add_credit_if(mod(studentNumber,n)=r, 1/num_rows, \"This is correct.\", \"This is incorrect.\")\n ,\n zip(ns,rs)\n)\n\nmark:\n apply(validNumber);\n apply(satisfied_congruences)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Get some help", "rawLabel": "Get some help", "otherPart": 2, "variableReplacements": [], "availabilityCondition": "credit<1 and not had_help", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}, {"label": "Try another problem with more statements.", "rawLabel": "Try another problem with more statements.", "otherPart": 1, "variableReplacements": [{"variable": "num_rows", "definition": "num_rows+1"}, {"variable": "had_help", "definition": "true"}], "availabilityCondition": "answered and credit=1 and num_rows<9", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}, {"label": "Find out what this is all about", "rawLabel": "Find out what this is all about", "otherPart": 7, "variableReplacements": [], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Go on, then! Write a number that:
\n{copy(congruences_in_words)}
", "minValue": "solution", "maxValue": "solution", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "information", "useCustomName": true, "customName": "Help", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Solve the first congruence", "rawLabel": "", "otherPart": 3, "variableReplacements": [{"variable": "had_help", "definition": "true"}], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "You can break this down step by step.
\nTry finding a number satisfying each line, one at a time.
"}, {"type": "numberentry", "useCustomName": true, "customName": "Solve the first congruence", "marks": "10", "scripts": {}, "customMarkingAlgorithm": "mark:\n apply(validNumber);\n correctif(mod(studentNumber,ns[0])=rs[0]);\n assert(studentNumber>rs[0], feedback(\"That's the easiest answer to find. Can you find another one?\"))", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Write an expression for numbers satisfying the first congruence", "rawLabel": "", "otherPart": 4, "variableReplacements": [], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": "Solve all the congruences", "prompt": "Write a number which leaves a remainder of {r} when divided by {n}.
", "minValue": "n+r", "maxValue": "n+r", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "jme", "useCustomName": true, "customName": "Write an expression for numbers satisfying the first congruence", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Solve the second congruence", "rawLabel": "", "otherPart": 5, "variableReplacements": [{"variable": "first_congruence_expression", "definition": "interpreted_answer"}], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Write an expression in terms of $n$ for numbers which leave a remainder {rs[0]} when divided by {ns[0]}.
\nFor example, the numbers which leave a remainder of 1 when divided by 2 can all be written in the form $2n+1$.
", "answer": "{n}n + {r}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "numberentry", "useCustomName": true, "customName": "Solve the second congruence", "marks": "30", "scripts": {}, "customMarkingAlgorithm": "num_rows_to_mark: 2\n\nsatisfied_congruences:\n map(([n,r]) -> \n feedback(\"The remainder on dividing {studentNumber} by {n} is {mod(studentNumber,n)}.\");\n add_credit_if(mod(studentNumber,n)=r, 1/num_rows_to_mark, \"This is correct.\", \"This is incorrect.\")\n ,\n zip(ns,rs)[0..num_rows_to_mark]\n)\n\nmark:\n apply(validNumber);\n apply(satisfied_congruences)", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Help with solving two congruences", "rawLabel": "", "otherPart": 6, "variableReplacements": [], "availabilityCondition": "not (answered and credit=1)", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}, {"label": "Write a number satisfying all the statements", "rawLabel": "Write a number satisfying all the statements", "otherPart": 1, "variableReplacements": [], "availabilityCondition": "answered and credit=1", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": true, "adaptiveMarkingPenalty": 0, "exploreObjective": "Solve all the congruences", "prompt": "You said that numbers which leave a remainder of {rs[0]} when divided by {ns[0]} can be written in the form
\n\\[ \\var{first_congruence_expression} \\]
\nNow write a number which satisfies that expression and also leaves a remainder of {rs[1]} when divided by {ns[1]}.
", "minValue": "solutions[1]", "maxValue": "solutions[1]", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "displayAnswer": "", "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "information", "useCustomName": true, "customName": "Help with solving two congruences", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [{"label": "Write a number satisfying all the statements", "rawLabel": "Write a number satisfying all the statements", "otherPart": 1, "variableReplacements": [], "availabilityCondition": "", "penalty": "", "penaltyAmount": 0, "showPenaltyHint": true, "lockAfterLeaving": false}], "suggestGoingBack": true, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "You've already said that numbers which leave a remainder of {rs[0]} when divided by {ns[0]} can be written in the form
\n\\[ \\var{ns[0]}n + \\var{rs[0]} \\]
\nTo find a number which also leaves a remainder of {rs[1]} when divided by {ns[1]}, you could just try different values of $n$ until you find one.
\n{two_congruences_table}
\nSo {solutions[1]} is a solution.
"}, {"type": "information", "useCustomName": true, "customName": "About the theorem", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "The statements you were given are called linear congruences.
\nThere's another way of writing them: for the statement \"$x$ leaves a remainder of $r$ when divided by $n$\", we write:
\n\\[ x \\equiv r \\mod n \\]
\nThe number after $\\bmod$ is called the modulus.
\nSo the statements you were given can be written as this system of congruence equations:
\n{congruences_latex}
\nThis system has a solution when all of the moduli are coprime.
\nThis is called the Chinese remainder theorem, after the first person known to have written about it, the Chinese mathematician Sunzi, in the 3rd to 5th century CE.
\nToday we say that this is a theorem from number theory.
\nThe Chinese remainder theorem is widely used for computing with large integers, as it allows replacing a computation for which one knows a bound on the size of the result by several similar computations on small integers
"}], "partsMode": "explore", "maxMarks": 0, "objectives": [{"name": "Solve all the congruences", "limit": "60"}], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Anthony Youd", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/5/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Anthony Youd", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/5/"}, {"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}