// Numbas version: exam_results_page_options
{"name": "Simplify integers and rationals in Z_n", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"s1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1,-1)", "name": "s1", "description": ""}, "b3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2,4,8,13,16,17)", "name": "b3", "description": ""}, "ans1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "a1*b1 + c1*d1 - f1", "name": "ans1", "description": ""}, "f1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(2..9)", "name": "f1", "description": ""}, "inv5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(rinv5, 5)", "name": "inv5", "description": ""}, "ans13": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,3)", "name": "ans13", "description": ""}, "p3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(3,b3),min(3,b3))", "name": "p3", "description": ""}, "inv11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(rinv11, 11)", "name": "inv11", "description": ""}, "s2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(s1=1,-1,1)", "name": "s2", "description": ""}, "rinv3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<3,q3,p3)", "name": "rinv3", "description": ""}, "q7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(7,b3),min(7,b3))", "name": "q7", "description": ""}, "ans15": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,5)", "name": "ans15", "description": ""}, "inv3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos( rinv3, 3)", "name": "inv3", "description": ""}, "rinv7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<7,q7,p7)", "name": "rinv7", "description": ""}, "c3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(17,19,23,29,31,37,41,43,47)", "name": "c3", "description": ""}, "q5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(5,b3),min(5,b3))", "name": "q5", "description": ""}, "minv3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv3,3)", "name": "minv3", "description": ""}, "ans111": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,11)", "name": "ans111", "description": ""}, "minv7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv7,7)", "name": "minv7", "description": ""}, "ans211": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,11)", "name": "ans211", "description": ""}, "minv5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv5,5)", "name": "minv5", "description": ""}, "ans27": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,7)", "name": "ans27", "description": ""}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "s2*random(3..4)", "name": "b1", "description": ""}, "q11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(11,b3),min(11,b3))", "name": "q11", "description": ""}, "ans23": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,3)", "name": "ans23", "description": ""}, "p7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(7,b3),min(7,b3))", "name": "p7", "description": ""}, "d1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(4..9)", "name": "d1", "description": ""}, "p5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(5,b3),min(5,b3))", "name": "p5", "description": ""}, "p11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(max(11,b3),min(11,b3))", "name": "p11", "description": ""}, "q3": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(max(3,b3),min(3,b3))", "name": "q3", "description": ""}, "inv7": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(rinv7, 7)", "name": "inv7", "description": ""}, "c1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(4..9)", "name": "c1", "description": ""}, "rinv11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<11,q11,p11)", "name": "rinv11", "description": ""}, "rinv5": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(b3<5,q5,p5)", "name": "rinv5", "description": ""}, "ans17": {"templateType": "anything", "group": "Ungrouped variables", "definition": "makepos(ans1,7)", "name": "ans17", "description": ""}, "ans25": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a2,5)", "name": "ans25", "description": ""}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)", "name": "a2", "description": ""}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "s1*random(3..9)", "name": "a1", "description": ""}, "minv11": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(c3*inv11,11)", "name": "minv11", "description": ""}}, "ungrouped_variables": ["f1", "p7", "ans1", "inv11", "b1", "b3", "ans27", "ans25", "ans23", "d1", "q3", "rinv11", "q5", "ans211", "s2", "s1", "ans111", "minv11", "a1", "ans13", "a2", "q11", "ans17", "ans15", "c3", "c1", "rinv3", "rinv5", "rinv7", "p3", "q7", "p11", "inv7", "inv5", "p5", "inv3", "minv3", "minv7", "minv5"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "name": "Simplify integers and rationals in Z_n", "showQuestionGroupNames": false, "functions": {"extendedgcd1": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "definition": "\n\n\nif((a|b) or (b|a),\n\n1\n\n,\n\nextendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n\n)\n\n\n", "parameters": [["a", "number"], ["b", "number"]]}, "makepos": {"type": "number", "language": "jme", "definition": "mod(a,b)", "parameters": [["a", "number"], ["b", "number"]]}}, "parts": [{"scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans13}", "maxValue": "{ans13}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans15}", "maxValue": "{ans15}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans17}", "maxValue": "{ans17}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans111}", "maxValue": "{ans111}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans23}", "maxValue": "{ans23}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans25}", "maxValue": "{ans25}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans27}", "maxValue": "{ans27}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{ans211}", "maxValue": "{ans211}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv3}", "maxValue": "{inv3}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv5}", "maxValue": "{inv5}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv7}", "maxValue": "{inv7}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{inv11}", "maxValue": "{inv11}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv3}", "maxValue": "{minv3}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv5}", "maxValue": "{minv5}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv7}", "maxValue": "{minv7}", "marks": 0.25, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "correctAnswerFraction": false, "minValue": "{minv11}", "maxValue": "{minv11}", "marks": 0.25, "showPrecisionHint": false}], "type": "gapfill", "prompt": "<p>&nbsp;</p>\n<table border=\"1\">\n<tbody>\n<tr><th>&nbsp;</th><th>$\\mathbb{Z}_{3}$</th><th>$\\mathbb{Z}_{5}$</th><th>$\\mathbb{Z}_{7}$</th><th>$\\mathbb{Z}_{11}$</th></tr>\n<tr>\n<td>$\\simplify[!basic]{{a1}*{b1}+{c1}*{d1}-{f1}}$</td>\n<td>[[0]]</td>\n<td>[[1]]</td>\n<td>[[2]]</td>\n<td>[[3]]</td>\n</tr>\n<tr>\n<td>$\\var{a2}$</td>\n<td>[[4]]</td>\n<td>[[5]]</td>\n<td>[[6]]</td>\n<td>[[7]]</td>\n</tr>\n<tr>\n<td>$ \\displaystyle{ \\frac{1}{\\var{b3}} } $</td>\n<td>[[8]]</td>\n<td>[[9]]</td>\n<td>[[10]]</td>\n<td>[[11]]</td>\n</tr>\n<tr>\n<td>$ \\displaystyle{ \\frac{\\var{c3}}{\\var{b3}} } $</td>\n<td>[[12]]</td>\n<td>[[13]]</td>\n<td>[[14]]</td>\n<td>[[15]]</td>\n</tr>\n</tbody>\n</table>", "showCorrectAnswer": true, "marks": 0}], "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "<p>Simplify the following in each of $\\mathbb{Z}_{3}, \\; \\mathbb{Z}_{5}, \\; \\mathbb{Z}_{7}$ and $\\mathbb{Z}_{11}$.</p>\n<p>For the last two questions, recall that for a prime $p$, $\\displaystyle{\\frac{1}{b} \\bmod{p}}$ is the unique solution to $bx \\equiv 1 \\bmod{p}$.</p>\n<p>You must input all values as positive integers; negative integers are not accepted.</p>", "tags": ["checked2015", "MAS3214"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "<p>Express various integers and rationals mod $\\mathbb{Z}_3, \\;\\mathbb{Z}_5,\\;\\mathbb{Z}_7,\\;\\mathbb{Z}_{11}$</p>"}, "advice": "<p>For the first row, it may help to simplify each of the numbers modulo the number corresponding to each column, and then perform the calculation.</p>\n<p>For example,</p>\n<p>\\begin{align}<br/> \\simplify[!basic]{{a1}*{b1}+{c1}*{d1}-{f1}} &amp;\\equiv \\simplify[!basic]{{mod(a1,3)}*{mod(b3,3)}+{mod(c1,3)}*{mod(d1,3)}-{mod(f1,3)}} &nbsp;\\mod{3} \\\\<br/>&amp;\\equiv \\var{ans13} \\mod{3}<br/>\\end{align}</p>\n<p>In the second row, you just have to work out the remainder when dividing $\\var{a2}$ by each of $3$, $5$, $7$ and $11$.</p>\n<p>In the third row we have to find the inverse of $\\var{b3}$ in each of $\\mathbb{Z}_{3}$, $\\mathbb{Z}_{5}$, $\\mathbb{Z}_{7}$ and $\\mathbb{Z}_{11}$.</p>\n<p>It should be clear to you that $\\var{b3}$ is coprime to each of $3$, $5$, $7$ and $11$, hence we can find an inverse in each of $\\mathbb{Z}_{3}$, $\\mathbb{Z}_{5}$, $\\mathbb{Z}_{7}$ and $\\mathbb{Z}_{11}$.</p>\n<p>You can do this in $\\mathbb{Z}_{3}$ by finding $x$ such that $\\var{b3}x \\equiv 1 \\bmod{3}$, similarly for $5$, $7$, $11$.</p>\n<p>You can do this by trying values to find one that works; this is easy for $\\mathbb{Z}_{3}$ since there are only two cases to check, and you will find that</p>\n<p>$b = \\var{inv3}$ satisfies $\\var{inv3} \\times \\var{b3} = \\var{inv3*b3} \\equiv 1 \\bmod{3}.$</p>\n<h4>Inverse in $\\mathbb{Z}_{5}$</h4>\n<p>If you cannot immediately find an inverse in $\\mathbb{Z}_{5}$, you can use the Euclidean algorithm to find $a$ and $b$ such that</p>\n<p>\\[\\var{b3}b +5a = \\operatorname{gcd}(\\var{b3},5) = 1\\]</p>\n<p>as $\\var{b3}$ and $5$ are coprime.</p>\n<p>It follows that $\\var{b3}b \\equiv 1 \\bmod{5}$, and hence $b \\bmod{5}$ is the inverse of $\\var{b3}$ in $\\mathbb{Z}_{5}$.</p>\n<p>Using the Euclidean algorithm I find that</p>\n<p>\\[\\simplify[!basic]{ {max(5,b3)}*{p5} + {min(5,b3)}*{q5} = 1 }.\\]</p>\n<p>Hence the inverse is</p>\n<p>\\[ b = \\var{rinv5} \\equiv \\var{inv5} \\bmod{5}.\\]</p>\n<h4>Inverse in $\\mathbb{Z}_{7}$</h4>\n<p>Once again if you cannot spot the solution:</p>\n<p>Using the Euclidean algorithm I find that</p>\n<p>\\[\\simplify[!basic]{ {max(7,b3)}*{p7} + {min(7,b3)}*{q7} = 1 }.\\]</p>\n<p>Hence the inverse of $\\var{b3}$ in $\\mathbb{Z}_{7}$ is</p>\n<p>\\[b = \\var{rinv7} \\equiv \\var{inv7} \\bmod{7}.\\]</p>\n<h4>Inverse in $\\mathbb{Z}_{11}$</h4>\n<p>Using the Euclidean algorithm I find that</p>\n<p>\\[\\simplify[!basic]{ {max(11,b3)}*{p11} + {min(11,b3)}*{q11} = 1}. \\]</p>\n<p>Hence the inverse of $\\var{b3}$ in $\\mathbb{Z}_{11}$ is</p>\n<p>\\[ b = \\var{rinv11} \\equiv \\var{inv11} \\bmod{11}.\\]</p>\n<h4>Last Question</h4>\n<p>The last question's answers are found by, for example in $\\mathbb{Z}_{7}$, considering (all $\\bmod 7$)</p>\n<p>\\[\\frac{\\var{c3}}{\\var{b3}} = \\var{c3} \\times \\frac{1}{\\var{b3}} \\equiv \\var{c3} \\times \\var{inv7} \\equiv \\var{c3*inv7} \\equiv \\var{minv7} \\bmod{7}.\\]</p>", "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}