// Numbas version: finer_feedback_settings
{"name": "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": [{"variable_groups": [], "variables": {"sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(30..60)", "description": "", "name": "sb"}, "r1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(10..sb-1)", "description": "", "name": "r1"}, "ans3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(r*ans2,sb)", "description": "", "name": "ans3"}, "ans2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(csa,sb)", "description": "", "name": "ans2"}, "mess": {"templateType": "anything", "group": "Ungrouped variables", "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", "description": "", "name": "mess"}, "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)", "description": "", "name": "sa"}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(r1=sa,r1-1,r1)", "description": "", "name": "r"}}, "ungrouped_variables": ["r1", "mess", "ans2", "ans3", "csa", "csb", "r", "sb", "sa"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "name": "Solve an equation in modular arithmetic", "showQuestionGroupNames": false, "functions": {"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\n", "parameters": [["a", "number"], ["b", "number"]]}, "chcop": {"type": "number", "language": "jme", "definition": "if(gcd(a,b)=1,b,chcop(a,random(10..a-1)))", "parameters": [["a", "number"], ["b", "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\n", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "html", "language": "javascript", "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", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}}, "parts": [{"showCorrectAnswer": true, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "{ans3}", "minValue": "{ans3}", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "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>", "variableReplacements": [], "marks": 0}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "", "tags": ["checked2015", "euclidean algorithm", "inverse in a ring", "Modular arithmetic", "modular arithmetic", "solving an equation", "udf", "units in a ring"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "<p>Solving an equation of the form $ax \\equiv b\\;\\textrm{mod}\\;n$ where $a$ and $n$ are coprime.</p>"}, "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>", "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/"}]}