// Numbas version: finer_feedback_settings
{"name": "John's copy of Solve an equation in modular arithmetic", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"ungrouped_variables": ["r1", "mess", "ans2", "ans3", "csa", "csb", "r", "sb", "sa"], "advice": "<p>We use the extended Euclidean Algorithm to get:</p>\n<p>{mdescextgcd(sa,sb,1,0,0,1)}</p>\n<p>It follows then that we have $\\var{csa}\\times \\var{sa}\\;\\equiv\\;1\\;\\mod \\var{sb}$</p>\n<p>{mess}</p>\n<p>We are asked to solve</p>\n<p>\\[ \\var{sa}x\\;\\equiv\\;\\var{r}\\;\\mod\\;\\var{sb}\\]</p>\n<p>Since <br/>\\[ \\begin{eqnarray*} \\var{ans2}\\times\\var{sa}\\;&amp;\\equiv&amp;\\;1\\;\\mod\\;\\var{sb} \\Rightarrow\\\\ \\var{ans2}\\times \\var{r} \\times \\var{sa}\\;&amp;\\equiv&amp;\\;\\var{r}\\;\\mod\\;\\var{sb}\\Rightarrow\\\\ \\var{ans2*r}\\times \\var{sa}&amp;\\equiv&amp;\\;\\var{r}\\;\\mod\\;\\var{sb} \\end{eqnarray*} \\]</p>\n<p>Hence</p>\n<p>\\[ x=\\var{ans2*r}\\; \\equiv\\;\\var{ans3}\\;\\mod\\;\\var{sb} \\]</p>\n<p>is the solution in the range $0\\le x \\le \\var{sb-1}$.</p>", "variable_groups": [], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "notes": "", "description": "<p>Solving an equation of the form $ax \\equiv b\\;\\textrm{mod}\\;n$ where $a$ and $n$ are coprime.</p>"}, "variablesTest": {"condition": "", "maxRuns": 100}, "functions": {"chcop": {"definition": "if(gcd(a,b)=1,b,chcop(a,random(10..a-1)))", "type": "number", "parameters": [["a", "number"], ["b", "number"]], "language": "jme"}, "extendedgcd1": {"definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n\n", "type": "number", "parameters": [["a", "number"], ["b", "number"]], "language": "jme"}, "mdescextgcd": {"definition": "var table=$('<table border=\"1\">');\nfunction disp(s){\n  return Numbas.jme.display.exprToLaTeX(s,['all'],scope);\n}\n\nfunction mdescextgcd(a,b,c1,c2,d1,d2){\nif((a%b==0) || (b%a==0)){\n  table.append('<tr><td>$\\\\var{'+a+'}$</td><td>$\\\\var{'+b+'}$</td><td>$'+ disp(c1+'a+'+c2+'b')+'$</td><td>$'+ disp(d1+'a+'+d2+'b')+'$</td></tr>');\n}\nelse {\n  if(a<b){\n  var fl=Math.floor(b/a);\n  table.append('<tr><td>$\\\\var{'+a+'}$</td><td>$\\\\var{'+b+'}-\\\\var{'+fl+'}\\\\times\\\\var{'+a+'}$</td><td>$'+ disp(c1+'a+'+c2+'b')+'$</td><td>$'+disp(d1+'a+'+d2+'b-'+fl+'('+c1+'a+'+c2+'b'+')')+'$</td></tr>');\n  mdescextgcd(a,b%a,c1,c2,d1-fl*c1,d2-fl*c2);\n  }\n  else {\nvar fl1=Math.floor(a/b);\ntable.append('<tr><td>$\\\\var{'+a+'}-\\\\var{'+fl1+'}\\\\times\\\\var{'+b+'}$</td><td>$\\\\var{'+b+'}$</td><td>$'+disp(c1+'a+'+c2+'b-'+fl1+'('+d1+'a+'+d2+'b'+')')+'$</td><td>$'+ disp(d1+'a+'+d2+'b')+'$</td></tr>');\nmdescextgcd(a%b,b,c1-fl1*d1,c2-fl1*d2,d1,d2);}\n}\n}\nmdescextgcd(a,b,c1,c2,d1,d2);\n\nreturn table;\n", "type": "html", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]], "language": "javascript"}, "extendedgcd2": {"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\n", "type": "number", "parameters": [["a", "number"], ["b", "number"]], "language": "jme"}}, "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "statement": "", "question_groups": [{"questions": [], "name": "", "pickingStrategy": "all-ordered", "pickQuestions": 0}], "variables": {"r1": {"definition": "random(10..sb-1)", "templateType": "anything", "name": "r1", "group": "Ungrouped variables", "description": ""}, "sb": {"definition": "random(30..60)", "templateType": "anything", "name": "sb", "group": "Ungrouped variables", "description": ""}, "sa": {"definition": "chcop(sb,sb)", "templateType": "anything", "name": "sa", "group": "Ungrouped variables", "description": ""}, "ans3": {"definition": "mod(r*ans2,sb)", "templateType": "anything", "name": "ans3", "group": "Ungrouped variables", "description": ""}, "r": {"definition": "if(r1=sa,r1-1,r1)", "templateType": "anything", "name": "r", "group": "Ungrouped variables", "description": ""}, "ans2": {"definition": "mod(csa,sb)", "templateType": "anything", "name": "ans2", "group": "Ungrouped variables", "description": ""}, "mess": {"definition": "\n\n\nif(csa<0,\n\n'A positive inverse of $\\\\var{sa} \\\\; \\\\mod\\\\;\\\\var{sb}$ in the range $0\\\\le x \\\\le \\\\var{sb-1}$ is given by $\\\\simplify[]{{csa}+{sb}}\\\\;\\\\mod\\\\;\\\\var{sb}\\=\\\\var{mod(csa,sb)}\\\\;\\\\mod\\\\;\\\\var{sb}$\\n\\n.'\n\n,\n\n'Hence the inverse of $\\\\var{sa}$ in $\\\\mathbb{Z}_{\\\\var{sb}}$ is give by $x=\\\\var{mod(csa,sb)}$.'\n\n)\n\n\n", "templateType": "anything", "name": "mess", "group": "Ungrouped variables", "description": ""}, "csa": {"definition": "extendedgcd1(sa,sb)", "templateType": "anything", "name": "csa", "group": "Ungrouped variables", "description": ""}, "csb": {"definition": "extendedgcd2(sa,sb)", "templateType": "anything", "name": "csb", "group": "Ungrouped variables", "description": ""}}, "type": "question", "preamble": {"js": "", "css": ""}, "name": "John's copy of Solve an equation in modular arithmetic", "showQuestionGroupNames": false, "parts": [{"type": "gapfill", "variableReplacements": [], "gaps": [{"variableReplacements": [], "type": "numberentry", "maxValue": "{ans3}", "minValue": "{ans3}", "allowFractions": false, "showCorrectAnswer": true, "marks": 1, "scripts": {}, "correctAnswerFraction": false, "variableReplacementStrategy": "originalfirst", "showPrecisionHint": false}], "showCorrectAnswer": true, "marks": 0, "scripts": {}, "variableReplacementStrategy": "originalfirst", "prompt": "<p>Solve the equation:<br/>\\[ \\var{sa}x\\;\\equiv\\;\\var{r}\\;\\mod\\;\\var{sb}\\]<br/>$x=\\;\\;$ [[0]]</p>\n<p>Your value of $x$ should satisfy $0 \\leq x \\leq \\var{sb-1}$</p>"}], "tags": ["checked2015", "euclidean algorithm", "inverse in a ring", "Modular arithmetic", "modular arithmetic", "solving an equation", "udf", "units in a ring"], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}, {"name": "John Moss", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3481/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}, {"name": "John Moss", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3481/"}]}