// Numbas version: exam_results_page_options
{"name": "Factorise polynomials over Z_5", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"parts": [{"prompt": "<p>&nbsp;$\\simplify[all,!collectnumbers]{{d1}+{c1}X+X^2} = $&nbsp;[[0]]</p>", "gaps": [{"answer": "({a1}+X)({b1}+X)", "vsetRangePoints": 5, "useCustomName": false, "checkingType": "absdiff", "valuegenerators": [{"value": "", "name": "x"}], "vsetRange": [0, 1], "showFeedbackIcon": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "checkingAccuracy": 0.001, "variableReplacements": [], "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "customName": "", "checkVariableNames": true, "unitTests": [], "scripts": {"mark": {"script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);", "order": "after"}}, "answerSimplification": "all,!collectNumbers", "showCorrectAnswer": true, "marks": 1}], "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"prompt": "<p>{poly2} $=$&nbsp;[[0]]</p>", "gaps": [{"answer": "({a}+X)({b[0]}+{b[1]}*X+X^2)", "vsetRangePoints": 5, "useCustomName": false, "checkingType": "absdiff", "valuegenerators": [{"value": "", "name": "x"}], "vsetRange": [0, 1], "showFeedbackIcon": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "checkingAccuracy": 0.001, "variableReplacements": [], "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "customName": "", "checkVariableNames": false, "unitTests": [], "scripts": {"mark": {"script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);", "order": "after"}}, "answerSimplification": "all,!collectNumbers", "showCorrectAnswer": true, "marks": 1}], "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"prompt": "<p>{poly3} $=$&nbsp;[[0]]</p>", "gaps": [{"answer": "({d}+X)({p[0]}+{p[1]}*X+X^2)", "vsetRangePoints": 5, "useCustomName": false, "checkingType": "absdiff", "valuegenerators": [{"value": "", "name": "x"}], "vsetRange": [0, 1], "showFeedbackIcon": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "checkingAccuracy": 0.001, "variableReplacements": [], "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "customName": "", "checkVariableNames": false, "unitTests": [], "scripts": {"mark": {"script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);", "order": "after"}}, "answerSimplification": "all,!collectNumbers", "showCorrectAnswer": true, "marks": 1}], "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"prompt": "<p>{poly4} $=$&nbsp;[[0]]</p>", "gaps": [{"answer": "({q}+X)({m[0]}+{m[1]}*X+{m[2]}*X^2+X^3)", "vsetRangePoints": 5, "useCustomName": false, "checkingType": "absdiff", "valuegenerators": [{"value": "", "name": "x"}], "vsetRange": [0, 1], "showFeedbackIcon": true, "type": "jme", "variableReplacementStrategy": "originalfirst", "checkingAccuracy": 0.001, "variableReplacements": [], "failureRate": 1, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "showPreview": true, "customName": "", "checkVariableNames": false, "unitTests": [], "scripts": {"mark": {"script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);", "order": "after"}}, "answerSimplification": "all,!collectNumbers", "showCorrectAnswer": true, "marks": 1}], "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variables": {"q": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "name": "q", "description": ""}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4 except a)", "name": "d", "description": ""}, "irrpolydeg2mod5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "[[2,0,1],[3,0,1],[1,1,1],[2,1,1],[3,2,1],[4,2,1],[3,3,1],[4,3,1],[1,4,1],[2,4,1]]", "name": "irrpolydeg2mod5", "description": ""}, "poly2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "displaypoly(c)", "name": "poly2", "description": ""}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "irrpolydeg2mod5[random(0..9)]", "name": "b", "description": ""}, "poly3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "displaypoly(h)", "name": "poly3", "description": ""}, "poly4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "displaypoly(r)", "name": "poly4", "description": ""}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4 except a1)", "name": "b1", "description": ""}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "multpolymodn(vector([a,1]),vector(b),5)", "name": "c", "description": ""}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "name": "a1", "description": ""}, "d1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a1*b1,n)", "name": "d1", "description": ""}, "c1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a1+b1,n)", "name": "c1", "description": ""}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "multpolymodn(vector([q,1]),vector(m),5)", "name": "r", "description": ""}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "5", "name": "n", "description": ""}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "name": "a", "description": ""}, "h": {"templateType": "anything", "group": "Ungrouped variables", "definition": "multpolymodn(vector([d,1]),vector(p),5)", "name": "h", "description": ""}, "fx_header": {"templateType": "anything", "group": "Ungrouped variables", "definition": "'$f(x)$'", "name": "fx_header", "description": ""}, "irrpolydeg3mod5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "\n[[1,0,1,1],[1,1,0,1],[4,1,0,1],[1,0,2,1],[4,1,2,1],[3,0,2,1],[2,0,1,1],[3,1,1,1],[2,0,3,1],\n[4,0,3,1],[2,3,0,1],[2,4,0,1],[3,4,0,1],[3,0,4,1]]\n\n", "name": "irrpolydeg3mod5", "description": ""}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "irrpolydeg2mod5[random(0..9)]", "name": "p", "description": ""}, "x_header": {"templateType": "anything", "group": "Ungrouped variables", "definition": "'$x$'", "name": "x_header", "description": ""}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "irrpolydeg3mod5[random(0..13)]", "name": "m", "description": ""}}, "ungrouped_variables": ["a", "a1", "c", "irrpolydeg2mod5", "d", "poly3", "poly2", "m", "n", "q", "p", "d1", "b", "b1", "irrpolydeg3mod5", "h", "c1", "r", "poly4", "x_header", "fx_header"], "variable_groups": [], "name": "Factorise polynomials over Z_5", "functions": {"displaypoly": {"type": "string", "language": "jme", "definition": "displaystring(listtopoly(a))", "parameters": [["a", "list"]]}, "displaystring": {"type": "string", "language": "javascript", "definition": "return '$'+Numbas.jme.display.exprToLaTeX(s,['all','!collectnumbers'],scope)+'$';", "parameters": [["s", "string"]]}, "listtopoly": {"type": "string", "language": "javascript", "definition": "return p.map(function(coefficient,power){ return coefficient+'*X^('+power+')'; }).join('+');", "parameters": [["p", "list"]]}, "multpolymodn": {"type": "list", "language": "jme", "definition": "map(mod(x,n),x,list(multpoly(p,q)))", "parameters": [["p", "vector"], ["q", "vector"], ["n", "number"]]}, "multpoly": {"type": "vector", "language": "jme", "definition": "\n//uses p(x)q(x)=p(0)q(x)+(p(x)-p(0))/x * xq(x)to multiply polys.\nif(length(list(p))=1,p[0]*q,  \n  p[0]*q+multpoly(vector(list(p)[1..length(list(p))]),vector([0]+list(q))))\n\n\n", "parameters": [["p", "vector"], ["q", "vector"]]}}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "<p>Factorize the following polynomials over $\\mathbb{Z}_{\\var{n}}$ into their monic irreducible factors.</p>\n<p>You must enter all polynomials with coefficients in $\\mathbb{Z}_{\\var{n}}=\\{0,\\;1,\\;2,\\;3,\\;4\\}$ (and no negative coefficients).&nbsp;</p>", "tags": ["checked2015"], "rulesets": {}, "preamble": {"css": "", "js": "function split(tree,op) {\n  var factors = [];\n  var queue = [tree];\n  var rule = new Numbas.jme.rules.Rule('?;a'+op+'(?`*);b');\n  while(queue.length) {\n    var t = queue.pop();\n    var res = rule.match(t);\n    if(res && res.b!==undefined) {\n      queue.push(res.a,res.b);\n    } else {\n      factors.push(t);\n    }\n  }\n  return factors;\n}\nwindow.split = split;\n\nvar rule_term = new Numbas.jme.rules.Rule('(`+-$n;number `| `+-$n`?*x^($n`?;d))','');\n\nquestion.polynomial_reduced = function(tree,n) {\n  if(typeof tree=='string') {\n    tree = Numbas.jme.compile(tree);\n  }\n  var factors = split(tree,'*');\n  var ok = factors.every(function(f) {\n    var terms = split(f,'+');\n    var degree = 0;\n    terms.forEach(function(t) {\n      var m = rule_term.match(t);\n      if(!m) {\n        var expr = Numbas.jme.display.treeToJME(t);\n        throw(new Error(\"Invalid term \"+expr));\n      }\n      var d;\n      if(m.number) {\n        d = 0;\n      } else if(m.d!==undefined) {\n        d = m.d.tok.value;\n      } else {\n        d = 1;\n      }\n      degree = Math.max(degree,d);\n    });\n    \n    if(degree<=1) {\n      return true;\n    }\n\n    var zeros = 0;\n    for(var i=0;i<n;i++) {\n      var v = Numbas.jme.builtinScope.evaluate(f,{x:i});\n      zeros += (v.value%n)==0;\n    }\n    return zeros==0;\n  });\n  return ok;\n}\n\n// if the part has been marked correct by the JME marking function,\n// check that it's the product of irreducible monic polynomials in Z_n\nquestion.mark_polynomial_reduced = function(part,n) {\n  if(part.credit<1) {\n    return;\n  }\n  var reduced;\n  try {\n    reduced = question.polynomial_reduced(part.studentAnswer,n);\n  } catch(e) {\n    reduced = false;\n  }\n\n  if(!reduced) {\n    part.setCredit(0,\"Your answer is not a product of monic irreducible factors\");\n  }\n}"}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Factorise 4 polynomials over $\\mathbb{Z}_5$.</p>"}, "extensions": [], "advice": "<p>Looking for a linear factor of a polynomial is easy over $\\mathbb{Z}_{\\var{n}}$: you try the values $X = 1, \\; 2, \\; 3, \\; 4$ and if the polynomial evaluates to $0 \\pmod{\\var{n}}$ for a value $X = n$ then you have a factor $(X-n)$.</p>\n<p><strong>Note also that any integers in your answers have to be positive.&nbsp;</strong> You can easily convert any negative integer into a positive integer $\\bmod \\var{n}$ by adding multiples of $\\var{n}$.</p>\n<h4>a)</h4>\n<p>For $f(X)= \\simplify[all,!collectnumbers]{{d1}+{c1}X+X^2}$, trying the values $X = 1, \\; 2, \\; 3, \\; 4$ gives</p>\n<p>{table([[x_header,'1','2','3','4'],[fx_header]+map(d1+c1*x+x^2,x,1..4)])}</p>\n<p>and on evaluating $\\bmod \\var{n}$ we see that $X=\\var{n-a1}$ and $X=\\var{n-b1}$ give $0 \\bmod \\var{n}$ hence $X-\\var{n-a1} \\equiv X+\\var{a1} \\pmod{\\var{n}}$ and $X-\\var{n-b1} \\equiv X+\\var{b1} \\pmod{\\var{n}}$ are factors.</p>\n<p>So, we obtain</p>\n<p>\\[f(X)=(\\var{a1}+X)(\\var{b1}+X)\\]</p>\n<h4>b)</h4>\n<p>Putting the values $X=1 ,\\;2,\\;3,\\;4$ into $f(X)=\\var{poly2}$ gives $f(\\var{n-a})=0 \\pmod{\\var{n}}$, hence $X-\\var{n-a} \\equiv&nbsp;X+\\var{a} \\pmod{\\var{n}}$ is a factor.</p>\n<p>We see on dividing $\\var{poly2}$ by $X+\\var{a}$ that</p>\n<p>\\[ \\var{poly2} \\equiv \\simplify[all,!collectNumbers,!noleadingMinus]{({a}+X)({b[0]}+{b[1]}X+X^2)} \\pmod{\\var{n}} \\]</p>\n<p>It is easy to check that $\\simplify[all,!collectNumbers,!noleadingMinus]{{b[0]}+{b[1]}X+X^2}$ is irreducible as it is never zero for $X \\in \\mathbb{Z}_5$ and therefore has no linear factors.</p>\n<p>So factorising into irreducible factors gives</p>\n<p>\\[ f(X)=\\simplify[all,!collectNumbers,!noleadingMinus]{({a}+X)({b[0]}+{b[1]}X+X^2)} \\]</p>\n<h4>c)</h4>\n<p>Putting the values $X=1, \\; 2, \\; 3, \\; 4$ into $f(X)=\\var{poly3}$ gives $f(\\var{n-d})=0 \\pmod{\\var{n}}$, hence $X-\\var{n-d} \\equiv X+\\var{d} \\pmod{var{n}}$ is a factor.</p>\n<p>We see on dividing $\\var{poly3}$ by $X+\\var{d}$ that</p>\n<p>\\[ \\var{poly3} \\equiv \\simplify[all,!collectNumbers,!noleadingMinus]{({d}+X)({p[0]}+{p[1]}X+X^2)} \\pmod{\\var{n}} \\]</p>\n<p>It is easy to check that $\\simplify[all,!collectNumbers,!noleadingMinus]{{p[0]}+{p[1]}X+X^2}$ is irreducible as it is never zero for $X \\in \\mathbb{Z}_5$ and therefore has no linear factors.</p>\n<p>So factorising into irreducible factors gives</p>\n<p>\\[ f(X)=\\simplify[all,!collectNumbers,!noleadingMinus]{({d}+X)({p[0]}+{p[1]}X+X^2)} \\]</p>\n<h4>d)</h4>\n<p>Putting the values $X=1, \\; 2, \\; 3, \\; 4$ into $f(X)=\\var{poly4}$ gives $f(\\var{n-q})=0 \\mod \\var{n}$, hence $X-\\var{n-q} \\equiv X+\\var{q} \\pmod{var{n}}$ is a factor.</p>\n<p>We see on dividing $\\var{poly4}$ by $X+\\var{q}$ that</p>\n<p>\\[ \\var{poly4} \\equiv \\simplify[all,!collectNumbers,!noleadingMinus]{({q}+X)({m[0]}+{m[1]}X+{m[2]}X^2+X^3)} \\pmod{\\var{n}} \\]</p>\n<p>A cubic polynomial is reducible if and only if it has a linear factor, so we can check by trying values $X \\in \\mathbb{Z}_{\\var{n}}$ to see if we get $f(X)=0$.</p>\n<p>We can&nbsp;confirm&nbsp;that $f(X) \\neq 0,\\;\\forall X \\in \\mathbb{Z}_{\\var{n}}$ and so $\\simplify[all,!collectNumbers,!noleadingMinus]{{m[0]}+{m[1]}X+{m[2]}X^2+X^3}$ is irreducible.</p>\n<p>So factorising into irreducible factors gives: \\[f(X)=\\simplify[all,!collectNumbers,!noleadingMinus]{({q}+X)({m[0]}+{m[1]}X+{m[2]}X^2+X^3)}\\]</p>", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}