// Numbas version: finer_feedback_settings
{"name": "Solve a pair of congruences", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"s1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sd-1)", "description": "", "name": "s1"}, "r1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5..sb-1)", "description": "", "name": "r1"}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(10..20)", "description": "", "name": "sb"}, "csc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sc,sd)", "description": "", "name": "csc"}, "pans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1*sd*invd+a2*sb*invb", "description": "", "name": "pans"}, "sc": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sd,sd,3,sd-1)", "description": "", "name": "sc"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(s*ansp2,sd)", "description": "", "name": "a2"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(r*ansp1,sb)", "description": "", "name": "a1"}, "sd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,sb-5,sb+5)", "description": "", "name": "sd"}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(pans,sd*sb)", "description": "", "name": "ans"}, "invd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sd,sb)", "description": "", "name": "invd"}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(r1=sa,r1-1,r1)", "description": "", "name": "r"}, "temp": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sd*sb", "description": "", "name": "temp"}, "csd": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sc,sd)", "description": "", "name": "csd"}, "s": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s1=sc,s1-1,s1)", "description": "", "name": "s"}, "csb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,sb)", "description": "", "name": "csb"}, "csa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sa,sb)", "description": "", "name": "csa"}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "chcop(sb,sb,5,sb-1)", "description": "", "name": "sa"}, "ansp2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(csc>0, mod(csc,sd),sd+mod(csc,sd))", "description": "", "name": "ansp2"}, "ansp1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(csa>0, mod(csa,sb),sb+mod(csa,sb))", "description": "", "name": "ansp1"}, "invb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sb,sd)", "description": "", "name": "invb"}}, "ungrouped_variables": ["pans", "ansp1", "sb", "r1", "temp", "csd", "s1", "csa", "csc", "csb", "a1", "s", "r", "ans", "sc", "ansp2", "sa", "invd", "invb", "a2", "sd"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "name": "Solve a pair of congruences", "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"]]}, "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"]]}, "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"]]}, "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 equations:<br/>\\[\\begin{eqnarray*}\n  \n  \\var{sa}x\\;&#38;\\equiv&#38;\\;\\var{r}\\;\\mod\\;\\var{sb}\\\\\n  \n  \\\\\n  \n  \\var{sc}x\\;&#38;\\equiv&#38;\\;\\var{s}\\;\\mod\\;\\var{sd}\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{sb*sd}$</p>\n  \n  ", "steps": [{"type": "information", "prompt": "<p>If we have two simultaneous congruences:<br/>\\[\\begin{eqnarray*} c_1x\\;&amp;\\equiv&amp;\\;b_1\\;&amp;\\mod&amp;\\;n_1\\\\ \\\\ c_2x\\;&amp;\\equiv&amp;\\;b_2\\;&amp;\\mod&amp;\\;n_2\\\\ \\end{eqnarray*} \\]<br/>where $\\operatorname{gcd}(c_1,n_1)=1$ and $\\operatorname{gcd}(c_2,n_2)=1$</p>\n<p>Then we can find the inverse $d_1$ of $c_1$ in $\\mathbb{Z}_{n_1}$ and the inverse $d_2$ of $c_2$ in $\\mathbb{Z}_{n_2}$ using the Extended Euclidean Algorithm or by inspection.</p>\n<p>Multiplying both sides of the first equation by $d_1$ and multiplying both sides of the second equation by $d_2$ gives the equations in the form:</p>\n<p>\\[\\begin{eqnarray*} x\\;&amp;\\equiv&amp;\\;a_1\\;&amp;\\mod&amp;\\;n_1\\\\ \\\\ x\\;&amp;\\equiv&amp;\\;a_2\\;&amp;\\mod&amp;\\;n_2\\\\ \\end{eqnarray*} \\]</p>\n<p>Since $n_1$ and $n_2$ are coprime there is a simple formula to find a solution $\\mod\\;n$ where $n=n_1n_2$</p>\n<p>This is given by:<br/>\\[x=a_1 n_2 y_2+a_2 n_1 y_1 \\mod\\;n\\]<br/>where $y_2 = n_2^{-1} \\mod\\;n_1$ and $y_1= n_1^{-1} \\mod\\;n_2$.</p>\n<p>This works as we have:</p>\n<p>$ x \\mod\\; n_1=a_1 \\times 1+0=a_1 \\mod\\;n_1$ as $n_2 y_2 = 1 \\mod \\;n_1,\\;\\;a_2 n_1 y_1=0\\mod\\;n_1$</p>\n<p>$ x \\mod\\; n_2=0+a_2 \\times 1=a_2 \\mod\\;n_2$ as $n_1 y_1 = 1 \\mod \\;n_2,\\;\\;a_1 n_2 y_2=0\\mod\\;n_2$</p>", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "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 two simultaneous congruences:</p>\n<p>\\[\\begin{eqnarray*} c_1x\\;&amp;\\equiv&amp;\\;b_1\\;&amp;\\mod&amp;\\;n_1\\\\ c_2x\\;&amp;\\equiv&amp;\\;b_2\\;&amp;\\mod&amp;\\;n_2\\\\ \\end{eqnarray*} \\] where $\\operatorname{gcd}(c_1,n_1)=1,\\;\\operatorname{gcd}(c_2,n_2)=1,\\;\\operatorname{gcd}(n_1,n_2)=1$</p>"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "\n  \n  \n  <p>Using the method given in Steps:</p>\n  \n  \n  \n  <p>First we find:</p>\n  \n  \n  \n  <p>The inverse of $\\var{sa}$ in $\\mathbb{Z}_{\\var{sb}}$ is $\\var{ansp1}$, the inverse of  $\\var{sc}$ in $\\mathbb{Z}_{\\var{sd}}$ is $\\var{ansp2}$.</p>\n  \n  \n  \n  <p>(You can use the Extended Euclidean Algorithm to do this, and and your answers may differ from those above, but must be the same $\\mod\\;\\var{sb}$  and $\\mod\\;\\var{sd}$ respectively.)</p>\n  \n  \n  \n  <p>Then multiplying both sides of the first equation by $\\var{ansp1}$ and both sides of the second equation by $\\var{ansp2}$ gives the pair of equations:</p>\n  \n  \n  \n  <p>\\[\\begin{eqnarray*}\n  \n  x\\;&#38;\\equiv&#38;\\;\\var{a1}\\;\\mod\\;\\var{sb}\\\\\n  \n  \\\\\n  \n  x\\;&#38;\\equiv&#38;\\;\\var{a2}\\;\\mod\\;\\var{sd}\n  \n  \\end{eqnarray*}\n  \n  \\]</p>\n  \n  \n  \n  <p>Now we use the formula given in Steps.</p>\n  \n  \n  \n  <p>Let $n=\\var{sb}\\times \\var{sd}=\\var{sb*sd}$</p>\n  \n  \n  \n  <p>Since $\\var{sb}$ and $\\var{sd}$ are coprime we find by using the Extended Euclidean Algorithm that:</p>\n  \n  \n  \n  <p>1) The inverse of $\\var{sb}\\;\\mod\\;\\var{sd}$ is $y_1=\\var{invb}$</p>\n  \n  \n  \n  <p>2) The inverse of $\\var{sd}\\;\\mod\\;\\var{sb}$ is $y_2=\\var{invd}$</p>\n  \n  \n  \n  <p>(You may get different values, but they should be the same as those above $\\mod\\;\\var{sd}$ and $\\mod\\;\\var{sb}$ respectively.)</p>\n  \n  \n  \n  <p>So $x=\\simplify[std]{{a1}* {sd} * {invd}+{a2}*{sb}*{invb}}=\\var{pans}=\\var{ans} \\;\\mod\\;\\var{sb*sd}$</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/"}]}