// Numbas version: exam_results_page_options {"variable_groups": [], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Add polynomials in Z_n", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "tags": ["bad implementation", "checked2015"], "metadata": {"description": "

Three parts, where the student has to collect together polynomials in $\\mathbb{Z}_3$, $\\mathbb{Z}_5$ and $\\mathbb{Z}_7$, respectively.

The answer to part a has no $X$ term, because they cancel out.

", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "

Compute the following sums of polynomials.

", "advice": "

a)

Adding the polynomials we obtain $3X-\\var{a1+a2+a3}$ . But $3 \\equiv 0 \\pmod 3$ and $ -\\var{a1+a2+a3} \\equiv \\var{ans1} \\pmod 3$.

Hence the sum is $\\var{ans1}$.

b)

Summing up, we obtain:

\\begin{align}
(\\simplify{X ^ 6 + {b4} * X ^ 4 + {b2} * X ^ 2 + {b0}})&+\\simplify{ {g}*(X ^ 6 + {c5} * X ^ 5 + {c4} * X ^ 4 + {c3} * X ^ 3 + {c2} * X ^ 2 + {c1} * X + {c0})} \\\\
&= \\simplify{{1 + g} * X ^ 6 + {g * c5} * X ^ 5 + {b4 + g * c4} * X ^ 4 + {g * c3} * X ^ 3 + {b2 + g * c2} * X ^ 2 + {g * c1} * X + {b0 + g * c0}} \\\\
&\\equiv \\simplify{{d6} * X ^ 6 + {d5} * X ^ 5 + {d4} * X ^ 4 + {d3} * X ^ 3 + {d2} * X ^ 2 + {d1} * X + {d0}} \\pmod 5
\\end{align}

c)

Once again, on summing up we obtain:

\\begin{align}
\\simplify{X ^ 6 + {f5} * X ^ 5 + {f4} * X ^ 4 + {f3} * X ^ 3 + {f2} * X ^ 2 + {f1} * X + {f0} } &+ \\simplify{ {h}*(X ^ 6 + {g5} * X ^ 5 + {g4} * X ^ 4 + {g3} * X ^ 3 + {g2} * X ^ 2 + {g1} * X + {g0})} \\\\
&= \\simplify{ {1 + h} * X ^ 6 + {f5 + h * g5} * X ^ 5 + {f4 + h * g4} * X ^ 4 + {f3 + h * g3} * X ^ 3 + {f2 + h * g2} * X ^ 2 + {f1 + h * g1} * X + {f0 + h * g0}} \\\\
&\\equiv \\simplify{{k6} * X ^ 6 + {k5} * X ^ 5 + {k4} * X ^ 4 + {k3} * X ^ 3 + {k2} * X ^ 2 + {k1} * X + {k0}} \\pmod 7
\\end{align}

", "rulesets": {}, "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"d1": {"name": "d1", "group": "Part b", "definition": "mod(g*c1,5)", "description": "", "templateType": "anything", "can_override": false}, "c2": {"name": "c2", "group": "Part b", "definition": "random(0..4)", "description": "", "templateType": "anything", "can_override": false}, "b0": {"name": "b0", "group": "Part b", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "k1": {"name": "k1", "group": "Part c", "definition": "mod(f1+h*g1,7)", "description": "", "templateType": "anything", "can_override": false}, "c5": {"name": "c5", "group": "Part b", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "f3": {"name": "f3", "group": "Part c", "definition": "random(1..6)", "description": "", "templateType": "anything", "can_override": false}, "k5": {"name": "k5", "group": "Part c", "definition": "mod(f5+h*g5,7)", "description": "", "templateType": "anything", "can_override": false}, "ans1": {"name": "ans1", "group": "Part a", "definition": "mod(-a1-a2-a3,3)", "description": "", "templateType": "anything", "can_override": false}, "c0": {"name": "c0", "group": "Part b", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "h": {"name": "h", "group": "Part c", "definition": "random(2..6)", "description": "", "templateType": "anything", "can_override": false}, "d4": {"name": "d4", "group": "Part b", "definition": "mod(b4+g*c4,5)", "description": "", "templateType": "anything", "can_override": false}, "k2": {"name": "k2", "group": "Part c", "definition": "mod(f2+h*g2,7)", "description": "", "templateType": "anything", "can_override": false}, "d2": {"name": "d2", "group": "Part b", "definition": "mod(b2+g*c2,5)", "description": "", "templateType": "anything", "can_override": false}, "k3": {"name": "k3", "group": "Part c", "definition": "mod(f3+h*g3,7)", "description": "", "templateType": "anything", "can_override": false}, "g1": {"name": "g1", "group": "Part c", "definition": "random(0..6)", "description": "", "templateType": "anything", "can_override": false}, "f0": {"name": "f0", "group": "Part c", "definition": "random(1..6)", "description": "", "templateType": "anything", "can_override": false}, "g0": {"name": "g0", "group": "Part c", "definition": "random(1..6)", "description": "", "templateType": "anything", "can_override": false}, "g4": {"name": "g4", "group": "Part c", "definition": "random(1..6)", "description": "", "templateType": "anything", "can_override": false}, "d0": {"name": "d0", "group": "Part b", "definition": "mod(b0+g*c0,5)", "description": "", "templateType": "anything", "can_override": false}, "f1": {"name": "f1", "group": "Part c", "definition": "random(1..6)", "description": "", "templateType": "anything", "can_override": false}, "f5": {"name": "f5", "group": "Part c", "definition": "random(0..6)", "description": "", "templateType": "anything", "can_override": false}, "b4": {"name": "b4", "group": "Part b", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "d5": {"name": "d5", "group": "Part b", "definition": "mod(g*c5,5)", "description": "", "templateType": "anything", "can_override": false}, "g": {"name": "g", "group": "Part c", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "g2": {"name": "g2", "group": "Part c", "definition": "random(1..6)", "description": "", "templateType": "anything", "can_override": false}, "f2": {"name": "f2", "group": "Part c", "definition": "random(0..6)", "description": "", "templateType": "anything", "can_override": false}, "f4": {"name": "f4", "group": "Part c", "definition": "random(1..6)", "description": "", "templateType": "anything", "can_override": false}, "k6": {"name": "k6", "group": "Part c", "definition": "mod(1+h,7)", "description": "", "templateType": "anything", "can_override": false}, "g5": {"name": "g5", "group": "Part c", "definition": "random(0..6)", "description": "", "templateType": "anything", "can_override": false}, "d6": {"name": "d6", "group": "Part b", "definition": "mod(1+g,5)", "description": "", "templateType": "anything", "can_override": false}, "c1": {"name": "c1", "group": "Part b", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "c3": {"name": "c3", "group": "Part b", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "d3": {"name": "d3", "group": "Part b", "definition": "mod(g*c3,5)", "description": "", "templateType": "anything", "can_override": false}, "b2": {"name": "b2", "group": "Part b", "definition": "random(1..4)", "description": "", "templateType": "anything", "can_override": false}, "g3": {"name": "g3", "group": "Part c", "definition": "random(0..6)", "description": "", "templateType": "anything", "can_override": false}, "k4": {"name": "k4", "group": "Part c", "definition": "mod(f4+h*g4,7)", "description": "", "templateType": "anything", "can_override": false}, "k0": {"name": "k0", "group": "Part c", "definition": "mod(f0+h*g0,7)", "description": "", "templateType": "anything", "can_override": false}, "c4": {"name": "c4", "group": "Part b", "definition": "random(0..4)", "description": "", "templateType": "anything", "can_override": false}, "a1,a2,a3": {"name": "a1,a2,a3", "group": "Part a", "definition": "repeat(random(1..2),3)", "description": "

Constant terms in the expression given in part a

", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [{"name": "Part a", "variables": ["ans1", "a1,a2,a3"]}, {"name": "Part b", "variables": ["b0", "b4", "b2", "c0", "c1", "c2", "c3", "c4", "c5", "d0", "d1", "d2", "d3", "d4", "d5", "d6"]}, {"name": "Part c", "variables": ["f0", "f1", "f2", "f3", "f4", "f5", "g", "g0", "g1", "g2", "g3", "g4", "g5", "h", "k0", "k1", "k2", "k3", "k4", "k5", "k6"]}], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Find the following sum of polynomials over $\\mathbb{Z}_3$.

All coefficients of non-zero terms in your answer should be either $1$ or $2$.

$(X - \\var{ a1}) + (X - \\var{ a2}) + (X - \\var{ a3}) = $ [[0]]

", "gaps": [{"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [{"variables": [{"name": "ans1", "value": "0"}, {"name": "a1", "value": "2"}, {"name": "a2", "value": "2"}, {"name": "a3", "value": "2"}, {"name": "b0", "value": "1"}, {"name": "b4", "value": "1"}, {"name": "b2", "value": "2"}, {"name": "c0", "value": "2"}, {"name": "c1", "value": "1"}, {"name": "c2", "value": "3"}, {"name": "c3", "value": "3"}, {"name": "c4", "value": "1"}, {"name": "c5", "value": "1"}, {"name": "d0", "value": "3"}, {"name": "d1", "value": "1"}, {"name": "d2", "value": "0"}, {"name": "d3", "value": "3"}, {"name": "d4", "value": "2"}, {"name": "d5", "value": "1"}, {"name": "d6", "value": "2"}, {"name": "f0", "value": "6"}, {"name": "f1", "value": "6"}, {"name": "f2", "value": "1"}, {"name": "f3", "value": "5"}, {"name": "f4", "value": "6"}, {"name": "f5", "value": "5"}, {"name": "g", "value": "1"}, {"name": "g0", "value": "3"}, {"name": "g1", "value": "1"}, {"name": "g2", "value": "1"}, {"name": "g3", "value": "1"}, {"name": "g4", "value": "6"}, {"name": "g5", "value": "0"}, {"name": "h", "value": "5"}, {"name": "k0", "value": "0"}, {"name": "k1", "value": "4"}, {"name": "k2", "value": "6"}, {"name": "k3", "value": "3"}, {"name": "k4", "value": "1"}, {"name": "k5", "value": "5"}, {"name": "k6", "value": "6"}], "name": "Correct answer", "answer": {"valid": true, "value": "0"}, "notes": [{"name": "mark", "expected": {"value": "nothing", "messages": ["Your answer is numerically correct.\n\nYou were awarded 1 mark."], "warnings": [], "error": "", "valid": true, "credit": 1}}]}, {"variables": [{"name": "ans1", "value": "0"}, {"name": "a1", "value": "2"}, {"name": "a2", "value": "2"}, {"name": "a3", "value": "2"}, {"name": "b0", "value": "1"}, {"name": "b4", "value": "1"}, {"name": "b2", "value": "2"}, {"name": "c0", "value": "2"}, {"name": "c1", "value": "1"}, {"name": "c2", "value": "3"}, {"name": "c3", "value": "3"}, {"name": "c4", "value": "1"}, {"name": "c5", "value": "1"}, {"name": "d0", "value": "3"}, {"name": "d1", "value": "1"}, {"name": "d2", "value": "0"}, {"name": "d3", "value": "3"}, {"name": "d4", "value": "2"}, {"name": "d5", "value": "1"}, {"name": "d6", "value": "2"}, {"name": "f0", "value": "6"}, {"name": "f1", "value": "6"}, {"name": "f2", "value": "1"}, {"name": "f3", "value": "5"}, {"name": "f4", "value": "6"}, {"name": "f5", "value": "5"}, {"name": "g", "value": "1"}, {"name": "g0", "value": "3"}, {"name": "g1", "value": "1"}, {"name": "g2", "value": "1"}, {"name": "g3", "value": "1"}, {"name": "g4", "value": "6"}, {"name": "g5", "value": "0"}, {"name": "h", "value": "5"}, {"name": "k0", "value": "0"}, {"name": "k1", "value": "4"}, {"name": "k2", "value": "6"}, {"name": "k3", "value": "3"}, {"name": "k4", "value": "1"}, {"name": "k5", "value": "5"}, {"name": "k6", "value": "6"}], "name": "Incorrect answer", "answer": {"valid": true, "value": "1"}, "notes": [{"name": "mark", "expected": {"value": "nothing", "messages": ["Your answer is incorrect."], "warnings": [], "error": "", "valid": true, "credit": 0}}]}], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "{ans1}", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": []}], "sortAnswers": false}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Find the following sum of polynomials over $\\mathbb{Z}_5$.

All coefficients of non-zero terms in your answer should be $1$, $2$, $3$ or $4$.

$(\\simplify{X ^ 6 + {b4} * X ^ 4 + {b2} * X ^ 2 + {b0}}) +\\simplify{ {g}(X ^ 6 + {c5} * X ^ 5 + {c4} * X ^ 4 + {c3} * X ^ 3 + {c2} * X ^ 2 + {c1} * X + {c0}) } = $ [[0]]

Find the following sum of polynomials over $\\mathbb{Z}_7$.

All coefficients of non-zero terms in your answer should be $1$, $2$, $3$, $4$, $5$ or $6$.

$(\\simplify{X ^ 6 + {f5}*X^5+{f4} * X ^ 4 +{f3} * X ^ 3 + {f2} * X ^ 2 +{f1}*X+ {f0}}) +\\simplify{ {h}(X ^ 6 + {g5} * X ^ 5 + {g4} * X ^ 4 + {g3} * X ^ 3 + {g2} * X ^ 2 + {g1} * X + {g0}) } = $ [[0]]

", "gaps": [{"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "(({k6} * (X ^ 6)) + ({k5} * (X ^ 5)) + ({k4} * (X ^ 4)) + ({k3} * (X ^ 3)) + ({k2} * (X ^ 2)) + ({k1} * X) + {k0})", "answerSimplification": "all", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "caseSensitive": false, "valuegenerators": [{"name": "x", "value": ""}]}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always"}, {"name": "Expand products of polynomials over Z_n", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"b3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-4..4 except 0)", "description": "", "name": "b3"}, "c10": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(-a1*a2*a3,3)", "description": "", "name": "c10"}, "c2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-6..6 except 0)", "description": "", "name": "c2"}, "c31": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c1*c2+c1*c3+c2*c3,7)", "description": "", "name": "c31"}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-4..4)", "description": "", "name": "b1"}, "c21": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(b1*b2+b2*b3+b1*b3,5)", "description": "", "name": "c21"}, "c12": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(-a1-a2-a3,3)", "description": "", "name": "c12"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-1..2)", "description": "", "name": "a1"}, "b2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-4..4 except 0)", "description": "", "name": "b2"}, "c22": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(-b1-b2-b3,5)", "description": "", "name": "c22"}, "c20": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(-b1*b2*b3,5)", "description": "", "name": "c20"}, "c11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a1*a2+a1*a3+a2*a3,3)", "description": "", "name": "c11"}, "c1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-6..6)", "description": "", "name": "c1"}, "a3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-2..2 except 0)", "description": "", "name": "a3"}, "c3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-6..6 except 0)", "description": "", "name": "c3"}, "c30": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(-c1*c2*c3,7)", "description": "", "name": "c30"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-2..2 except 0)", "description": "", "name": "a2"}, "c32": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(-c1-c2-c3,7)", "description": "", "name": "c32"}}, "ungrouped_variables": ["c22", "c20", "c21", "a1", "a3", "a2", "c1", "b1", "b2", "b3", "c3", "c12", "c11", "c10", "c31", "c30", "c2", "c32"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"answer": "((X ^ 3) + ({c12} * (X ^ 2)) + ({c11} * X) + {c10})", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "showCorrectAnswer": true, "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Find the following product of polynomials over $\\mathbb{Z}_3$.

All coefficients of non zero terms in your answer should be $1$ or $2$.

$\\simplify{(X - { a1})(X - { a2})(X - { a3})} = $ [[0]]

", "showCorrectAnswer": true, "marks": 0}, {"scripts": {}, "gaps": [{"answer": "((X ^ 3) + ({c22} * (X ^ 2)) + ({c21} * X) + {c20})", "showCorrectAnswer": true, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "answersimplification": "all", "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Find the following product of polynomials over $\\mathbb{Z}_5$.

All coefficients of non zero terms in your answer should be $1$, $2$, $3$ or $4$.

$\\simplify{(X -{ b1})(X -{ b2})(X - { b3}) } =$ [[0]]

", "showCorrectAnswer": true, "marks": 0}, {"scripts": {}, "gaps": [{"answer": "((X ^ 3) + ({c32} * (X ^ 2)) + ({c31} * X) + {c30})", "showCorrectAnswer": true, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "answersimplification": "all", "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Find the following product of polynomials over $\\mathbb{Z}_7$.

All coefficients of non zero terms in your answer should be $1$, $2$, $3$, $4$, $5$ or $6$.

$\\simplify{(X - { c1})(X - { c2})(X - { c3}) } =$ [[0]]

", "showCorrectAnswer": true, "marks": 0}], "statement": "

Compute the following products of polynomials.

", "tags": ["checked2015", "MAS2213"], "rulesets": {}, "preamble": {"css": "ul {\n padding-left: 2em;\n}", "js": ""}, "type": "question", "metadata": {"notes": "

29/07/2013:

Created version directly from the iassess question.

", "licence": "Creative Commons Attribution 4.0 International", "description": "

Expanding products of 3 linear polynomials over $\\mathbb{Z}_3,\\;\\mathbb{Z}_5,\\;\\mathbb{Z}_7$

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

a)

Expanding out the polynomials gives:

\\[ \\simplify{(X + { -a1}) * (X + { -a2}) * (X + { -a3}) = X ^ 3 + {-a1-a2-a3} * X ^ 2 + {a1*a2+a1*a3+a2*a3} * X + {-a1*a2*a3}} \\]

But we have to reduce the coefficients $\\bmod 3$ and we get:

\\begin{align}
\\text{Coefficient of } X^2 \\text{:} && \\var{-a1-a2-a3} &\\equiv \\var{c12} \\pmod 3 \\\\
\\text{Coefficient of } X \\text{:} && \\var{a2*a1+a2*a3+a1*a3} &\\equiv \\var{c11} \\pmod 3 \\\\
\\text{Constant term:} && \\var{-a1*a2*a3} &\\equiv \\var{c10} \\pmod 3 \\\\
\\end{align}

Hence the product is $\\simplify{((X ^ 3) + ({c12} * (X ^ 2)) + ({c11} * X) + {c10})}$.

b)

Expanding out the polynomials gives:

\\[ \\simplify{(X + { -b1}) * (X + { -b2}) * (X + { -b3}) = X ^ 3 + {-b1-b2-b3} * X ^ 2 + {b1*b2+b1*b3+b2*b3} * X + {-b1*b2*b3}} \\]

But we have to reduce the coefficients $\\bmod 5$ and we get:

\\begin{align}
\\text{Coefficient of } X^2 \\text{:} && \\var{-b1-b2-b3} &\\equiv \\var{c22} \\pmod 5 \\\\
\\text{Coefficient of } X \\text{:} && \\var{b2*b1+b2*b3+b1*b3} &\\equiv \\var{c21} \\pmod 5 \\\\
\\text{Constant term:} && \\var{-b1*b2*b3} &\\equiv \\var{c20} \\pmod 5 \\\\
\\end{align}

Hence the product is $\\simplify{((X ^ 3) + ({c22} * (X ^ 2)) + ({c21} * X) + {c20})}$.

c)

Expanding out the polynomials gives:

\\[ \\simplify{(X + { -c1}) * (X + { -c2}) * (X + { -c3}) = X ^ 3 + {-c1-c2-c3} * X ^ 2 + {c1*c2+c1*c3+c2*c3} * X + {-c1*c2*c3}} \\]

But we have to reduce the coefficients $\\operatorname{mod} 7$ and we get:

\\begin{align}
\\text{Coefficient of } X^2 \\text{:} && \\var{-c1-c2-c3} &\\equiv \\var{c32} \\pmod 7 \\\\
\\text{Coefficient of } X \\text{:} && \\var{c2*c1+c2*c3+c1*c3} &\\equiv \\var{c31} \\pmod 7 \\\\
\\text{Constant term:} && \\var{-c1*c2*c3} &\\equiv \\var{c30} \\pmod 7 \\\\
\\end{align}

Hence the product is $\\simplify{((X ^ 3) + ({c32} * (X ^ 2)) + ({c31} * X) + {c30})}$.

"}, {"name": "Factorise rational polynomials", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-9..9)", "description": "", "name": "r"}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-9..9 except [0,1,-1])", "description": "", "name": "b"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-9..9 except 0)", "description": "", "name": "c"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-9..9)", "description": "", "name": "d"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..9)", "description": "", "name": "a1"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-9..9 except 0)", "description": "", "name": "a"}}, "ungrouped_variables": ["a", "c", "b", "d", "a1", "r"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"answer": "X+{a}", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "showCorrectAnswer": true, "marks": 1, "vsetrangepoints": 5}, {"answer": "{r}", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "showCorrectAnswer": true, "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

$\\simplify{f(X) = X ^ 5 + {1 + a} * X ^ 4 + {1 + a} * X ^ 3 + {1 + a} * X ^ 2 + {1 + a} * X + {a + r}}$

$\\simplify{g(X) = X ^ 4 + X ^ 3 + X ^ 2 + X + 1}$

$q(X)=$ [[0]]

$r(X)=$ [[1]]

", "showCorrectAnswer": true, "marks": 0}, {"scripts": {}, "gaps": [{"answer": "X-{a}", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "showCorrectAnswer": true, "marks": 1, "vsetrangepoints": 5}, {"answer": "{-r}", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "showCorrectAnswer": true, "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

$\\simplify{f(X) = X ^ 5 + { -1 -a} * X ^ 4 + {1 + a} * X ^ 3 + { -1 -a} * X ^ 2 + {1 + a} * X + { -a -r}}$

$\\simplify{g(X) = X ^ 4 - X ^ 3 + X ^ 2 - X + 1}$

$q(X)=$ [[0]]

$r(X)=$ [[1]]

", "showCorrectAnswer": true, "marks": 0}, {"scripts": {}, "gaps": [{"answer": "X^3/{a1}+{d}/{a1}*X-{b}/{a1^2}", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "showCorrectAnswer": true, "expectedvariablenames": [], "notallowed": {"message": "

Enter numbers as fractions or integers and not as decimals.

", "showStrings": false, "partialCredit": 0, "strings": ["."]}, "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "checkvariablenames": false, "type": "jme", "answersimplification": "std", "marks": 1, "vsetrangepoints": 5}, {"answer": "-{b*d}/{a1}*X+{b^2+a1^2*c}/{a1^2}", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "showCorrectAnswer": true, "expectedvariablenames": [], "notallowed": {"message": "

Enter numbers as fractions or integers and not as decimals.

$\\simplify{f(X) = X ^ 6 + {d} * X ^ 4 + {c}}$

$\\simplify{g(X) = {a1} * X ^ 3 + {b}}$

Remember to enter all numbers as rationals i.e. as fractions or integers and not as decimals.

$q(X)=$ [[0]]

$r(X)=$ [[1]]

", "showCorrectAnswer": true, "marks": 0}], "statement": "

Let $\\mathbb{Q}$ be the rational numbers. This exercise considers polynomials over $\\mathbb{Q}$.

In each of the following examples, find polynomials $q(X)$ and $r(X)$ over $\\mathbb{Q}$ such that $f(X)=q(X)g(X)+r(X)$ and $\\operatorname{deg}r(X) \\lt \\operatorname{deg}g(X)$.

Enter all numbers as rationals, i.e. as fractions or integers and not as decimals.

", "tags": ["checked2015", "MAS2213"], "rulesets": {"std": ["all", "!noleadingminus", "fractionnumbers"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "

Given polynomial $f(X)$, $g(X)$ over $\\mathbb{Q}$, find polynomials $q(X)$ and $r(X)$ over $\\mathbb{Q}$ such that $f(X)=q(X)g(X)+r(X)$ and $\\operatorname{deg}r(X) \\lt \\operatorname{deg}g(X)$.

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

a)

We have:

\\[ \\simplify{f(X) = X ^ 5 + {1 + a} * X ^ 4 + {1 + a} * X ^ 3 + {1 + a} * X ^ 2 + {1 + a} * X + {a + r} = (X + {a}) * (X ^ 4 + X ^ 3 + X ^ 2 + X + 1) + {r}} \\]

Hence $\\simplify{g(X)=X+{a}}$, $r=\\var{r}$.

b)

Similarly:

\\[ \\simplify{f(X) = X ^ 5 + { -1 -a} * X ^ 4 + {1 + a} * X ^ 3 + { -1 -a} * X ^ 2 + {1 + a} * X + { -a -r} = (X + { -a}) * (X ^ 4 -(X ^ 3) + X ^ 2 -X + 1) + { -r}} \\]

Hence $\\simplify{g(X)=X-{a}}$, $r=\\var{-r}$.

c)

\\begin{align}
f(X) &= \\simplify{X ^ 6 + {d} * X ^ 4 + {c}} \\\\
&= \\simplify[std]{({a1} * X ^ 3 + {b}) * (X ^ 3 / {a1} + ({d} / {a1}) * X -({b} / {a1 ^ 2})) + {b^2 + c * a1 ^ 2} / {a1 ^ 2} - ({b * d} / {a1}) * X}
\\end{align}

Hence

\\begin{align} \\displaystyle g(X) &= \\simplify[std]{X ^ 3 / {a1} + ({d} / {a1}) * X -({b} / {a1 ^ 2})}, & r(X) &= \\simplify[std]{{b^2 + c * a1 ^ 2} / {a1 ^ 2} - ({b * d} / {a1}) * X} \\end{align}

"}, {"name": "Find numbers modulo a base", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"r1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(20..99)", "description": "", "name": "r1"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "m*n+r", "description": "", "name": "a"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5,6,7,8,9,11,12,13)", "description": "", "name": "m"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(6,7,8,9,11,12,13,14,15,16,17,18,19)", "description": "", "name": "n"}, "n1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1001..1999#2)", "description": "", "name": "n1"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "m1*n1+r1", "description": "", "name": "a1"}, "m1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3,4,5,6)", "description": "", "name": "m1"}, "n2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(301..999#2)", "description": "", "name": "n2"}, "r": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..5)", "description": "", "name": "r"}, "m2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2,3,4)", "description": "", "name": "m2"}, "r2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(10..19)", "description": "", "name": "r2"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "m2*n2+r2", "description": "", "name": "a2"}}, "ungrouped_variables": ["a", "r1", "r2", "m", "n", "a1", "r", "m1", "m2", "n1", "n2", "a2"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"prompt": "

$\\var{a} \\bmod \\var{n}=$ [[0]]
Input your answer as an integer $a$, $0 \\le a \\le \\var{n-1}$.
$\\var{a1} \\bmod \\var{n1}=$ [[1]]
Input your answer as an integer $b$, $0 \\le b \\le \\var{n1-1}$.
$\\var{a2} \\bmod \\var{n2}=$ [[2]]
Input your answer as an integer $c$, $0 \\le c \\le \\var{n2-1}$.

", "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "{r}", "minValue": "{r}", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "{r1}", "minValue": "{r1}", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "{r2}", "minValue": "{r2}", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "showCorrectAnswer": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "statement": "

Find the following numbers modulo the given number $n$.

", "tags": ["Arithmetic", "arithmetic", "checked2015", "MAS2213", "mod", "Modular arithmetic", "modular arithmetic", "modulo", "remainder algorithm for integers", "tested1"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "

11/07/2012:

Added tags.

Calculation checked.

24/07/2012:

Added description.

3/08/2012:

In the Advice section, moved \\Rightarrow to the beginning of the line instead of the end of the previous line.

Question appears to be working correctly.

20/12/2012:

Changed marks from 0.5 for each part to 1 for each part.

Could replace the variables using the mod function which is available, also use except for the random variable values. But not for now, calculations checked.

Added tag tested1.

", "licence": "Creative Commons Attribution 4.0 International", "description": "

Modular arithmetic. Find the following numbers modulo the given number $n$. Three examples to do.

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

a)

We seek a number

\\[r=\\var{a} \\bmod \\var{n} \\implies \\var{a} = m\\var{n}+r \\]

where $m$ is a positive integer and $0 \\le r \\le \\var{n-1}$.

This is achieved by dividing $\\var{a}$ by $\\var{n}$ and we find that:

\\begin{align}
\\frac{\\var{a}}{\\var{n}} &= \\var{m}+\\frac{\\var{r}}{\\var{n}} \\\\
\\implies \\var{a} &= \\var{m}\\times \\var{n}+\\var{r}
\\end{align}

on multiplying through by $\\var{n}$.

Hence $r=\\var{r}$ and $\\var{a} \\bmod \\var{n}=\\var{r}$.

You can use your calculator to find this as follows:

Divide $\\var{a}$ by $\\var{n}$ to get

\\[ \\frac{\\var{a}}{\\var{n}}=\\var{a/n}=\\var{m}+\\var{a/n-m} \\]

Then multiplying $\\var{a/n-m}$ by $\\var{n}$ gives the remainder, i.e.

\\[ \\var{a/n-m}\\times \\var{n} = \\var{r} \\]

This must be an integer if no error is introduced, but the calculator result will be either an integer or very close to an integer – so you need to round to the integer in that case.

b)

As in a),

\\[\\frac{\\var{a1}}{\\var{n1}}=\\var{m1}+\\frac{\\var{r1}}{\\var{n1}}\\]

So $\\var{a1} \\bmod \\var{n1} = \\var{r1}$

c)

\\[\\frac{\\var{a2}}{\\var{n2}}=\\var{m2}+\\frac{\\var{r2}}{\\var{n2}}\\]

So $\\var{a2} \\bmod \\var{n2} = \\var{r2}$

"}, {"name": "Solve linear equations in the rationals and Z_n", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"b3": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2..n-2)", "description": "", "name": "b3"}, "b4": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(3..n-2 except b3)", "description": "", "name": "b4"}, "b1": {"group": "Ungrouped variables", "templateType": "anything", "definition": "mod(a1,n)", "description": "", "name": "b1"}, "a1": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(-16..16 except 0)", "description": "", "name": "a1"}, "b2": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(2..5)", "description": "", "name": "b2"}, "a5": {"group": "Ungrouped variables", "templateType": "anything", "definition": "mod(-s*(b4+2)*findinversemodp(b4,n),n)", "description": "", "name": "a5"}, "invb3": {"group": "Ungrouped variables", "templateType": "anything", "definition": "findinversemodp(b3,n)", "description": "", "name": "invb3"}, "invb4": {"group": "Ungrouped variables", "templateType": "anything", "definition": "findinversemodp(b4,n)", "description": "", "name": "invb4"}, "n": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(11,13,17,19)", "description": "", "name": "n"}, "a3": {"group": "Ungrouped variables", "templateType": "anything", "definition": "mod((1+b3)*invb3,n)", "description": "", "name": "a3"}, "s": {"group": "Ungrouped variables", "templateType": "anything", "definition": "random(-1,1)", "description": "", "name": "s"}, "a2": {"group": "Ungrouped variables", "templateType": "anything", "definition": "if(b2=2,random(2..6),if(b2=3,random(2..4),if(b2=4,random(2..3),2)))", "description": "", "name": "a2"}}, "ungrouped_variables": ["a1", "a3", "n", "b4", "s", "a2", "a5", "b1", "b2", "b3", "invb4", "invb3"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"findinversemodp": {"type": "number", "language": "jme", "definition": "//n, p coprime. Finds s such that sn=1 mod p i.e. inverse of n in Z_p\n mod(extendedgcd1(n,p),p)", "parameters": [["n", "number"], ["p", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "//finds coefficients s, t such that sa+tb=gcd(a,b)\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "describegcdold": {"type": "string", "language": "jme", "definition": "\n \n \n if(a First of all, the biggest number needs to go first: $\\\\operatorname{gcd}(\\\\var{a},\\\\var{b}) = \\\\operatorname{gcd}(\\\\var{b},\\\\var{a}), $ '+describeGCD(b,a)\n \n ,\n \n if(b|a,\n \n ' Finally, $\\\\var{b}$ divides into $\\\\var{a}$ exactly $\\\\var{a/b}$ times: $\\\\var{a} = \\\\var{b} \\\\times \\\\var{a/b}.$ '\n \n ,\n \n ' Divide $\\\\var{a}$ by $\\\\var{b}$ with remainder $\\\\var{mod(a,b)}$: $\\\\var{a} = \\\\var{b} \\\\times \\\\var{floor(a/b)} + \\\\var{mod(a,b)},$ '+describeGCD(b,mod(a,b))\n \n )\n \n )\n \n ", "parameters": [["a", "number"], ["b", "number"]]}, "describegcd": {"type": "html", "language": "javascript", "definition": "var table = $('');\nfunction describegcd(a,b) {\nif(a');\nreturn describegcd(b,a);\n}\n\nif(a%b==0) {\ntable.append('');\n}\nelse {\ntable.append('');\ndescribegcd(b,a%b);\n}\n}\ndescribegcd(a,b);\nreturn table;", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n//finds coefficients s, t such that sa+tb=gcd(a,b)\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", "parameters": [["a", "number"], ["b", "number"]]}}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"showCorrectAnswer": true, "showPrecisionHint": false, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "a2", "minValue": "a2", "correctAnswerFraction": false, "marks": 1}, {"showCorrectAnswer": true, "showPrecisionHint": false, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "a2", "minValue": "a2", "correctAnswerFraction": false, "marks": 1}], "type": "gapfill", "prompt": "

$\\simplify{{b2}*x-{b2*a2}=0}$

Solution in $\\mathbb{Q}=$ [[0]]

Solution in $\\mathbb{Z}_{\\var{n}}=$ [[1]]

", "showCorrectAnswer": true, "marks": 0}, {"marks": 0, "scripts": {}, "gaps": [{"answer": "{1+b3}/{b3}", "showCorrectAnswer": true, "vsetrange": [0, 1], "scripts": {}, "checkvariablenames": false, "expectedvariablenames": [], "notallowed": {"message": "

Enter you answer as a rational number and not as a decimal.

", "showStrings": false, "partialCredit": 0, "strings": ["."]}, "showpreview": true, "checkingtype": "absdiff", "checkingaccuracy": 0.001, "type": "jme", "answersimplification": "all, fractionNumbers", "marks": 1, "vsetrangepoints": 5}, {"showCorrectAnswer": true, "showPrecisionHint": false, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "a3", "minValue": "a3", "correctAnswerFraction": false, "marks": 1}], "type": "gapfill", "showCorrectAnswer": true, "steps": [{"type": "information", "showCorrectAnswer": true, "prompt": "

You will have to find $\\var{b3}^{-1}$ in $\\mathbb{Z}_{\\var{n}}$.

If you cannot find this easily, use the Euclidean algorithm to find $s$ and $t$ such that $\\simplify{{b3}s+{n}t = gcd({b3},{n}) = 1}$.

$s \\bmod \\var{n}$ is then an inverse of $\\var{b3}$ in $\\mathbb{Z}_{\\var{n}}$.

", "marks": 0, "scripts": {}}], "prompt": "

$\\simplify{{b3}x-{b3+1}}=0$

Solution in $\\mathbb{Q}=$ [[0]]

Solution in $\\mathbb{Z}_{\\var{n}}=$ [[1]]

Click on Show steps for more information on solving the equation over $\\mathbb{Z}_{\\var{n}}$.

", "stepsPenalty": 0}, {"marks": 0, "scripts": {}, "gaps": [{"answer": "{-s}*({b4+2}/{b4})", "showCorrectAnswer": true, "vsetrange": [0, 1], "scripts": {}, "checkvariablenames": false, "expectedvariablenames": [], "notallowed": {"message": "

Input ypur answer as a rational number and not as a decimal.

", "showStrings": false, "partialCredit": 0, "strings": ["."]}, "showpreview": true, "checkingtype": "absdiff", "checkingaccuracy": 0.001, "type": "jme", "answersimplification": "all,fractionNumbers", "marks": 1, "vsetrangepoints": 5}, {"showCorrectAnswer": true, "showPrecisionHint": false, "scripts": {}, "allowFractions": false, "type": "numberentry", "maxValue": "a5", "minValue": "a5", "correctAnswerFraction": false, "marks": 1}], "type": "gapfill", "showCorrectAnswer": true, "steps": [{"type": "information", "showCorrectAnswer": true, "prompt": "

You will have to find $\\var{b4}^{-1}$ in $\\mathbb{Z}_{\\var{n}}$.

If you cannot find this easily use the Euclidean algorithm to find $s$ and $t$ such that $\\var{b4}s+\\var{n}t=\\operatorname{gcd}(\\var{b4},\\var{n})=1$.

$s \\operatorname{mod} \\var{n}$ is then an inverse of $\\var{b4}$ in $\\mathbb{Z}_{\\var{n}}$.

", "marks": 0, "scripts": {}}], "prompt": "

$\\simplify{{b4}x+{s*(b4+2)}}=0$

Solution in $\\mathbb{Q}=$ [[0]]

Solution in $\\mathbb{Z}_{\\var{n}}=$ [[1]]

", "stepsPenalty": 0}], "statement": "

Solve each of the following equations, first over $\\mathbb{Q}$, the rational numbers and then over $\\mathbb{Z}_{\\var{n}}$.

Solutions to the equations over $\\mathbb{Q}$ must be entered as integers or fractions.

The solutions in $\\mathbb{Z}_{\\var{n}}$ must be in the set $\\{0,1,\\ldots,\\var{n-1}\\}$

", "tags": ["checked2015", "MAS2213"], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "

30/07/2013:

Created from iassess question, except allowed n=13, 17 or 19 and missed out users having to find inverses of all elements in $\\mathbb{Z}_n$ . Instead reminded them how to find inverses in general using the Euclidean Algorithm so reinforcing earlier questions. Advice reminds them of that method.

", "licence": "Creative Commons Attribution 4.0 International", "description": "

Solving simple linear equations in $\\mathbb{Q}$ and $\\mathbb{Z}_n$ for $n= 13, \\;17$ or $19$.

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

a)

The solution in $\\mathbb{Q}$ is $x=\\var{a2}$.

The solution in $\\mathbb{Z}_{\\var{n}}$ is also $x=\\var{a2}$.

b)

The solution in $\\mathbb{Q}$ is $x= \\frac{\\var{b3+1}}{\\var{b3}}$.

The solution in $\\mathbb{Z}_{\\var{n}}$ is given by $x=\\var{b3+1}\\times\\var{b3}^{-1} \\pmod{\\var{n}}$.

We find that $\\var{b3}^{-1} = \\var{invb3}$ in $\\mathbb{Z}_{\\var{n}}$. See below for one method for finding the inverse.

Hence the solution is $x=\\var{b3+1}\\times\\var{invb3} \\equiv \\var{(b3+1)*invb3}=\\var{a3} \\pmod {\\var{ n}}$.

Finding the inverse:

Use the Euclidean Algorithm to find $s$ and $t$ such that $\\simplify{{b3}s+{n}t = gcd({b3},{n})=1}$.

It follows that $s \\bmod n$ is the inverse of $\\var{b3}$ in $\\mathbb{Z}_{\\var{n}}$.

In this case one such application gives:

{describegcd(n,b3)}

Using this we obtain:

\\[ \\simplify[]{{extendedgcd2(n,b3)}*{b3}+{extendedgcd1(n,b3)}*{n}=1} \\]

Hence the inverse of $\\var{b3}$ in $\\mathbb{Z}_{\\var{n}}$ is $\\simplify{{extendedgcd2(n,b3)}} \\equiv \\var{invb3} \\pmod{\\var{n}}$.

c)

The solution in $\\mathbb{Q}$ is $x = \\simplify{{-s}*({b4+2}/{b4})}$.

The solution in $\\mathbb{Z}_{\\var{n}}$ is given by $x=\\var{-s*(b4+2)}\\times\\var{b4}^{-1} \\pmod{\\var{n}}$.

We find that $\\var{b4}^{-1}=\\var{invb4}$ in $\\mathbb{Z}_{\\var{n}}$. See below for one method for finding the inverse.

Hence the solution is $x=\\var{-s*(b4+2)}\\times\\var{invb4}=\\var{-s*(b4+2)*invb4} \\equiv \\var{a5} \\pmod{\\var{n}}$.

Finding the inverse:

Use the Euclidean Algorithm to find $s$ and $t$ such that $\\simplify{{b4}s+{n}t = gcd({b4},{n}) = 1}$.

It follows that $s \\bmod n$ is the inverse of $\\var{b4}$ in $\\mathbb{Z}_{\\var{n}}$.

In this case one such application gives:

{describegcd(n,b4)}

Using this we obtain:

\\[ \\simplify[]{{extendedgcd2(n,b4)}*{b4}+{extendedgcd1(n,b4)}*{n}=1} \\]

Hence the inverse of $\\var{b4}$ in $\\mathbb{Z}_{\\var{n}}$ is $\\simplify{{extendedgcd2(n,b4)}} \\equiv \\var{invb4} \\pmod{\\var{n}}$.

"}, {"name": "Use B\u00e9zout's algorithm to solve $as + bt = \\gcd(a,b)$, ", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [{"variables": ["g", "num_lines", "numbers", "a", "b"], "name": "Setup"}, {"variables": ["d", "diff", "s", "t", "multiple", "show_diff"], "name": "Intermediate"}, {"variables": ["sval", "tval"], "name": "Answers"}], "variables": {"d": {"group": "Intermediate", "templateType": "anything", "definition": "gcd(a,b)", "description": "", "name": "d"}, "b": {"group": "Setup", "templateType": "anything", "definition": "numbers[1]", "description": "", "name": "b"}, "tval": {"group": "Answers", "templateType": "anything", "definition": "t-multiple*a/d", "description": "", "name": "tval"}, "t": {"group": "Intermediate", "templateType": "anything", "definition": "extendedgcd2(max(a,b),min(a,b))", "description": "", "name": "t"}, "multiple": {"group": "Intermediate", "templateType": "anything", "definition": "(sval-s)/diff", "description": "

Multiple of diff to add to s to get a value in the range $(0,...diff-1)$

", "name": "multiple"}, "show_diff": {"group": "Intermediate", "templateType": "anything", "definition": "random(sval+1..diff)", "description": "", "name": "show_diff"}, "diff": {"group": "Intermediate", "templateType": "anything", "definition": "b/d", "description": "", "name": "diff"}, "numbers": {"group": "Setup", "templateType": "anything", "definition": "long_gcd(g*random(2..10),g,num_lines)", "description": "", "name": "numbers"}, "sval": {"group": "Answers", "templateType": "anything", "definition": "mod(s,diff)", "description": "", "name": "sval"}, "s": {"group": "Intermediate", "templateType": "anything", "definition": "extendedgcd1(max(a,b),min(a,b))", "description": "", "name": "s"}, "num_lines": {"group": "Setup", "templateType": "randrange", "definition": "random(3..5#1)", "description": "

Number of lines in the Euclidean algorithm for a and b.

", "name": "num_lines"}, "a": {"group": "Setup", "templateType": "anything", "definition": "numbers[0]", "description": "", "name": "a"}, "g": {"group": "Setup", "templateType": "anything", "definition": "random(1..20)", "description": "

GCD of a and b

", "name": "g"}}, "ungrouped_variables": [], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {"describebezout": {"type": "html", "language": "javascript", "definition": "// describe the steps of B\u00e9zout's algorithm, to solve a*x+b*y = gcd(a,b)\nvar tex = '\\\\begin{align}\\n';\n\nvar as = [];\nvar bs = [];\nvar qs = [];\nvar q,r,old_r;\nwhile(r=a%b) {\n q=(a-r)/b;\n as.push(a);\n bs.push(b);\n qs.push(q);\n a=b;\n b=r;\n old_r=r;\n}\nvar lines = [];\nvar s=0,t=1,tmp;\nwhile(qs.length) {\n q = qs.pop();\n a = as.pop();\n b = bs.pop();\n tmp = s;\n s = t;\n t = tmp - q*t;\n var expr = '('+s+')*('+a+') + ('+t+')*('+b+')';\n expr = Numbas.jme.display.exprToLaTeX(expr,['basic'],scope);\n lines.push(old_r+' &= '+expr);\n old_r = '';\n}\ntex = '\\\\begin{align}\\n'+lines.join(' \\\\\\\\\\n')+'\\n\\\\end{align}';\nreturn $('

').text(tex);", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd1": {"type": "number", "language": "jme", "definition": "// x in a*x + b*y = gcd(a,b)\nif((a|b) or (b|a),\n0\n,\nextendedgcd2(b,mod(a,b))\n)", "parameters": [["a", "number"], ["b", "number"]]}, "describegcd": {"type": "html", "language": "javascript", "definition": "// describe the steps of the Euclidean algorithm\nvar table = $('

First of all, the biggest number needs to go first:	$\\\\operatorname{gcd}(\\\\var{'+a+'},\\\\var{'+b+'}) = \\\\operatorname{gcd}(\\\\var{'+b+'},\\\\var{'+a+'}), $
Finally, $\\\\var{'+b+'}$ divides into $\\\\var{'+a+'}$ exactly $\\\\var{'+a/b+'}$ times:	$\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+a/b+'}.$
Divide $\\\\var{'+a+'}$ by $\\\\var{'+b+'}$ with remainder $\\\\var{'+(a%b)+'}$:	$\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+Math.floor(a/b)+'} + \\\\var{'+(a%b)+'},$

');\nwhile(a%b!=0) {\n if(a');\n var t = a;\n a = b;\n b = t;\n } else {\n table.append('');\n var t = a;\n a = b\n b = t%b;\n }\n}\ntable.append('');\nreturn table;", "parameters": [["a", "number"], ["b", "number"]]}, "long_gcd": {"type": "list", "language": "jme", "definition": "// return a pair of numbers (x,y) with gcd(x,y)=b, and the euclidean algorithm takes steps to get to this point\nif(lines<=0,\n [a,b],\n let(m,random(2..10),\n long_gcd(a*m+b,a,lines-1)\n )\n)", "parameters": [["a", "number"], ["b", "number"], ["lines", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "// y in a*x + b*y = gcd(a,b)\nif((a|b) or (b|a),\n1\n,\nextendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n)", "parameters": [["a", "number"], ["b", "number"]]}}, "showQuestionGroupNames": false, "parts": [{"prompt": "

Find $d = \\operatorname{gcd}(\\var{a},\\var{b})$, the greatest common divisor of $\\var{a}$ and $\\var{b}$:

$d = $ [[0]]

", "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showPrecisionHint": false, "variableReplacementStrategy": "originalfirst", "allowFractions": false, "scripts": {}, "type": "numberentry", "showCorrectAnswer": true, "minValue": "d", "maxValue": "d", "variableReplacements": [], "marks": 1}], "type": "gapfill", "showCorrectAnswer": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}, {"prompt": "

Now find integers $s$ and $t$ such that $0 \\le s \\le \\var{show_diff-1}$ and

\\[\\var{a}s+\\var{b}t = d\\]

$s = $ [[0]]

$t = $ [[1]]

Click on Show steps for more information on the possible solutions for $s$ and $t$.

", "marks": 0, "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showPrecisionHint": false, "variableReplacementStrategy": "originalfirst", "allowFractions": false, "scripts": {}, "type": "numberentry", "showCorrectAnswer": true, "minValue": "sval", "maxValue": "sval", "variableReplacements": [], "marks": 1}, {"correctAnswerFraction": false, "showPrecisionHint": false, "variableReplacementStrategy": "originalfirst", "allowFractions": false, "scripts": {}, "type": "numberentry", "showCorrectAnswer": true, "minValue": "tval", "maxValue": "tval", "variableReplacements": [], "marks": 1}], "type": "gapfill", "showCorrectAnswer": true, "steps": [{"prompt": "

If you find $s_1$ and $t_1$ such that $\\var{a}s_1+\\var{b}t_1=d$ but $s_1$ does not satisfy $0 \\le s_1 \\le \\var{show_diff-1}$ then you can add the following integer multiples to $s_1$ and $t_1$ so that the requirement is met:

\\begin{align}
s &= s_1+\\lambda \\times \\frac{\\var{b}}{d} \\\\\\\\
t &= t_1-\\lambda \\times \\frac{\\var{a}}{d}
\\end{align}

You have to find the appropriate value of $\\lambda$ if the requirement is not met.

You can easily check that it is still the case that $\\var{a}s+\\var{b}t=d$.

", "scripts": {}, "type": "information", "showCorrectAnswer": true, "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0}], "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "stepsPenalty": 0}], "statement": "", "tags": ["checked2015", "euclidean algorithm", "gcd", "greatest common divisor", "MAS1702", "MAS2213", "number theory"], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "

The functions to generate the tables in the Advice could be done a lot better using the new HTML data type, but they do work.

", "licence": "Creative Commons Attribution 4.0 International", "description": "

Given two numbers, find the gcd, then use Bézout's algorithm to find $s$ and $t$ such that $as+bt=\\operatorname{gcd}(a,b)$.

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

a)

On applying the standard method for finding the $\\operatorname{gcd}$ of two numbers we have the following sequence of operations:

{describegcd(a,b)}

The last non-zero remainder is $\\var{d}$, so this is the $\\operatorname{gcd}$ of $\\var{a}$ and $\\var{b}$.

b)

Now work backwards through those steps, rearranging them to find the remainders as linear combinations of the other numbers.

When you reach the last line you will have found $s_1$ and $t_1$ such that

\\[\\var{a}s_1+\\var{b}t_1= \\var{d}\\]

In this case we find:

{describebezout(a,b)}

So we obtain values $s_1 = \\var{s}$ and $t_1 = \\var{t}$.

We see that $0 \\le s_1 \\le \\var{show_diff-1}$ and so meets our requirement and we have $s=\\var{s}$, $t=\\var{t}$.

We see that $s_1$ does not meet the requirement that $0 \\le s_1 \\le \\var{show_diff-1}$.

Note that if $(s,t)$ is a solution to $\\simplify{{a}s + {b}t = {d}}$, then $(\\simplify[]{s + lambda*({b}/{d})}, \\simplify[]{t + lambda*({-a}/{d})})$ is also a solution.

So we have to add a multiple of $\\frac{\\var{b}}{\\var{d}}=\\var{b/d}$ to $s_1$ and the same multiple of $-\\frac{\\var{a}}{\\var{d}} = -\\var{a/d}$ to $t_1$.

We see that the multiple is $\\var{multiple}$ and we have:

\\begin{align}
s =\\var{s} + \\var{multiple}\\times \\var{b/d} &= \\var{sval}, \\\\
t =\\var{t} - \\var{multiple}\\times \\var{a/d} &= \\var{tval}.
\\end{align}

"}, {"name": "Divide two elements of $\\mathbb{Z}[i]$", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d*t+c*v+n", "description": "", "name": "b"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(m=1,random(2..5),if(m=2,random(1,3,4,5),if(m=3,random(1,2,4,5),if(m=4,random(1,2,3,5),random(1..4)))))", "description": "", "name": "n"}, "p1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..4)", "description": "", "name": "p1"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(n+m)*p1", "description": "", "name": "c"}, "v": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "v"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(n-m)*p1", "description": "", "name": "d"}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "t"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..5)", "description": "", "name": "p"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "c*t-d*v+m", "description": "", "name": "a"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..5)", "description": "", "name": "m"}}, "ungrouped_variables": ["a", "c", "p1", "d", "m", "n", "p", "b", "t", "v"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"answer": "{m}+{n}i", "vsetrange": [0, 1], "checkingaccuracy": 0.001, "showCorrectAnswer": true, "expectedvariablenames": [], "notallowed": {"message": "

Please input your answers in the form a+b*i where a and b are integers. Do not include decimal numbers.

", "showStrings": false, "partialCredit": 0, "strings": ["."]}, "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "checkvariablenames": false, "type": "jme", "answersimplification": "all,!collectNumbers", "marks": 1, "vsetrangepoints": 5}, {"answer": "{t}+{v}*i", "showCorrectAnswer": true, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "answersimplification": "all,!collectNumbers", "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Remainder $r=\\;$[[0]]

Find $z=c+di$ such that $\\simplify[all,!collectNumbers]{{a}+{b}*i=({c}+{d}*i)*z+r}$

$z=\\;$[[1]]

Please input your answers in the form a+b*i where a and b are integers. Do not include decimal numbers.

", "showCorrectAnswer": true, "marks": 0}], "statement": "

In the Gaussian integer ring $\\mathbb{Z}[i]$ , find the remainder $r=a+bi$, where $a \\gt 0,\\;b \\gt 0$ , on dividing $\\simplify[all,!collectNumbers]{{a}+{b}*i}$ by $\\simplify[all,!collectNumbers]{{c}+{d}*i}$ .

", "tags": ["algebra", "checked2015", "division", "euclidean rings", "factorization in rings", "gaussian integers", "gcd", "gcd in euclidean rings", "MAS2213", "remainders", "rings"], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "

16/01/2013:

Based on iassess questions.

", "licence": "Creative Commons Attribution 4.0 International", "description": "

In the Gaussian integer ring $\\mathbb{Z}[i]$ , find the remainder $r=r_1+r_2i$, where $a \\gt 0,\\;b \\gt 0$ , on dividing $a+bi$ by $c+di$ .

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

We have:

\\[\\begin{align}\\simplify[all,!collectNumbers]{({a} + {b} * i) / ({c} + {d} * i)}& = \\simplify[all,!collectNumbers]{(({a} + {b} * i) * ({c} + { -d} * i)) / (({c} + {d} * i) * ({c} + { -d} * i))}\\\\& = \\simplify[all,!collectNumbers]{{a * c + b * d} / {c ^ 2 + d ^ 2} + ({b * c -(a * d)} / {c ^ 2 + d ^ 2}) * i}\\\\&=\\simplify[all,!collectNumbers]{{(a * c + b * d) / (c ^ 2 + d ^ 2)} + {(b * c -(a * d)) / (c ^ 2 + d ^ 2)} * i}\\\\& \\approx \\simplify[all,!collectNumbers]{{t} + {v}* i}\\end{align}\\]

on taking the nearest integer values.

Taking $z= \\simplify[all,!collectNumbers]{{t} + {v}* i}$ and on calculating we find:

\\[\\simplify[all,!collectNumbers]{{a} + {b} * i = ({c} + {d} * i) * ({t} + {v} * i) + {m} + {n} * i}\\]

So the remainder is $r=\\simplify{{m}+{n}*i}$.

Note that: \\[N(r) = \\simplify{{m ^ 2 + n ^ 2}} \\lt \\simplify[all,!collectNumbers]{N({c} + {d} * i) = {c ^ 2 + d ^ 2}}.\\]

"}, {"name": "Divide two elements of $\\mathbb{Z}[\\sqrt{2}]$", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"v": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "v"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(m=1,random(2..5),if(m=2,random(3,4,5),if(m=3,random(1,2,4,5),if(m=4,random(1,3,5),random(1..4)))))", "description": "", "name": "n"}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d*t+c*v+n", "description": "", "name": "b"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(2*n-m)*p", "description": "", "name": "c"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(m-n)*p", "description": "", "name": "d"}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "t"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..5)", "description": "", "name": "p"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "c*t+2*d*v+m", "description": "", "name": "a"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..5)", "description": "", "name": "m"}}, "ungrouped_variables": ["a", "c", "b", "d", "m", "n", "p", "t", "v"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"answer": "{m}+{n}sqrt(2)", "showCorrectAnswer": true, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "answersimplification": "all,!collectNumbers", "marks": 1, "vsetrangepoints": 5}, {"answer": "{t}+{v}*sqrt(2)", "musthave": {"message": "

Please input your answer in the form a+b*sqrt(2) where a and b are integers.

", "showStrings": false, "partialCredit": 0, "strings": ["sqrt(2)"]}, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "showCorrectAnswer": true, "expectedvariablenames": [], "notallowed": {"message": "

Please input your answer in the form a+b*sqrt(2) where a and b are integers. Do not include decimal numbers.

Remainder $r=\\;$[[0]]

Find $z=c+d\\sqrt{2}$ such that $\\simplify[all,!collectNumbers]{{a}+{b}*sqrt(2)=({c}+{d}*sqrt(2))*z+r}$

$z=\\;$[[1]]

Please input your answers in the form a+b*sqrt(2) where a and b are integers. Do not include decimal numbers.

", "showCorrectAnswer": true, "marks": 0}], "statement": "

In the quadratic number ring $\\mathbb{Z}[\\sqrt{2}]$ , find the remainder $r=a+b\\sqrt{2}$, where $a \\gt 0,\\;b \\gt 0$ , on dividing $\\simplify[all,!collectNumbers]{{a}+{b}*sqrt(2)}$ by $\\simplify[all,!collectNumbers]{{c}+{d}*sqrt(2)}$ .

", "tags": ["checked2015", "division rings", "euclidean rings", "quadratic number rings", "rings"], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "

In the ring $\\mathbb{Z}[\\sqrt{2}]$ , find the remainder $r=r_1+r_2\\sqrt{2}$, where $a \\gt 0,\\;b \\gt 0$ , on dividing $a+b\\sqrt{2}$ by $c+d\\sqrt{2}$ .

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

We have:

\\[\\begin{align}\\simplify[all,!collectNumbers]{({a} + {b} * sqrt(2)) / ({c} + {d} * sqrt(2))}& = \\simplify[all,!collectNumbers]{(({a} + {b} * sqrt(2)) * ({c} + { -d} * sqrt(2))) / (({c} + {d} * sqrt(2)) * ({c} + { -d} * sqrt(2)))}\\\\
& = \\simplify{{a * c - 2*b * d} / {c ^ 2 -2*d ^ 2} + ({b * c -(a * d)} / {c ^ 2 - 2*d ^ 2}) * sqrt(2)}\\\\&=\\simplify[all,!collectNumbers]{{(a * c - 2*b * d) / (c ^ 2 - 2*d ^ 2)} + {(b * c -(a * d)) / (c ^ 2 - 2*d ^ 2)} * sqrt(2)}\\\\
& \\approx \\simplify[all,!collectNumbers]{{t} + {v}* sqrt(2)}\\end{align}\\]

on taking the nearest integer values.

Taking $z= \\simplify[all,!collectNumbers]{{t} + {v}* sqrt(2)}$ and on calculating we find:

\\[\\simplify[all,!collectNumbers]{{a} + {b} * sqrt(2) = ({c} + {d} * sqrt(2)) * ({t} + {v} * sqrt(2)) + {m} + {n} * sqrt(2)}\\]

So the remainder is $r=\\simplify[all,!collectNumbers]{{m}+{n}*sqrt(2)}$.

Note that: \\[N(r) = \\simplify[all,!collectNumbers]{Abs({m ^ 2 -(2 * n ^ 2)}) = {Abs(m ^ 2 -(2 * n ^ 2))}} \\lt\\simplify[all,!collectNumbers]{ N({c} + {d} * Sqrt(2)) = Abs({c ^ 2 -(2 * d ^ 2)}) = {Abs(c ^ 2 -(2 * d ^ 2))}}.\\]

"}, {"name": "Divide two numbers in $\\mathbb{Z}[\\sqrt{-2}]$", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "d*t+c*v+n", "description": "", "name": "b"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(m=1,random(2..5),if(m=2,random(1,3,4,5),if(m=3,random(1,2,4,5),if(m=4,random(1,2,3,5),random(1..4)))))", "description": "", "name": "n"}, "p1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..3)", "description": "", "name": "p1"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(2*n+m)*p1", "description": "", "name": "c"}, "v": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "v"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "(n-m)*p1", "description": "", "name": "d"}, "t": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "t"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(3..5)", "description": "", "name": "p"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "c*t-2*d*v+m", "description": "", "name": "a"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..5)", "description": "", "name": "m"}}, "ungrouped_variables": ["a", "c", "p1", "d", "m", "n", "p", "b", "t", "v"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"answer": "{m}+{n}sqrt(-2)", "musthave": {"message": "

Please input your answers in the form a+b*sqrt(-2) where a and b are integers. Do not include decimal numbers.

", "showStrings": false, "partialCredit": 0, "strings": ["sqrt(-2)"]}, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "showCorrectAnswer": true, "expectedvariablenames": [], "notallowed": {"message": "

Please input your answers in the form a+b*sqrt(-2) where a and b are integers. Do not include decimal numbers.

", "showStrings": false, "partialCredit": 0, "strings": ["."]}, "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "checkvariablenames": false, "type": "jme", "answersimplification": "all,!collectNumbers", "marks": 1, "vsetrangepoints": 5}, {"answer": "{t}+{v}*sqrt(-2)", "showCorrectAnswer": true, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "answersimplification": "all,!collectNumbers", "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Remainder $r=\\;$[[0]]

Find $z=c+d\\sqrt{-2}$ such that $\\simplify[all,!collectNumbers]{{a}+{b}*sqrt(-2)=({c}+{d}*sqrt(-2))*z+r}$

$z=\\;$[[1]]

Please input your answers in the form a+b*sqrt(-2) where a and b are integers. Do not include decimal numbers.

", "showCorrectAnswer": true, "marks": 0}], "statement": "

In the quadratic number ring $\\mathbb{Z}[\\sqrt{-2}]$ , find the remainder $r=a+b\\sqrt{-2}$, where $a \\gt 0,\\;b \\gt 0$ , on dividing $\\simplify[all,!collectNumbers]{{a}+{b}*sqrt(-2)}$ by $\\simplify[all,!collectNumbers]{{c}+{d}*sqrt(-2)}$ .

", "tags": ["checked2015", "division rings", "euclidean rings", "MAS2213", "remainders", "rings"], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "

In the ring $\\mathbb{Z}[\\sqrt{-2}]$ , find the remainder $r=r_1+r_2\\sqrt{-2}$, where $a \\gt 0,\\;b \\gt 0$ , on dividing $a+b\\sqrt{-2}$ by $c+d\\sqrt{-2}$ .

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

We have:

\\[\\begin{align}\\simplify[all,!collectNumbers]{({a} + {b} * sqrt(-2)) / ({c} + {d} * sqrt(-2))}& = \\simplify[all,!collectNumbers]{(({a} + {b} * sqrt(-2)) * ({c} + { -d} * sqrt(-2))) / (({c} + {d} * sqrt(-2)) * ({c} + { -d} * sqrt(-2)))}\\\\
& = \\simplify{{a * c + 2*b * d} / {c ^ 2 + 2*d ^ 2} + ({b * c -(a * d)} / {c ^ 2 + 2*d ^ 2}) * sqrt(-2)}\\\\&=\\simplify[all,!collectNumbers]{{(a * c + 2*b * d) / (c ^ 2 + 2*d ^ 2)} + {(b * c -(a * d)) / (c ^ 2 + 2*d ^ 2)} * sqrt(-2)}\\\\
& \\approx \\simplify[all,!collectNumbers]{{t} + {v}* sqrt(-2)}\\end{align}\\]

on taking the nearest integer values.

Taking $z= \\simplify[all,!collectNumbers]{{t} + {v}* sqrt(-2)}$ and on calculating we find:

\\[\\simplify[all,!collectNumbers]{{a} + {b} * sqrt(-2) = ({c} + {d} * sqrt(-2)) * ({t} + {v} * sqrt(-2)) + {m} + {n} * sqrt(-2)}\\]

So the remainder is $r=\\simplify[all,!collectNumbers]{{m}+{n}*sqrt(-2)}$.

Note that: \\[N(r) = \\simplify{{m ^ 2 + 2*n ^ 2}} \\lt \\simplify[all,!collectNumbers]{N({c} + {d} * sqrt(-2)) = {c ^ 2 + 2*d ^ 2}}.\\]

"}, {"name": "Factorise polynomial into irreducible factors", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"d3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g0+be+g1*al,n)", "description": "", "name": "d3"}, "h0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(h1=0,random(2,3),if(h1=1,random(1,2),if(h1=2,random(3,4),if(h1=3,random(3,4),random(1,2)))))", "description": "", "name": "h0"}, "f1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(h1*g0+g1*h0,n)", "description": "", "name": "f1"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "a1"}, "c2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c+a,n)", "description": "", "name": "c2"}, "be": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(al=0,random(1,3,4),0)", "description": "", "name": "be"}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(a=0,random(2,3),if(a=1,random(1,2),\nif(a=2,random(3,4),if(a=3,random(3,4),random(1,2)))))", "description": "", "name": "b"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "5", "description": "", "name": "n"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0,1,2,3,4)", "description": "", "name": "a"}, "f2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(h1*g1+h0+g0,n)", "description": "", "name": "f2"}, "g0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(g1=0,random(2,3),if(g1=1,random(1,2),if(g1=2,random(3,4),if(g1=3,random(3,4),random(1,2)))))", "description": "", "name": "g0"}, "f3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g1+h1,n)", "description": "", "name": "f3"}, "h1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(g1=0,random(1..4),if(g1=1,random(0,2,3,4),if(g1=2,random(0,1,3,4),if(g1=3,random(0,1,2,4),random(0..3)))))", "description": "", "name": "h1"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(a1=1,random(2..4),if(a1=2,random(1,3,4),if(a1=3,random(1,2,4),random(1..3))))", "description": "", "name": "a2"}, "c0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(b*c,n)", "description": "", "name": "c0"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1,2,3,4)", "description": "", "name": "c"}, "g1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0,1,2,3,4)", "description": "", "name": "g1"}, "d2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g0*al+be*g1+ga,n)", "description": "", "name": "d2"}, "d4": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g1+al,n)", "description": "", "name": "d4"}, "b0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a1*a2,n)", "description": "", "name": "b0"}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a1+a2,n)", "description": "", "name": "b1"}, "al": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(0..4)", "description": "", "name": "al"}, "d1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g1*ga+g0*be,n)", "description": "", "name": "d1"}, "c1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a*c+b,n)", "description": "", "name": "c1"}, "ga": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(al=1,random(1,2),if(al=2,random(1,3),if(al=3,2,if(al=4,3,if(be=1,random(1,4), if(be=4,random(2,3),2))))))", "description": "", "name": "ga"}, "f0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(h0*g0,n)", "description": "", "name": "f0"}, "d0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(g0*ga,n)", "description": "", "name": "d0"}}, "ungrouped_variables": ["f0", "f1", "f2", "f3", "h0", "h1", "al", "b0", "b1", "ga", "d4", "d2", "d3", "d0", "d1", "be", "g1", "g0", "a1", "a2", "c2", "c1", "c0", "a", "c", "b", "n"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"answer": "X^2+{g1}*X+{g0}", "showCorrectAnswer": true, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "answersimplification": "all", "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Consider $f(X)$ and $g(X)$ as polynomials over $\\mathbb{Z}_{\\var{n}}$.

Find their greatest common divisor (GCD) and enter it as a monic polynomial.

Note that the coefficients all should be in $\\mathbb{Z}_{\\var{n}}=\\{0,\\;1,\\;2,\\;3,\\;4\\}$.

GCD=[[0]].

Click on Show steps to obtain information on monic polynomials over $\\mathbb{Z}_{\\var{n}}$.

", "steps": [{"type": "information", "prompt": "

Monic Polynomials.

A monic polynomial over $\\mathbb{Z}_{\\var{n}}$ has the coefficient of the greatest power equalling $1$.

For example: in order to normalize $2X^2+3X+1$ over $\\mathbb{Z}_{\\var{n}}$ into a monic polynomial we are allowed to multiply the polynomial by a constant, and since$ 2^{-1} = 3 \\mod {\\var{n}}$ we have on multiplying the polynomial throughout by $3$ that

$\\simplify{3 * (2 * X ^ 2 + 3 * X + 1) = 6 * X ^ 2 + 9 * X + 3 = X ^ 2 + 4 * X + 3}$ as a polynomial over $\\mathbb{Z}_{\\var{n}}$

and which is now a monic polynomial .

", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}, {"scripts": {}, "gaps": [{"answer": "(((X ^ 2) + ({g1} * X) + {g0}) * ((X ^ 2) + ({h1} * X) + {h0}))", "musthave": {"message": "

Factorize the polynomial into irreducible factors.

", "showStrings": false, "partialCredit": 0, "strings": ["("]}, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "showCorrectAnswer": true, "expectedvariablenames": [], "notallowed": {"message": "

Factorize the polynomial into irreducible factors.

", "showStrings": false, "partialCredit": 0, "strings": ["^4", "^3"]}, "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "checkvariablenames": false, "type": "jme", "answersimplification": "all", "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Find the irreducible factorization of $f(X)$ over $\\mathbb{Z}_{\\var{n}}$.

$f(X)=\\;$[[0]]

", "showCorrectAnswer": true, "marks": 0}], "statement": "

Let \\[\\begin{align}\\\\
f(X)&=\\simplify{ X ^ 4 + {f3} * X ^ 3 + {f2} * X ^ 2 + {f1} * X + {f0}}\\\\\\\\
g(X)&=\\simplify{X^5+{d4}*X^4+{d3}*X ^ 3 + {d2} * X ^ 2 + {d1} * X + {d0}}\\end{align}\\]

", "tags": ["checked2015", "factorize polynomials", "finite fields", "gcd", "irreducible polynomials", "MAS2213", "normalized polynomials", "polynomials over finite fields"], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "

$f(X)$ and $g(X)$ are polynomials over $\\mathbb{Z}_n$.

Find their greatest common divisor (GCD) and enter it as a monic polynomial.

Hence factorize $f(X)$ into irreducible factors.

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

1. We have on using the Euclidean Algorithm that the GCD of $f(X)$ and $g(X)$ is $\\simplify{X^2+{g1}*X+{g0}}$ over $\\mathbb{Z}_{\\var{n}}$.

Note that this GCD is a monic polynomial.

2. Hence $\\simplify{X^2+{g1}*X+{g0}}$ is a factor of $f(X)$ and is irreducible over $\\mathbb{Z}_{\\var{n}}$ as you can check.

On dividing $f(X)$ by $\\simplify{X^2+{g1}*X+{g0}}$ we obtain:

$f(X) = \\simplify{(X ^ 2 + {g1} * X + {g0}) * (X ^ 2 + {h1} * X + {h0})}$ over $\\mathbb{Z}_{\\var{n}}$.

You can check that $\\simplify{X ^ 2 + {h1} * X + {h0}}$ is also irreducible over $\\mathbb{Z}_{\\var{n}}$.

Hence the above factorization expresses $f(X)$ as the product of irreducible polynomials over $\\mathbb{Z}_{\\var{n}}$.

"}, {"name": "Factorise polynomials over Z_5", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "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/"}], "parts": [{"prompt": "

$\\simplify[all,!collectnumbers]{{d1}+{c1}X+X^2} = $ [[0]]

", "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": "

{poly2} $=$ [[0]]

", "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": "

{poly3} $=$ [[0]]

", "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": "

{poly4} $=$ [[0]]

", "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": [], "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": "

Factorize the following polynomials over $\\mathbb{Z}_{\\var{n}}$ into their monic irreducible factors.

You must enter all polynomials with coefficients in $\\mathbb{Z}_{\\var{n}}=\\{0,\\;1,\\;2,\\;3,\\;4\\}$ (and no negative coefficients).

", "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;iFactorise 4 polynomials over $\\mathbb{Z}_5$.

"}, "advice": "

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)$.

Note also that any integers in your answers have to be positive. You can easily convert any negative integer into a positive integer $\\bmod \\var{n}$ by adding multiples of $\\var{n}$.

a)

For $f(X)= \\simplify[all,!collectnumbers]{{d1}+{c1}X+X^2}$, trying the values $X = 1, \\; 2, \\; 3, \\; 4$ gives

{table([[x_header,'1','2','3','4'],[fx_header]+map(d1+c1*x+x^2,x,1..4)])}

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.

So, we obtain

\\[f(X)=(\\var{a1}+X)(\\var{b1}+X)\\]

b)

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 X+\\var{a} \\pmod{\\var{n}}$ is a factor.

We see on dividing $\\var{poly2}$ by $X+\\var{a}$ that

\\[ \\var{poly2} \\equiv \\simplify[all,!collectNumbers,!noleadingMinus]{({a}+X)({b[0]}+{b[1]}X+X^2)} \\pmod{\\var{n}} \\]

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.

So factorising into irreducible factors gives

\\[ f(X)=\\simplify[all,!collectNumbers,!noleadingMinus]{({a}+X)({b[0]}+{b[1]}X+X^2)} \\]

c)

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.

We see on dividing $\\var{poly3}$ by $X+\\var{d}$ that

\\[ \\var{poly3} \\equiv \\simplify[all,!collectNumbers,!noleadingMinus]{({d}+X)({p[0]}+{p[1]}X+X^2)} \\pmod{\\var{n}} \\]

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.

So factorising into irreducible factors gives

\\[ f(X)=\\simplify[all,!collectNumbers,!noleadingMinus]{({d}+X)({p[0]}+{p[1]}X+X^2)} \\]

d)

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.

We see on dividing $\\var{poly4}$ by $X+\\var{q}$ that

\\[ \\var{poly4} \\equiv \\simplify[all,!collectNumbers,!noleadingMinus]{({q}+X)({m[0]}+{m[1]}X+{m[2]}X^2+X^3)} \\pmod{\\var{n}} \\]

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$.

We can confirm 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.

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)}\\]

"}, {"name": "Find greatest common divisor of two polynomials over the rationals", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "variable_groups": [], "variables": {"r1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "1", "description": "", "name": "r1"}, "d0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "r2*a2*a3+n2", "description": "", "name": "d0"}, "n1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "n*r1", "description": "", "name": "n1"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..3)", "description": "", "name": "a1"}, "d1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a2*r2+a3*r2+a2*a3+n1", "description": "", "name": "d1"}, "n2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "n*r2", "description": "", "name": "n2"}, "d2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "r2+a2+a3", "description": "", "name": "d2"}, "c1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1*(r2*(a2+a3)+a2*a3+n1)+n2+a3+r2*a2*a3+r2", "description": "", "name": "c1"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "5", "description": "", "name": "n"}, "a3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..4)", "description": "", "name": "a3"}, "r2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(-3,-2,-1,1,2,3)", "description": "", "name": "r2"}, "c3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "r2+a1+a2+a3", "description": "", "name": "c3"}, "c2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "1+a1*(r2+a2+a3)+n1+r2*(a2+a3)+a2*a3", "description": "", "name": "c2"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..3)", "description": "", "name": "a2"}, "c0": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1*r2*a2*a3+a1*n2+r2*a3", "description": "", "name": "c0"}}, "ungrouped_variables": ["r1", "r2", "n", "a1", "a3", "a2", "n1", "c3", "c2", "n2", "c0", "d2", "c1", "d0", "d1"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "functions": {}, "showQuestionGroupNames": false, "parts": [{"stepsPenalty": 0, "scripts": {}, "gaps": [{"answer": "X+{r2}", "showCorrectAnswer": true, "vsetrange": [0, 1], "checkingaccuracy": 0.001, "checkvariablenames": false, "expectedvariablenames": [], "showpreview": true, "checkingtype": "absdiff", "scripts": {}, "type": "jme", "answersimplification": "all", "marks": 1, "vsetrangepoints": 5}], "type": "gapfill", "prompt": "

Consider $f(X)$ and $g(X)$ as polynomials over the rational numbers $\\mathbb{Q}$.

Find their greatest common divisor (GCD).

GCD=[[0]].

You must input your answer as a monic polynomial over $\\mathbb{Q}$ .

Click on Steps to obtain information on monic polynomials.

", "steps": [{"type": "information", "prompt": "

Normalized Polynomials.

A monic polynomial over $\\mathbb{Q}$ has the coefficient of the greatest power equalling 1.

If a polynomial over $\\mathbb{Q}$ has the coefficient of the greatest power $a \\neq 1$, then you multiply the polynomial by $\\frac{1}{a}$.

", "showCorrectAnswer": true, "scripts": {}, "marks": 0}], "showCorrectAnswer": true, "marks": 0}], "statement": "

Let \\[\\begin{align}\\\\
f(X)&=\\simplify{ X ^ 4 + {c3} * X ^ 3 + {c2} * X ^ 2 + {c1} * X + {c0}}\\\\\\\\
g(X)&=\\simplify{X ^ 3 + {d2} * X ^ 2 + {d1} * X + {d0}}\\end{align}\\]

", "tags": ["checked2015", "factorize polynomials", "fields", "gcd of polynomials", "MAS2213", "normalized polyno9mials", "polynomials over fields", "polynomials over the rationals"], "rulesets": {}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "

$f(X)$ and $g(X)$ as polynomials over the rational numbers $\\mathbb{Q}$.

Find their greatest common divisor (GCD) and enter as a normalized polynomial.

"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "

First we divide $f(X)$ by $g(X)$ to get the remainder $r_1(X) =\\simplify{ X ^ 2 + {r2 + a3} * X + {r2 * a3}}$ :

\\[f(X) = \\simplify{X ^ 4 + {c3} * X ^ 3 + {c2} * X ^ 2 + {c1} * X + {c0} = (X + {a1}) * (X ^ 3 + {d2} * X ^ 2 + {d1} * X + {d0}) + X ^ 2 + {r2 + a3} * X + {r2 * a3}}\\]

Next we divide $g(X)$ by $r_1(X)$ to get the remainder $ r_2(X) =\\simplify{ {n1} * X + {n2}}$ :

\\[g(X) = \\simplify{X ^ 3 + {d2} * X ^ 2 + {d1} * X + {d0} = (X + {a2}) * (X ^ 2 + {r2 + a3} * X + {r2 * a3}) + {n1} * X + {n2}}\\]

Now divide $r_1(X)$ by $r_2(X)$ to obtain:

\\[r _1(X) =\\simplify{ X ^ 2 + {r2 + a3} * X + {r2 * a3} = (1 / {n}) * (X + {a3}) * ({n1} * X + {n2})}\\]

As we have zero remainder, the last non-zero remainder is the GCD and this is $\\simplify{{n1} * X + {n2}}$.

But we have to make this into a monic polynomial and the required monic GCD $\\simplify{X+{r2}}$ is given by multiplying by $\\frac{1}{\\var{n1}}$ so that the coefficient of the highest degree term is 1.

"}], "name": "", "pickQuestions": 0}], "name": "Abstract algebra", "showQuestionGroupNames": false, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "Questions used in a university course titled \"Abstract algebra\""}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}], "extensions": [], "custom_part_types": [], "resources": []}

First of all, the biggest number needs to go first:	$\\\\operatorname{gcd}(\\\\var{'+a+'},\\\\var{'+b+'}) = \\\\operatorname{gcd}(\\\\var{'+b+'},\\\\var{'+a+'}), $
Divide $\\\\var{'+a+'}$ by $\\\\var{'+b+'}$ with remainder $\\\\var{'+(a%b)+'}$:	$\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+Math.floor(a/b)+'} + \\\\var{'+(a%b)+'},$
Finally, $\\\\var{'+b+'}$ divides into $\\\\var{'+a+'}$ exactly $\\\\var{'+a/b+'}$ times:	$\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+a/b+'}.$