// Numbas version: finer_feedback_settings
{"name": "Blathnaid's copy of Solve three congruences using Chinese Remainder Theorem", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "ungrouped_variables": ["pans", "na", "nb", "nc", "ea", "rc", "ec", "n", "ra", "rb", "ans", "sc", "sb", "sa", "eb"], "parts": [{"prompt": "<p>Solve the following simultaneous congruences:<br/>\\[\\begin{eqnarray*} x\\;&amp;\\equiv&amp;\\;\\var{ra}\\;&amp;\\mod&amp;\\;\\var{sa}\\\\ \\\\ x\\;&amp;\\equiv&amp;\\;\\var{rb}\\;&amp;\\mod&amp;\\;\\var{sb}\\\\ \\\\ x\\;&amp;\\equiv&amp;\\;\\var{rc}\\;&amp;\\mod&amp;\\;\\var{sc} \\end{eqnarray*} \\]<br/>$x=\\;\\;$ [[0]]</p>\n<p>Your value of $x$ should satisfy $0 \\leq x \\lt \\var{n}$</p>\n<p></p>", "customName": "", "type": "gapfill", "sortAnswers": false, "customMarkingAlgorithm": "", "variableReplacements": [], "scripts": {}, "adaptiveMarkingPenalty": 0, "showFeedbackIcon": true, "useCustomName": false, "showCorrectAnswer": true, "gaps": [{"mustBeReduced": false, "customMarkingAlgorithm": "", "customName": "", "type": "numberentry", "mustBeReducedPC": 0, "minValue": "{ans}", "notationStyles": ["plain", "en", "si-en"], "adaptiveMarkingPenalty": 0, "showFeedbackIcon": true, "showCorrectAnswer": true, "showFractionHint": true, "marks": "4", "unitTests": [], "variableReplacementStrategy": "originalfirst", "extendBaseMarkingAlgorithm": true, "correctAnswerStyle": "plain", "maxValue": "{ans}", "variableReplacements": [], "scripts": {}, "useCustomName": false, "correctAnswerFraction": false, "allowFractions": false}], "marks": 0, "unitTests": [], "variableReplacementStrategy": "originalfirst", "extendBaseMarkingAlgorithm": true}], "statement": "", "tags": [], "name": "Blathnaid's copy of Solve three congruences using Chinese Remainder Theorem", "extensions": [], "variables": {"pans": {"name": "pans", "templateType": "anything", "group": "Ungrouped variables", "definition": "mod(ra*ea+rb*eb+rc*ec,n)", "description": ""}, "eb": {"name": "eb", "templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sb,nb)*nb", "description": ""}, "sa": {"name": "sa", "templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,8,sb-1)", "description": ""}, "ra": {"name": "ra", "templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sa-1)", "description": ""}, "n": {"name": "n", "templateType": "anything", "group": "Ungrouped variables", "definition": "na*sa", "description": ""}, "rc": {"name": "rc", "templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..sc-1)", "description": ""}, "rb": {"name": "rb", "templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..sb-1)", "description": ""}, "sb": {"name": "sb", "templateType": "anything", "group": "Ungrouped variables", "definition": "random(12..20)", "description": ""}, "na": {"name": "na", "templateType": "anything", "group": "Ungrouped variables", "definition": "sb*sc", "description": ""}, "nb": {"name": "nb", "templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sc", "description": ""}, "nc": {"name": "nc", "templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb", "description": ""}, "ec": {"name": "ec", "templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,nc)*nc", "description": ""}, "ans": {"name": "ans", "templateType": "anything", "group": "Ungrouped variables", "definition": "pans", "description": ""}, "sc": {"name": "sc", "templateType": "anything", "group": "Ungrouped variables", "definition": "chcop3(sa,sb,sb,2,sa-1)", "description": ""}, "ea": {"name": "ea", "templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,na)*na", "description": ""}}, "advice": "\n  \n  \n  <p>Using the notation in Steps we have:</p>\n  \n  \n  \n  <p>1) $n_1=\\var{sa},\\;n_2=\\var{sb},\\;n_3=\\var{sc}$ are coprime as they have no factors in common.<br/>$n=n_1n_2n_3=\\var{n}$</p>\n  \n  \n  \n  <p>2) <br/>$N_1=\\var{sb}\\times \\var{sc}=\\var{na},\\;\tN_2=\\var{sa}\\times \\var{sc}=\\var{nb},\\;N_3=\\var{sa}\\times \\var{sb}=\\var{nc}$</p>\n  \n  \n  \n  <p>3)</p>\n  \n  \n  \n  <p>Using the Extended Euclidean Algorithm for $N_1=\\var{na}$ and $n_1=\\var{sa}$ we find:<br/>\\[\\simplify[std]{{extendedgcd2(sa,na)}* {na} +{extendedgcd1(sa,na)}*{sa}=1} \\Rightarrow E_1=\\var{extendedgcd2(sa,na)}\\times \\var{na}=\\var{ea}\\]<br/>Using the Extended Euclidean Algorithm for $N_2=\\var{nb}$ and $n_2=\\var{sb}$ we find:<br/>\\[\\simplify[std]{{extendedgcd2(sb,nb)}* {nb} +{extendedgcd1(sb,nb)}*{sb}=1} \\Rightarrow E_2=\\var{extendedgcd2(sb,nb)}\\times \\var{nb}=\\var{eb}\\]<br/>Using the Extended Euclidean Algorithm for $N_3=\\var{nc}$ and $n_3=\\var{sc}$ we find:<br/>\\[\\simplify[std]{{extendedgcd2(sc,nc)}* {nc} +{extendedgcd1(sc,nc)}*{sc}=1} \\Rightarrow E_3=\\var{extendedgcd2(sc,nc)}\\times \\var{nc}=\\var{ec}\\]\t<br/>4)<br/>Then the general solution is:\\[\\begin{eqnarray*}\n  \n  x&#38;=&#38; a_1 E_1+a_2 E_2+a_3 E_3\\;\\mod\\;n\\\\\n  \n  &#38;=&#38; \\simplify[std]{{ra}*{ea}+{rb}*{eb}+{rc}*{ec}}\\;\\mod\\;\\var{n}\\\\\n  \n  &#38;=&#38;\\var{ra*ea+rb*eb+rc*ec}\\;\\mod\\;\\var{n}\\\\\n  \n  &#38;=&#38; \\var{ans}\\;\\mod\\;\\var{n}\n  \n  \\end{eqnarray*}\n  \n  \\]</p>\n  \n  ", "preamble": {"css": "", "js": ""}, "metadata": {"description": "<p>Solving three simultaneous congruences using the Chinese Remainder Theorem:</p>\n<p>\\[\\begin{eqnarray*} x\\;&amp;\\equiv&amp;\\;b_1\\;&amp;\\mod&amp;\\;n_1\\\\ x\\;&amp;\\equiv&amp;\\;b_2\\;&amp;\\mod&amp;\\;n_2\\\\x\\;&amp;\\equiv&amp;\\;b_3\\;&amp;\\mod&amp;\\;n_3 \\end{eqnarray*} \\] where $\\operatorname{gcd}(n_1,n_2,n_3)=1$</p>", "licence": "Creative Commons Attribution 4.0 International"}, "variablesTest": {"condition": "", "maxRuns": 100}, "functions": {"extendedgcd2": {"language": "jme", "parameters": [["a", "number"], ["b", "number"]], "type": "number", "definition": "\n  \n  \n  if((a|b) or (b|a),\n  \n  1\n  \n  ,\n  \n  extendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n  \n  )\n  \n  "}, "mdescextgcd": {"language": "jme", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"], ["t", "number"]], "type": "string", "definition": "\n  \n  \n  if (t=0, \n  \n  '\\n\\n<table  border = \"1\">\\n'+mdescextGCD(a,b,c1,c2,d1,d2,1)\n  \n  ,\n  \n  if(a|b,\n  \n  '<tr> <td>$\\var{a}$</td><td>$\\var{b}$</td><td>$\\simplify[std]{{c1}a+{c2}b}$</td><td>$\\simplify[std]{{d1}a+{d2}b}$</td></tr></table>\n  \n  \n  \n   $\\var{a} | \\var{b}$ and so $(\\var{sa},\\var{sb})=\\var{a}$. Note that $\\simplify[std]{{c1}*{sa}+{c2}*{sb} = {a}}$\\n\\n '\n  \n  ,\n  \n  if(b|a,\n  \n  '<tr> <td>$\\var{a}$</td><td>$\\var{b}$</td><td>$\\simplify[std]{{c1}a+{c2}b}$</td><td>$\\simplify[std]{{d1}a+{d2}b}$</td></tr></table> \n  \n  \n  \n  $\\var{b} | \\var{a}$ and so $(\\var{sa},\\var{sb})=\\var{b}$. Note that $\\simplify[std]{{d1}*{sa}+{d2}*{sb} = {b}}$\\n\\n '\n  \n  ,\n  \n  '<tr> <td>$\\var{a}$</td><td>$\\var{b}$</td><td>$\\simplify{{c1}a+{c2}b}$</td><td>$\\simplify{{d1}a+{d2}b}$</td></tr> \\n'+mdescext1GCD(a,b,c1,c2,d1,d2)\n  \n  )\n  \n  )\n  \n  )\n  \n  "}, "chcop": {"language": "jme", "parameters": [["a", "number"], ["b", "number"], ["p", "number"], ["q", "number"]], "type": "number", "definition": "if(gcd(a,b)=1,b,chcop(a,random(p..q),p,q))"}, "chcop3": {"language": "jme", "parameters": [["a", "number"], ["b", "number"], ["c", "number"], ["p", "number"], ["q", "number"]], "type": "number", "definition": "if(testgcd3(a,b,c)=1,c,chcop3(a,b,random(p..q),p,q))"}, "extendedgcd1": {"language": "jme", "parameters": [["a", "number"], ["b", "number"]], "type": "number", "definition": "\n  \n  \n  if((a|b) or (b|a),\n  \n  0\n  \n  ,\n  \n  extendedgcd2(b,mod(a,b))\n  \n  )\n  \n  "}, "testgcd3": {"language": "jme", "parameters": [["a", "number"], ["b", "number"], ["c", "number"]], "type": "number", "definition": "max(max(gcd(a,b),gcd(a,c)),gcd(b,c))"}, "mdescext1gcd": {"language": "jme", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]], "type": "string", "definition": "\n  \n  \n  if(a<b,\n  \n  '<tr><td>$\\var{a}$</td><td>$\\var{b}-\\var{floor(b/a)}\\times\\var{a}$</td><td>$\\simplify{{c1}a+{c2}b}$</td><td>$\\simplify[std,noleadingMinus]{{d1}a+{d2}b-{floor(b/a)}*({c1}a+{c2}b)}$</td></tr>\\n'+mdescextGCD(a,mod(b,a),c1,c2,d1-floor(b/a)*c1,d2-floor(b/a)*c2,1)\n  \n  ,\n  \n  '<tr><td>$\\var{a}-\\var{floor(a/b)}\\times\\var{b}$</td><td>$\\var{b}$</td><td>$\\simplify[std,noleadingMinus]{{c1}a+{c2}b-{floor(a/b)}*({d1}a+{d2}b)}$</td><td>$\\simplify{{d1}a+{d2}b}$</td></tr>\\n'+mdescextGCD(mod(a,b),b,c1-floor(a/b)*d1,c2-floor(a/b)*d2,d1,d2,1)\n  \n  )\n  \n  "}}, "variable_groups": [], "type": "question", "contributors": [{"name": "Blathnaid Sheridan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/447/"}]}]}], "contributors": [{"name": "Blathnaid Sheridan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/447/"}]}