// Numbas version: finer_feedback_settings {"name": "Solve linear equations in the rationals and 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": {"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}], "name": "Solve linear equations in the rationals and Z_n", "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}}$.

", "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/"}]}

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)+'},$