// Numbas version: exam_results_page_options
{"name": "Modular Arithmetic: composite multiplication table", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Modular Arithmetic: composite multiplication table", "tags": [], "metadata": {"description": "<p>Introduction to modular arithmetic in $\\mathbb Z_b$ using a multiplication table and lookup with coprime $b \\in \\mathbb N$.</p>", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "<p>Here is the multiplication table in modulo $\\var{p}$. It's a bit different to the multiplication table for the previous question.</p>\n<p style=\"text-align: center;\">{table(p)}</p>\n<p style=\"text-align: left;\">Notice that in row $a$ the numbers are all multiples of $\\gcd(a,\\var{p})$.</p>", "advice": "<p>This question introduces the concept of solving linear equations of the form $ax \\equiv c \\pmod{b}$, and the idea that there are multiple solutions when $\\gcd(a,b) &gt; 1$.</p>", "rulesets": {}, "extensions": [], "variables": {"p": {"name": "p", "group": "Ungrouped variables", "definition": "random(8,9,12)", "description": "", "templateType": "anything"}, "factor": {"name": "factor", "group": "Ungrouped variables", "definition": "if(1=mod(p,2), 3, 2)", "description": "", "templateType": "anything"}, "x1": {"name": "x1", "group": "Ungrouped variables", "definition": "random(2..p except [p,factor,otherfactor])", "description": "", "templateType": "anything"}, "otherfactor": {"name": "otherfactor", "group": "Ungrouped variables", "definition": "p/factor", "description": "", "templateType": "anything"}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "random(2..p except [p,factor,otherfactor,x1])", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "gcd(x1,p) != 1 && gcd(p,a) != 1 ", "maxRuns": 100}, "ungrouped_variables": ["p", "factor", "otherfactor", "x1", "a"], "variable_groups": [], "functions": {"table": {"parameters": [["p", "number"]], "type": "html", "language": "javascript", "definition": "var table = \"<table>\";\n\n// headings\ntable += \"<tr><th>$\\\\times$</th>\";\nfor (var i = 0; i < p; i++) {\n  table += \"<th>\" + i + \"</th>\";\n}\ntable += \"</tr>\";\n\n// rows\nfor (var i = 0; i < p; i++) {\n  table += \"<tr><th>\" + i + \"</th>\";\n  for (var j = 0; j < p; j++) {\n    table += \"<td>\" + (i*j % p) + \"</td>\";\n  }\n  table += \"</tr>\";\n}\n\ntable += \"</table>\";\n\nreturn table;"}}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {"mark": {"script": "// extract question variables\nvar variables = this.question.scope.variables;\nvar unwrap = Numbas.jme.unwrapValue;\nvar p = unwrap(variables.p);\n\n// any number such that gcd(ans,p) > 1 will do\nvar tree;\ntry {\n  tree = Numbas.jme.compile(\"gcd(\" + this.studentAnswer + \",\" + p + \")\");\n  var gcd = unwrap(Numbas.jme.evaluate(tree,this.question.scope));\n  tree = Numbas.jme.compile(this.studentAnswer);\n  var ans = unwrap(Numbas.jme.evaluate(tree,this.question.scope));\n  \n  if (1 < gcd) { \n    this.setCredit(1,\"$\" + ans + \" x = 1 \\\\pmod{\" + p +\"}$ has no solutions.\");    \n  } else if (0 == ans) {\n    this.setCredit(0,\"You must choose a non-zero number\");\n  } else {\n    // ax=1 has a solution\n    var x;\n    for (x=1; (ans*x % p > 1) && x < p; x++);\n    this.setCredit(0,\"$\" + ans + \"$ has an inverse because $\" + ans + \" \\\\times \" + x + \" = 1 \\\\pmod{\" + p +\"}$.\" );\n  }\n  \n}\ncatch(e) {\n    this.markingComment(e);\n}", "order": "instead"}, "validate": {"script": "return true;", "order": "instead"}}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>Use the multiplication table to find a non-zero number $a$ such that $a\\equiv1 \\pmod{\\var{p}}$ has no solutions.</p>\n<p>Hint: look for row $a$ where $\\gcd(a,\\var{p}) &gt; 1$.</p>", "minValue": "{factor}", "maxValue": "{factor}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {"mark": {"script": "// extract question variables\nvar variables = this.question.scope.variables;\nvar unwrap = Numbas.jme.unwrapValue;\nvar p = unwrap(variables.p);\nvar a = unwrap(variables.a);\nvar x = unwrap(variables.x1);\n\n// compute its derivative\nvar tree;\ntry {\n  tree = Numbas.jme.compile(this.studentAnswer);\n  var ans = unwrap(Numbas.jme.evaluate(tree,this.question.scope));\n  \n  if (((a*x) %p) == ((a*ans) % p)) { \n    this.setCredit(1,\"$\" + a + \" \\\\times \" + ans + \"  = \" + (a*x %p) + \" \\\\pmod{\" + p +\"}$.\");\n    if (ans >= p || ans < 0) {\n        this.multCredit(0.5,\"But in modulo $\" +p+\"$ arithmetic you should present your answer as an integer between $0$ and $\" + (p-1)+ \"$. \");\n    }\n  } else { \n    this.setCredit(0,\"You were asked to find $x$ where $\" + a + \" x = \" + ((a*x) %p) + \" \\\\pmod{\" + p +\"}$. But your answer gives $\" + a + \" \\\\times \" + ans + \" = \" + ((a*ans) %p) + \" \\\\pmod{\" + p +\"}$.\");\n  }\n  \n}\ncatch(e) {\n    this.markingComment(e);\n}", "order": "instead"}, "validate": {"script": "return true;", "order": "instead"}}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>Solve $ \\var{a} x \\equiv \\var{mod(a*x1,p)} \\pmod{\\var{p}}$ for $x$.</p>", "minValue": "{x1}", "maxValue": "{x1}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>There are two solutions to $\\var{2*a} x \\equiv \\var{mod(2*a*x1,2*p)} \\pmod{\\var{2*p}}$ which are</p>\n<p style=\"text-align: center;\">$x = $ [[0]] and [[1]].</p>", "stepsPenalty": 0, "steps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": "0", "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p style=\"text-align: left;\">Notice that each part of the equation $\\var{2*a} x \\equiv \\var{mod(2*a*x1,2*p)} \\pmod{\\var{2*p}}$ has a common factor of</p>", "minValue": "2", "maxValue": "2", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "information", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>This common factor can be removed to obtain an equivalent equation with smaller modulus:</p>\n<p style=\"text-align: center;\">$\\var{a} x \\equiv \\var{mod(a*x1,p)} \\pmod{\\var{p}}$.</p>\n<p style=\"text-align: left;\">Your answer to part b is a solution to this equation, let's call it $x$. In fact all the numbers</p>\n<p style=\"text-align: center;\">$ \\ldots, x-\\var{2*p},x-\\var{p},x,x+\\var{p},x+\\var{2*p},\\ldots $</p>\n<p style=\"text-align: left;\">are solutions to this equation, and in modulo $\\var{p}$ they are all the same. So there is really only one answer in modulo $\\var{p}$.</p>\n<p style=\"text-align: left;\">But in modulo $\\var{2*p}$ the numbers $x$ and $x+\\var{p}$ are different. So there are two answers in modulo $\\var{2*p}$ which differ by $\\var{p}$.</p>"}], "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": "1", "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {"mark": {"script": "// extract question variables\nvar variables = this.question.scope.variables;\nvar unwrap = Numbas.jme.unwrapValue;\nvar p = 2*unwrap(variables.p);\nvar a = 2*unwrap(variables.a);\nvar x = unwrap(variables.x1);\n\nvar gap0 = Numbas.util.parseNumber(this.parentPart.gaps[0].studentAnswer);\n\nif (((a*gap0 % p)+p)%p == (a*x) % p) {\n  this.setCredit(1,\"$\" + a + \"\\\\times \" + gap0 + \" = \" + (a*x) % p + \" \\\\pmod{\" + p + \"}$.\");\n} else {\n  this.setCredit(0,\"$\" + a + \"\\\\times \" + gap0 + \" = \" + (a*gap0) % p + \" \\\\neq \" + (a*x) % p + \" \\\\pmod{\" + p + \"}$.\");\n}", "order": "instead"}, "validate": {"script": "return Numbas.util.isNumber(this.studentAnswer,false,\"\");", "order": "instead"}}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "minValue": "{x1}", "maxValue": "{x1}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {"mark": {"script": "// extract question variables\nvar variables = this.question.scope.variables;\nvar unwrap = Numbas.jme.unwrapValue;\nvar p = 2*unwrap(variables.p);\nvar a = 2*unwrap(variables.a);\nvar x = unwrap(variables.x1);\n\ntry {\n  // get the student's answers to the first two steps\n  var gap0 = Numbas.util.parseNumber(this.parentPart.gaps[0].studentAnswer);\n  var gap1 = Numbas.util.parseNumber(this.parentPart.gaps[1].studentAnswer);\n  \n  if ((gap0 % p + p)%p == (gap1 % p + p)%p) {\n    this.setCredit(0,\"You must choose different solutions.\");\n    return;\n  } else if (((a*gap1 % p)+p)%p == (a*x % p)) {\n    this.setCredit(1,\"$\" + a + \"\\\\times \" + gap1 + \" = \" + (a*x) % p + \" \\\\pmod{\" + p + \"}$.\");\n  } else {\n    this.setCredit(0,\"$\" + a + \"\\\\times \" + gap1 + \" = \" + (a*gap1) % p + \" \\\\neq \" + (a*x) % p + \" \\\\pmod{\" + p + \"}$.\");\n  }\n  //var ans = unwrap(Numbas.jme.evaluate(tree,this.question.scope));\n  \n}\ncatch(e) {\n    this.markingComment(e);\n}", "order": "instead"}, "validate": {"script": "return Numbas.util.isNumber(this.studentAnswer,false,\"\");", "order": "instead"}}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "minValue": "{x1+p}", "maxValue": "{x1+p}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "sortAnswers": false}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}]}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}