// Numbas version: exam_results_page_options
{"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}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"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}], "name": "Use B\u00e9zout's algorithm to solve $as + bt = \\gcd(a,b)$, ", "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 = $('
');\nwhile(a%b!=0) {\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+'}), $ | ');\n var t = a;\n a = b;\n b = t;\n } else {\n table.append(' Divide $\\\\var{'+a+'}$ by $\\\\var{'+b+'}$ with remainder $\\\\var{'+(a%b)+'}$: | $\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+Math.floor(a/b)+'} + \\\\var{'+(a%b)+'},$ |
');\n var t = a;\n a = b\n b = t%b;\n }\n}\ntable.append(' Finally, $\\\\var{'+b+'}$ divides into $\\\\var{'+a+'}$ exactly $\\\\var{'+a/b+'}$ times: | $\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+a/b+'}.$ |
');\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}$:
\n$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
\n\\[\\var{a}s+\\var{b}t = d\\]
\n$s = $ [[0]]
\n$t = $ [[1]]
\nClick 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:
\n\\begin{align}
s &= s_1+\\lambda \\times \\frac{\\var{b}}{d} \\\\\\\\
t &= t_1-\\lambda \\times \\frac{\\var{a}}{d}
\\end{align}
\nYou have to find the appropriate value of $\\lambda$ if the requirement is not met.
\nYou 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)
\nOn applying the standard method for finding the $\\operatorname{gcd}$ of two numbers we have the following sequence of operations:
\n{describegcd(a,b)}
\nThe last non-zero remainder is $\\var{d}$, so this is the $\\operatorname{gcd}$ of $\\var{a}$ and $\\var{b}$.
\nb)
\nNow work backwards through those steps, rearranging them to find the remainders as linear combinations of the other numbers.
\nWhen you reach the last line you will have found $s_1$ and $t_1$ such that
\n\\[\\var{a}s_1+\\var{b}t_1= \\var{d}\\]
\nIn this case we find:
\n{describebezout(a,b)}
\nSo we obtain values $s_1 = \\var{s}$ and $t_1 = \\var{t}$.
\n\n
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}$.
\n
\n\n
We see that $s_1$ does not meet the requirement that $0 \\le s_1 \\le \\var{show_diff-1}$.
\n
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.
\n
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$.
\n
We see that the multiple is $\\var{multiple}$ and we have:
\n
\\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}
\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/"}]}