// Numbas version: exam_results_page_options
{"name": "Luis's copy of 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": [{"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", "MAS2213"], "functions": {"displaystring": {"definition": "return '$'+Numbas.jme.display.exprToLaTeX(s,['all','!collectnumbers'],scope)+'$';", "language": "javascript", "type": "string", "parameters": [["s", "string"]]}, "displaypoly": {"definition": "displaystring(listtopoly(a))", "language": "jme", "type": "string", "parameters": [["a", "list"]]}, "multpoly": {"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", "language": "jme", "type": "vector", "parameters": [["p", "vector"], ["q", "vector"]]}, "listtopoly": {"definition": "return p.map(function(coefficient,power){ return coefficient+'*X^('+power+')'; }).join('+');", "language": "javascript", "type": "string", "parameters": [["p", "list"]]}, "multpolymodn": {"definition": "map(mod(x,n),x,list(multpoly(p,q)))", "language": "jme", "type": "list", "parameters": [["p", "vector"], ["q", "vector"], ["n", "number"]]}}, "question_groups": [{"name": "", "pickQuestions": 0, "pickingStrategy": "all-ordered", "questions": []}], "variables": {"d": {"group": "Ungrouped variables", "definition": "random(1..4 except a)", "templateType": "anything", "description": "", "name": "d"}, "a1": {"group": "Ungrouped variables", "definition": "random(1..4)", "templateType": "anything", "description": "", "name": "a1"}, "r": {"group": "Ungrouped variables", "definition": "multpolymodn(vector([q,1]),vector(m),5)", "templateType": "anything", "description": "", "name": "r"}, "a": {"group": "Ungrouped variables", "definition": "random(1..4)", "templateType": "anything", "description": "", "name": "a"}, "b1": {"group": "Ungrouped variables", "definition": "random(1..4 except a1)", "templateType": "anything", "description": "", "name": "b1"}, "q": {"group": "Ungrouped variables", "definition": "random(1..4)", "templateType": "anything", "description": "", "name": "q"}, "n": {"group": "Ungrouped variables", "definition": "5", "templateType": "anything", "description": "", "name": "n"}, "fx_header": {"group": "Ungrouped variables", "definition": "'$f(x)$'", "templateType": "anything", "description": "", "name": "fx_header"}, "poly3": {"group": "Ungrouped variables", "definition": "displaypoly(h)", "templateType": "anything", "description": "", "name": "poly3"}, "poly4": {"group": "Ungrouped variables", "definition": "displaypoly(r)", "templateType": "anything", "description": "", "name": "poly4"}, "irrpolydeg3mod5": {"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", "templateType": "anything", "description": "", "name": "irrpolydeg3mod5"}, "c": {"group": "Ungrouped variables", "definition": "multpolymodn(vector([a,1]),vector(b),5)", "templateType": "anything", "description": "", "name": "c"}, "b": {"group": "Ungrouped variables", "definition": "irrpolydeg2mod5[random(0..9)]", "templateType": "anything", "description": "", "name": "b"}, "p": {"group": "Ungrouped variables", "definition": "irrpolydeg2mod5[random(0..9)]", "templateType": "anything", "description": "", "name": "p"}, "irrpolydeg2mod5": {"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]]", "templateType": "anything", "description": "", "name": "irrpolydeg2mod5"}, "x_header": {"group": "Ungrouped variables", "definition": "'$x$'", "templateType": "anything", "description": "", "name": "x_header"}, "m": {"group": "Ungrouped variables", "definition": "irrpolydeg3mod5[random(0..13)]", "templateType": "anything", "description": "", "name": "m"}, "h": {"group": "Ungrouped variables", "definition": "multpolymodn(vector([d,1]),vector(p),5)", "templateType": "anything", "description": "", "name": "h"}, "poly2": {"group": "Ungrouped variables", "definition": "displaypoly(c)", "templateType": "anything", "description": "", "name": "poly2"}, "d1": {"group": "Ungrouped variables", "definition": "mod(a1*b1,n)", "templateType": "anything", "description": "", "name": "d1"}, "c1": {"group": "Ungrouped variables", "definition": "mod(a1+b1,n)", "templateType": "anything", "description": "", "name": "c1"}}, "name": "Luis's copy of Factorise polynomials over Z_5", "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": [], "type": "question", "preamble": {"css": "", "js": "function split(tree,op) {\n  var factors = [];\n  var queue = [tree];\n  var rule = Numbas.jme.compile('?;a'+op+'m_all(??);b');\n  while(queue.length) {\n    var t = queue.pop();\n    var res = Numbas.jme.display.matchTree(rule,t,true);\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 = Numbas.jme.compile('m_pm(m_any(m_number;number,??;c*m_any(x,x^m_number;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 = Numbas.jme.display.matchTree(rule_term,t,true);\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}"}, "variablesTest": {"maxRuns": 100, "condition": ""}, "metadata": {"description": "<p>Factorise 4 polynomials over $\\mathbb{Z}_5$.</p>", "notes": "\n                \t\t                \t\t<p><strong>1/08/2013:</strong></p>\n                \t\t                \t\t                <p><strong><br /></strong>Using lists of irreducible polys and multiplying them using multpolymodn</p>\n                \t\t                \n                \t\t", "licence": "Creative Commons Attribution 4.0 International"}, "showQuestionGroupNames": false, "parts": [{"type": "gapfill", "prompt": "<p>&nbsp;$\\simplify[all,!collectnumbers]{{d1}+{c1}X+X^2} = $&nbsp;[[0]]</p>", "scripts": {}, "gaps": [{"variableReplacements": [], "checkvariablenames": true, "vsetrangepoints": 5, "expectedvariablenames": ["x"], "vsetrange": [0, 1], "marks": 1, "checkingaccuracy": 0.001, "type": "jme", "showpreview": true, "variableReplacementStrategy": "originalfirst", "scripts": {"mark": {"order": "after", "script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);"}}, "answersimplification": "all,!collectNumbers", "answer": "({a1}+X)({b1}+X)", "showCorrectAnswer": true, "checkingtype": "absdiff"}], "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "marks": 0}, {"type": "gapfill", "prompt": "<p>{poly2} $=$&nbsp;[[0]]</p>", "scripts": {}, "gaps": [{"variableReplacements": [], "checkvariablenames": false, "vsetrangepoints": 5, "expectedvariablenames": [], "vsetrange": [0, 1], "marks": 1, "checkingaccuracy": 0.001, "type": "jme", "showpreview": true, "variableReplacementStrategy": "originalfirst", "scripts": {"mark": {"order": "after", "script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);"}}, "answersimplification": "all,!collectNumbers", "answer": "({a}+X)({b[0]}+{b[1]}*X+X^2)", "showCorrectAnswer": true, "checkingtype": "absdiff"}], "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "marks": 0}, {"type": "gapfill", "prompt": "<p>{poly3} $=$&nbsp;[[0]]</p>", "scripts": {}, "gaps": [{"variableReplacements": [], "checkvariablenames": false, "vsetrangepoints": 5, "expectedvariablenames": [], "vsetrange": [0, 1], "marks": 1, "checkingaccuracy": 0.001, "type": "jme", "showpreview": true, "variableReplacementStrategy": "originalfirst", "scripts": {"mark": {"order": "after", "script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);"}}, "answersimplification": "all,!collectNumbers", "answer": "({d}+X)({p[0]}+{p[1]}*X+X^2)", "showCorrectAnswer": true, "checkingtype": "absdiff"}], "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "marks": 0}, {"type": "gapfill", "prompt": "<p>{poly4} $=$&nbsp;[[0]]</p>", "scripts": {}, "gaps": [{"variableReplacements": [], "checkvariablenames": false, "vsetrangepoints": 5, "expectedvariablenames": [], "vsetrange": [0, 1], "marks": 1, "checkingaccuracy": 0.001, "type": "jme", "showpreview": true, "variableReplacementStrategy": "originalfirst", "scripts": {"mark": {"order": "after", "script": "question.mark_polynomial_reduced(this,question.unwrappedVariables.n);"}}, "answersimplification": "all,!collectNumbers", "answer": "({q}+X)({m[0]}+{m[1]}*X+{m[2]}*X^2+X^3)", "showCorrectAnswer": true, "checkingtype": "absdiff"}], "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "marks": 0}], "rulesets": {}, "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": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}, {"name": "Luis Hernandez", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2870/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}, {"name": "Luis Hernandez", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2870/"}]}