// Numbas version: exam_results_page_options
{"name": "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": [{"variable_groups": [], "variables": {"sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(12..20)", "description": "", "name": "sb"}, "rb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..sb-1)", "description": "", "name": "rb"}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(ra*ea+rb*eb+rc*ec,n)", "description": "", "name": "pans"}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop3(sa,sb,sb,2,sa-1)", "description": "", "name": "sc"}, "nb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sc", "description": "", "name": "nb"}, "rc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..sc-1)", "description": "", "name": "rc"}, "ra": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sa-1)", "description": "", "name": "ra"}, "na": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sb*sc", "description": "", "name": "na"}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,8,sb-1)", "description": "", "name": "sa"}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "pans", "description": "", "name": "ans"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "na*sa", "description": "", "name": "n"}, "eb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sb,nb)*nb", "description": "", "name": "eb"}, "nc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb", "description": "", "name": "nc"}, "ec": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,nc)*nc", "description": "", "name": "ec"}, "ea": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,na)*na", "description": "", "name": "ea"}}, "ungrouped_variables": ["pans", "na", "nb", "nc", "ea", "rc", "ec", "n", "ra", "rb", "ans", "sc", "sb", "sa", "eb"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "name": "Solve three congruences using Chinese Remainder Theorem", "functions": {"mdescext1gcd": {"type": "string", "language": "jme", "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  ", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "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  ", "parameters": [["a", "number"], ["b", "number"]]}, "testgcd3": {"type": "number", "language": "jme", "definition": "max(max(gcd(a,b),gcd(a,c)),gcd(b,c))", "parameters": [["a", "number"], ["b", "number"], ["c", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "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  ", "parameters": [["a", "number"], ["b", "number"]]}, "chcop3": {"type": "number", "language": "jme", "definition": "if(testgcd3(a,b,c)=1,c,chcop3(a,b,random(p..q),p,q))", "parameters": [["a", "number"], ["b", "number"], ["c", "number"], ["p", "number"], ["q", "number"]]}, "chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(p..q),p,q))", "parameters": [["a", "number"], ["b", "number"], ["p", "number"], ["q", "number"]]}, "mdescextgcd": {"type": "string", "language": "jme", "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  ", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"], ["t", "number"]]}}, "showQuestionGroupNames": false, "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans}", "minValue": "{ans}", "correctAnswerFraction": false, "marks": 4, "showPrecisionHint": false}], "type": "gapfill", "prompt": "\n  \n  \n  <p>Solve the following simultaneous congruences:<br/>\\[\\begin{eqnarray*}\n  \n  x\\;&#38;\\equiv&#38;\\;\\var{ra}\\;&#38;\\mod&#38;\\;\\var{sa}\\\\\n  \n  \\\\\n  \n  x\\;&#38;\\equiv&#38;\\;\\var{rb}\\;&#38;\\mod&#38;\\;\\var{sb}\\\\\n  \n  \\\\\n  \n  x\\;&#38;\\equiv&#38;\\;\\var{rc}\\;&#38;\\mod&#38;\\;\\var{sc}\n  \n  \\end{eqnarray*}\n  \n  \\]<br/>$x=\\;\\;$ [[0]]</p>\n  \n  \n  \n  <p>Your value of $x$ should satisfy $0 \\leq x \\lt \\var{n}$</p>\n  \n  \n  \n  <p>Steps gives you information on the Chinese Remainder Theorem and the steps you need to take to solve the congruences.</p>\n  \n  ", "steps": [{"type": "information", "prompt": "\n  \n  \n  <p>Given the simultaneous congruences:<br/>\\[\\begin{eqnarray*}\n  \n  x\\;&\\equiv&\\;a_1\\;&\\mod&\\;n_1\\\\\n  \n  \\\\\n  \n  x\\;&\\equiv&\\;a_2\\;&\\mod&\\;n_2\\\\\n  \n  \\\\\n  \n  x\\;&\\equiv&\\;a_3\\;&\\mod&\\;n_3\n  \n  \\end{eqnarray*}\n  \n  \\]<br/>where $\\operatorname{gcd}(n_1,n_2,n_3)=1$ we first observe that:</p>\n  \n  \n  \n  <p>$N_1=n_2 n_3$ and $n_1$ are coprime, $N_2=n_1 n_3$ and $n_2$ are coprime, $N_3=n_1 n_2$ and $n_3$ are coprime.</p>\n  \n  \n  \n  <p>So there is an inverse $x_1$ of $N_1$ in $Z_{n_1}$ such that $N_1x_1\\equiv 1 \\;\\mod\\;n_1$. Let $E_1=N_1x_1$, and similarly:</p>\n  \n  \n  \n  <p>There is an inverse $x_2$ of $N_2$ in $Z_{n_2}$ such that $N_2x_2\\equiv 1 \\;\\mod\\;n_2$. Let $E_2=N_2x_2$.</p>\n  \n  \n  \n  <p>There is an inverse $x_3$ of $N_3$ in $Z_{n_3}$ such that $N_3x_3\\equiv 1 \\;\\mod\\;n_3$. Let $E_3=N_3x_3$.</p>\n  \n  \n  \n  <p>Then $x=a_1 E_1+a_2 E_2  + a_3 E_3 \\;\\mod\\;n_1n_2n_3$ is a solution to the simultaneous congruences.</p>\n  \n  \n  \n  <p>See your notes for a full explanation.</p>\n  \n  ", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "", "tags": ["checked2015", "Chinese Remainder Theorem", "congruences", "coprime", "euclidean algorithm", "gcd", "MAS3214", "Modular arithmetic", "modular arithmetic", "simultaneous congruences", "solving equations", "Solving equations"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "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>"}, "variablesTest": {"condition": "", "maxRuns": 100}, "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  ", "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}