// Numbas version: finer_feedback_settings
{"name": "Find all solutions of a quadratic in Z_n, given one", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"variable_groups": [], "variables": {"q": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(p=11,2,random(2,3))", "description": "", "name": "q"}, "b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(a+p-m*q>=0,mod(a+p-m*q,n),n+mod(a+p-m*q,n))", "description": "", "name": "b"}, "c": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a+b,n)", "description": "", "name": "c"}, "b1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(a-m*q>=0,mod(a-m*q,n),n+mod(a-m*q,n))", "description": "", "name": "b1"}, "b2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "max(a1,b1)", "description": "", "name": "b2"}, "a1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a+p,n)", "description": "", "name": "a1"}, "a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(ar=p or ar=q, ar+1, ar)", "description": "", "name": "a"}, "m1": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1..2)", "description": "", "name": "m1"}, "ans": {"templateType": "anything", "group": "Ungrouped variables", "definition": "sort([b,a2,b2])", "description": "", "name": "ans"}, "n": {"templateType": "anything", "group": "Ungrouped variables", "definition": "p*q", "description": "", "name": "n"}, "ar": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(round(n/2)..n-1)", "description": "", "name": "ar"}, "d": {"templateType": "anything", "group": "Ungrouped variables", "definition": "mod(a*b,n)", "description": "", "name": "d"}, "p": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(5,7,11)", "description": "", "name": "p"}, "a2": {"templateType": "anything", "group": "Ungrouped variables", "definition": "min(a1,b1)", "description": "", "name": "a2"}, "m": {"templateType": "anything", "group": "Ungrouped variables", "definition": "if(mod(a+p-m1*q,n)=0,m1+1,m1)", "description": "", "name": "m"}}, "ungrouped_variables": ["a", "a1", "a2", "ans", "ar", "b", "b1", "b2", "c", "d", "m", "m1", "n", "p", "q"], "question_groups": [{"pickingStrategy": "all-ordered", "questions": [], "name": "", "pickQuestions": 0}], "name": "Find all solutions of a quadratic in Z_n, given one", "functions": {}, "showQuestionGroupNames": false, "parts": [{"scripts": {}, "gaps": [{"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans[0]}", "minValue": "{ans[0]}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans[1]}", "minValue": "{ans[1]}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}, {"showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "maxValue": "{ans[2]}", "minValue": "{ans[2]}", "correctAnswerFraction": false, "marks": 1, "showPrecisionHint": false}], "type": "gapfill", "prompt": "Enter the three other roots in increasing order below:
\n $x_2 = \\;$ [[0]]
\n $x_3 = \\;$ [[1]]
\n $x_4 = \\;$ [[2]]
", "showCorrectAnswer": true, "marks": 0}], "statement": "$x = x_1 = \\var{a}$ is a solution of this quadratic equation in $\\mathbb{Z}_{\\var{n}}$:
\n\\[\\simplify[std]{x^2 -{c}x+{d} = 0}\\]
\nThere are three other solutions $x_2$, $x_3$, $x_4$ in $\\mathbb{Z}_{\\var{n}}$ of this quadratic equation, where $0\\le x_2 \\lt x_3 \\lt x_4 \\le \\var{n-1}$ .
", "tags": ["checked2015", "MAS3214"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "preamble": {"css": "", "js": ""}, "type": "question", "metadata": {"notes": "", "licence": "Creative Commons Attribution 4.0 International", "description": "Given one solution of the quadratic equation in $\\mathbb{Z}_n$ where $n=pq$ is a product of two primes find the other 3 solutions.
"}, "variablesTest": {"condition": "", "maxRuns": 100}, "advice": "Putting $x=\\var{a}$ gives:
\n\\begin{align}
\\simplify[std]{x^2 -{c}x+{d}} & = \\simplify[std]{{a}^2-{c}*{a} + {d}} \\\\
&= \\simplify[std]{{a^2-c*a+d}} \\\\
& \\equiv 0 \\bmod{\\var{n}}
\\end{align}
\nHence $x=\\var{a}$ is a solution of the quadratic equation in $\\mathbb{Z}_{\\var{n}}$.
\nWe can use this to factorize the quadratic equation, giving $b$, which will also be a solution, such that:
\n\\[ \\simplify[std]{x^2 -{c}x+{d}} = (x-\\var{a})(x-b) \\]
\nWe see that $b$ has to satisfy:
\n\\begin{align}
\\var{a} b & \\equiv \\var{d} \\bmod{\\var{n}}, \\\\
\\var{a} + b & \\equiv \\var{c} \\bmod{\\var{n}}.
\\end{align}
\nBy rearranging the second equation, we see that $b = \\simplify[std]{{c}-{a}} =\\var{c-a} \\equiv \\var{b} \\bmod{\\var{n}}$ satisfies the second equation. You can check that it also satisfies the first equation.
\nSo $\\simplify[std]{x^2 -{c}x+{d} = (x-{a})(x-{b})}$ expresses the quadratic as the product of two factors and we have found another solution $x=\\var{b}$.
\nBut there are two other roots.
\nThe strategy is to try values of $x$ such that substituting a value of $x$ in one of the factors gives a multiple of $\\var{p}$, and substituting the same value into the other factor gives a multiple of $\\var{q}$.
\nTogether they give a multiple of $\\var{n} = \\var{p} \\times \\var{q} = 0 \\bmod{\\var{n}}$ and so will give a solution in $\\mathbb{Z}_{\\var{n}}$.
\nWe see that trying $x = \\var{a1}$ gives
\n\\[ \\simplify[std]{(x-{a})(x-{b}) = ({a1}-{a})({a1}-{b}) = {a1-a}*{a1-b} = {(a1-a)(a1-b)}} \\equiv 0 \\bmod{\\var{n}}. \\]
\nFor the other we see that trying $x = \\var{b1}$ gives
\n\\[ \\simplify[std]{(x-{a})(x-{b}) = ({b1}-{a})({b1}-{b}) = {b1-a}*{b1-b} = {(b1-a)(b1-b)}} \\equiv 0 \\bmod{\\var{n}}. \\]
\nHence, apart from the solution $x = \\var{a}$, the other solutions are, in increasing order: $\\var{ans[0]}$, $\\var{ans[1]}$, $\\var{ans[2]}$.
\nHence $x_2 = \\var{ans[0]}$, $x_3 = \\var{ans[1]}$, $x_4 = \\var{ans[2]}$.
", "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/"}]}