// Numbas version: exam_results_page_options
{"name": "Solve three congruences with the Chinese Remainder Theorem", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"parts": [{"marks": 0, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showPrecisionHint": false, "allowFractions": false, "scripts": {}, "type": "numberentry", "showCorrectAnswer": true, "minValue": "{age}", "maxValue": "{age}", "marks": 3}], "type": "gapfill", "showCorrectAnswer": true, "steps": [{"type": "information", "prompt": "\n\n\n<p>First you convert the statements about age into 3 simultaneous congruences of the form:<br/>\\[\\begin{eqnarray*}\n\nx\\;&\\equiv&\\;a_1\\;&\\mod&\\;n_1\\\\\n\n\\\\\n\nx\\;&\\equiv&\\;a_2\\;&\\mod&\\;n_2\\\\\n\n\\\\\n\nx\\;&\\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, "marks": 0, "scripts": {}}], "prompt": "\n\n\n<p>Solve the following simultaneous congruences.<br/>On division by $\\var{sa}$ my age gives remainder $\\var{ra}$.<br/>On division by $\\var{sb}$ my age gives remainder $\\var{rb}$.<br/>On division by $\\var{sc}$ my age gives remainder $\\var{rc}$.</p>\n\n\n\n<p>Hold old am I?</p>\n\n\n\n<p>age$\\;=$ [[0]]</p>\n\n\n\n<p>Your value of the age should satisfy $29 \\leq x \\leq 73$</p>\n\n\n\n<p>Steps gives you more information on solving the Chinese Remainder Theorem.</p>\n\n", "stepsPenalty": 0}], "variables": {"ra": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(age,sa)", "name": "ra", "description": ""}, "rb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(age,sb)", "name": "rb", "description": ""}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(ra*ea+rb*eb+rc*ec,n)", "name": "pans", "description": ""}, "co": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[[2,5,7],[2,5,9],[3,4,5],[3,4,7],[3,5,7],[3,5,8],[3,7,10],[4,5,7],[4,5,9]]", "name": "co", "description": ""}, "nb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sc", "name": "nb", "description": ""}, "rc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(age,sc)", "name": "rc", "description": ""}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "co[t][1]", "name": "sb", "description": ""}, "na": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sb*sc", "name": "na", "description": ""}, "age": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(29,31,37,41,43,47,53,59,61,67,71,73)", "name": "age", "description": ""}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb*sc", "name": "n", "description": ""}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "co[t][2]", "name": "sc", "description": ""}, "eb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sb,nb)*nb", "name": "eb", "description": ""}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "co[t][0]", "name": "sa", "description": ""}, "ec": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,nc)*nc", "name": "ec", "description": ""}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..8)", "name": "t", "description": ""}, "ea": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,na)*na", "name": "ea", "description": ""}, "nc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sa*sb", "name": "nc", "description": ""}}, "ungrouped_variables": ["pans", "co", "na", "age", "nc", "ea", "ec", "n", "t", "rb", "rc", "sc", "sb", "sa", "eb", "nb", "ra"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "name": "Solve three congruences with the Chinese Remainder Theorem", "functions": {"chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(10..a-1)))", "parameters": [["a", "number"], ["b", "number"]]}, "mdescext1gcd": {"type": "string", "language": "jme", "definition": "\n\n\nif(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"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n1\n\n,\n\nextendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n\n)\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "string", "language": "jme", "definition": "\n\n\nif (t=0, \n\n'\\n\\n<table  border = \"1\">\\n'+mdescextGCD(a,b,c1,c2,d1,d2,1)\n\n,\n\nif(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\nif(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"]]}}, "variable_groups": [], "showQuestionGroupNames": false, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "", "tags": ["checked2015", "congruences", "coprime", "euclidean algorithm", "gcd", "hcf", "MAS3214", "Modular arithmetic", "modular arithmetic", "simultaneous congruences", "solving equations", "Solving equations", "udf"], "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>"}, "advice": "\n\n\n<p>After converting the statements about age into congruences we obtain the following congruences:<br/>\\[\\begin{eqnarray*}\n\nx\\;&#38;\\equiv&#38;\\;\\var{ra}\\;&#38;\\mod&#38;\\;\\var{sa}\\\\\n\n\\\\\n\nx\\;&#38;\\equiv&#38;\\;\\var{rb}\\;&#38;\\mod&#38;\\;\\var{sb}\\\\\n\n\\\\\n\nx\\;&#38;\\equiv&#38;\\;\\var{rc}\\;&#38;\\mod&#38;\\;\\var{sc}\n\n\\end{eqnarray*}\n\n\\]</p>\n\n\n\n<p>Following the notation as set out 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.</p>\n\n\n\n<p>$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 solution is:\\[\\begin{eqnarray*}\n\nx&#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{age}\\;\\mod\\;\\var{n}\n\n\\end{eqnarray*}\n\n\\]<br/>So my age is $\\var{age}$.</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/"}]}