// Numbas version: exam_results_page_options
{"name": "John's copy of 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": [{"variablesTest": {"maxRuns": 100, "condition": ""}, "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"], "name": "John's copy of Simplify integers and rationals in Z_n", "variables": {"q3": {"templateType": "anything", "description": "", "definition": "extendedgcd2(max(3,b3),min(3,b3))", "group": "Ungrouped variables", "name": "q3"}, "a1": {"templateType": "anything", "description": "", "definition": "s1*random(3..9)", "group": "Ungrouped variables", "name": "a1"}, "d1": {"templateType": "anything", "description": "", "definition": "random(4..9)", "group": "Ungrouped variables", "name": "d1"}, "p7": {"templateType": "anything", "description": "", "definition": "extendedgcd1(max(7,b3),min(7,b3))", "group": "Ungrouped variables", "name": "p7"}, "c3": {"templateType": "anything", "description": "", "definition": "random(17,19,23,29,31,37,41,43,47)", "group": "Ungrouped variables", "name": "c3"}, "p11": {"templateType": "anything", "description": "", "definition": "extendedgcd1(max(11,b3),min(11,b3))", "group": "Ungrouped variables", "name": "p11"}, "rinv11": {"templateType": "anything", "description": "", "definition": "if(b3<11,q11,p11)", "group": "Ungrouped variables", "name": "rinv11"}, "s2": {"templateType": "anything", "description": "", "definition": "if(s1=1,-1,1)", "group": "Ungrouped variables", "name": "s2"}, "ans13": {"templateType": "anything", "description": "", "definition": "makepos(ans1,3)", "group": "Ungrouped variables", "name": "ans13"}, "b3": {"templateType": "anything", "description": "", "definition": "random(2,4,8,13,16,17)", "group": "Ungrouped variables", "name": "b3"}, "inv5": {"templateType": "anything", "description": "", "definition": "makepos(rinv5, 5)", "group": "Ungrouped variables", "name": "inv5"}, "rinv5": {"templateType": "anything", "description": "", "definition": "if(b3<5,q5,p5)", "group": "Ungrouped variables", "name": "rinv5"}, "minv7": {"templateType": "anything", "description": "", "definition": "mod(c3*inv7,7)", "group": "Ungrouped variables", "name": "minv7"}, "minv11": {"templateType": "anything", "description": "", "definition": "mod(c3*inv11,11)", "group": "Ungrouped variables", "name": "minv11"}, "minv3": {"templateType": "anything", "description": "", "definition": "mod(c3*inv3,3)", "group": "Ungrouped variables", "name": "minv3"}, "ans17": {"templateType": "anything", "description": "", "definition": "makepos(ans1,7)", "group": "Ungrouped variables", "name": "ans17"}, "inv7": {"templateType": "anything", "description": "", "definition": "makepos(rinv7, 7)", "group": "Ungrouped variables", "name": "inv7"}, "ans23": {"templateType": "anything", "description": "", "definition": "mod(a2,3)", "group": "Ungrouped variables", "name": "ans23"}, "minv5": {"templateType": "anything", "description": "", "definition": "mod(c3*inv5,5)", "group": "Ungrouped variables", "name": "minv5"}, "a2": {"templateType": "anything", "description": "", "definition": "random(19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97)", "group": "Ungrouped variables", "name": "a2"}, "s1": {"templateType": "anything", "description": "", "definition": "random(1,-1)", "group": "Ungrouped variables", "name": "s1"}, "inv11": {"templateType": "anything", "description": "", "definition": "makepos(rinv11, 11)", "group": "Ungrouped variables", "name": "inv11"}, "ans111": {"templateType": "anything", "description": "", "definition": "makepos(ans1,11)", "group": "Ungrouped variables", "name": "ans111"}, "rinv3": {"templateType": "anything", "description": "", "definition": "if(b3<3,q3,p3)", "group": "Ungrouped variables", "name": "rinv3"}, "ans27": {"templateType": "anything", "description": "", "definition": "mod(a2,7)", "group": "Ungrouped variables", "name": "ans27"}, "p3": {"templateType": "anything", "description": "", "definition": "extendedgcd1(max(3,b3),min(3,b3))", "group": "Ungrouped variables", "name": "p3"}, "q7": {"templateType": "anything", "description": "", "definition": "extendedgcd2(max(7,b3),min(7,b3))", "group": "Ungrouped variables", "name": "q7"}, "p5": {"templateType": "anything", "description": "", "definition": "extendedgcd1(max(5,b3),min(5,b3))", "group": "Ungrouped variables", "name": "p5"}, "f1": {"templateType": "anything", "description": "", "definition": "random(2..9)", "group": "Ungrouped variables", "name": "f1"}, "q5": {"templateType": "anything", "description": "", "definition": "extendedgcd2(max(5,b3),min(5,b3))", "group": "Ungrouped variables", "name": "q5"}, "ans211": {"templateType": "anything", "description": "", "definition": "mod(a2,11)", "group": "Ungrouped variables", "name": "ans211"}, "c1": {"templateType": "anything", "description": "", "definition": "random(4..9)", "group": "Ungrouped variables", "name": "c1"}, "inv3": {"templateType": "anything", "description": "", "definition": "makepos( rinv3, 3)", "group": "Ungrouped variables", "name": "inv3"}, "ans25": {"templateType": "anything", "description": "", "definition": "mod(a2,5)", "group": "Ungrouped variables", "name": "ans25"}, "rinv7": {"templateType": "anything", "description": "", "definition": "if(b3<7,q7,p7)", "group": "Ungrouped variables", "name": "rinv7"}, "ans15": {"templateType": "anything", "description": "", "definition": "makepos(ans1,5)", "group": "Ungrouped variables", "name": "ans15"}, "b1": {"templateType": "anything", "description": "", "definition": "s2*random(3..4)", "group": "Ungrouped variables", "name": "b1"}, "ans1": {"templateType": "anything", "description": "", "definition": "a1*b1 + c1*d1 - f1", "group": "Ungrouped variables", "name": "ans1"}, "q11": {"templateType": "anything", "description": "", "definition": "extendedgcd2(max(11,b3),min(11,b3))", "group": "Ungrouped variables", "name": "q11"}}, "variable_groups": [], "parts": [{"showCorrectAnswer": true, "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>", "type": "gapfill", "scripts": {}, "gaps": [{"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans13}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans13}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans15}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans15}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans17}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans17}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans111}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans111}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans23}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans23}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans25}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans25}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans27}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans27}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{ans211}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{ans211}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{inv3}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{inv3}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{inv5}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{inv5}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{inv7}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{inv7}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{inv11}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{inv11}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{minv3}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{minv3}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{minv5}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{minv5}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{minv7}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{minv7}"}, {"correctAnswerFraction": false, "showCorrectAnswer": true, "allowFractions": false, "maxValue": "{minv11}", "type": "numberentry", "showPrecisionHint": false, "scripts": {}, "marks": 0.25, "minValue": "{minv11}"}], "marks": 0}], "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>", "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>", "preamble": {"css": "", "js": ""}, "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "tags": ["checked2015", "MAS3214"], "type": "question", "functions": {"makepos": {"type": "number", "parameters": [["a", "number"], ["b", "number"]], "definition": "mod(a,b)", "language": "jme"}, "extendedgcd2": {"type": "number", "parameters": [["a", "number"], ["b", "number"]], "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", "language": "jme"}, "extendedgcd1": {"type": "number", "parameters": [["a", "number"], ["b", "number"]], "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n\n", "language": "jme"}}, "question_groups": [{"questions": [], "pickingStrategy": "all-ordered", "name": "", "pickQuestions": 0}], "showQuestionGroupNames": false, "metadata": {"description": "<p>Express various integers and rationals mod $\\mathbb{Z}_3, \\;\\mathbb{Z}_5,\\;\\mathbb{Z}_7,\\;\\mathbb{Z}_{11}$</p>", "licence": "Creative Commons Attribution 4.0 International", "notes": ""}, "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}, {"name": "John Moss", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3481/"}]}]}], "contributors": [{"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}, {"name": "John Moss", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/3481/"}]}