// 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');\n var t = a;\n a = b;\n b = t;\n } else {\n table.append('');\n var t = a;\n a = b\n b = t%b;\n }\n}\ntable.append('');\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]]

\n

Click 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}

\n

You have to find the appropriate value of $\\lambda$ if the requirement is not met.

\n

You 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)

\n

On applying the standard method for finding the $\\operatorname{gcd}$ of two numbers we have the following sequence of operations:

\n

{describegcd(a,b)}

\n

The last non-zero remainder is $\\var{d}$, so this is the $\\operatorname{gcd}$ of $\\var{a}$ and $\\var{b}$.

\n

b)

\n

Now work backwards through those steps, rearranging them to find the remainders as linear combinations of the other numbers.

\n

When 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}\\]

\n

In this case we find:

\n

{describebezout(a,b)}

\n

So 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/"}]}
First of all, the biggest number needs to go first: $\\\\operatorname{gcd}(\\\\var{'+a+'},\\\\var{'+b+'}) = \\\\operatorname{gcd}(\\\\var{'+b+'},\\\\var{'+a+'}), $
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+'}.$