// Numbas version: exam_results_page_options {"name": "Blathnaid's copy of 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": [{"preamble": {"js": "", "css": ""}, "ungrouped_variables": [], "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.
", "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)$.
", "licence": "Creative Commons Attribution 4.0 International"}, "variables": {"multiple": {"definition": "(sval-s)/diff", "templateType": "anything", "group": "Intermediate", "description": "Multiple of diff to add to s to get a value in the range $(0,...diff-1)$
", "name": "multiple"}, "show_diff": {"definition": "random(sval+1..diff)", "templateType": "anything", "group": "Intermediate", "description": "", "name": "show_diff"}, "sval": {"definition": "mod(s,diff)", "templateType": "anything", "group": "Answers", "description": "", "name": "sval"}, "b": {"definition": "numbers[1]", "templateType": "anything", "group": "Setup", "description": "", "name": "b"}, "s": {"definition": "extendedgcd1(max(a,b),min(a,b))", "templateType": "anything", "group": "Intermediate", "description": "", "name": "s"}, "tval": {"definition": "t-multiple*a/d", "templateType": "anything", "group": "Answers", "description": "", "name": "tval"}, "g": {"definition": "random(1..20)", "templateType": "anything", "group": "Setup", "description": "GCD of a and b
", "name": "g"}, "a": {"definition": "numbers[0]", "templateType": "anything", "group": "Setup", "description": "", "name": "a"}, "d": {"definition": "gcd(a,b)", "templateType": "anything", "group": "Intermediate", "description": "", "name": "d"}, "num_lines": {"definition": "random(3..5#1)", "templateType": "randrange", "group": "Setup", "description": "Number of lines in the Euclidean algorithm for a and b.
", "name": "num_lines"}, "t": {"definition": "extendedgcd2(max(a,b),min(a,b))", "templateType": "anything", "group": "Intermediate", "description": "", "name": "t"}, "diff": {"definition": "b/d", "templateType": "anything", "group": "Intermediate", "description": "", "name": "diff"}, "numbers": {"definition": "long_gcd(g*random(2..10),g,num_lines)", "templateType": "anything", "group": "Setup", "description": "", "name": "numbers"}}, "parts": [{"gaps": [{"maxValue": "d", "variableReplacementStrategy": "originalfirst", "allowFractions": false, "variableReplacements": [], "type": "numberentry", "scripts": {}, "showCorrectAnswer": true, "marks": 1, "correctAnswerFraction": false, "showPrecisionHint": false, "minValue": "d"}], "variableReplacementStrategy": "originalfirst", "prompt": "Find $d = \\operatorname{gcd}(\\var{a},\\var{b})$, the greatest common divisor of $\\var{a}$ and $\\var{b}$:
\n$d = $ [[0]]
", "scripts": {}, "variableReplacements": [], "marks": 0, "type": "gapfill", "showCorrectAnswer": true}, {"stepsPenalty": 0, "variableReplacementStrategy": "originalfirst", "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$.
", "steps": [{"variableReplacementStrategy": "originalfirst", "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}
You 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": {}, "variableReplacements": [], "marks": 0, "type": "information", "showCorrectAnswer": true}], "scripts": {}, "variableReplacements": [], "marks": 0, "type": "gapfill", "showCorrectAnswer": true, "gaps": [{"maxValue": "sval", "variableReplacementStrategy": "originalfirst", "allowFractions": false, "variableReplacements": [], "type": "numberentry", "scripts": {}, "showCorrectAnswer": true, "marks": 1, "correctAnswerFraction": false, "showPrecisionHint": false, "minValue": "sval"}, {"maxValue": "tval", "variableReplacementStrategy": "originalfirst", "allowFractions": false, "variableReplacements": [], "type": "numberentry", "scripts": {}, "showCorrectAnswer": true, "marks": 1, "correctAnswerFraction": false, "showPrecisionHint": false, "minValue": "tval"}]}], "question_groups": [{"pickQuestions": 0, "pickingStrategy": "all-ordered", "questions": [], "name": ""}], "name": "Blathnaid's copy of Use B\u00e9zout's algorithm to solve $as + bt = \\gcd(a,b)$,", "showQuestionGroupNames": false, "functions": {"extendedgcd1": {"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"]], "language": "jme", "type": "number"}, "describebezout": {"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"]], "language": "javascript", "type": "html"}, "extendedgcd2": {"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"]], "language": "jme", "type": "number"}, "describegcd": {"definition": "// describe the steps of the Euclidean algorithm\nvar table = $('
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)+'},$ |
Finally, $\\\\var{'+b+'}$ divides into $\\\\var{'+a+'}$ exactly $\\\\var{'+a/b+'}$ times: | $\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+a/b+'}.$ |