// Numbas version: exam_results_page_options {"name": "Greatest common divisor and B\u00e9zout's algorithm", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"ungrouped_variables": ["s", "diff", "b1", "b", "n", "t", "a1", "bb", "c", "describeleast", "a", "least", "d", "k"], "name": "Greatest common divisor and B\u00e9zout's algorithm", "extensions": [], "variable_groups": [], "preamble": {"css": "", "js": ""}, "metadata": {"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)$. Finally, find all solutions of an equation $\\mod b$.

"}, "statement": "", "tags": ["euclidean algorithm", "gcd", "greatest common divisor", "Number theory", "number theory"], "parts": [{"type": "gapfill", "variableReplacements": [], "prompt": "\n\n\n

Find $d = \\operatorname{gcd}(\\var{a},\\var{b})$, the greatest common divisor of $\\var{a}$ and $\\var{b}$:

\n\n\n\n

$d = \\phantom{{}}$[[0]]

\n\n\n\n

Now find integers $s$ and $t$ such that:

\n\n\n\n

\\[\\var{a}s+\\var{b}t = d\\]

\n\n\n\n

$s = \\phantom{{}}$[[1]] $, t = \\phantom{{}}$[[2]]$.$

\n\n\n ", "showCorrectAnswer": true, "variableReplacementStrategy": "originalfirst", "marks": 0, "gaps": [{"correctAnswerStyle": "plain", "type": "numberentry", "minValue": "d", "variableReplacementStrategy": "originalfirst", "mustBeReduced": false, "notationStyles": ["plain", "en", "si-en"], "maxValue": "d", "scripts": {}, "marks": 1, "variableReplacements": [], "showFeedbackIcon": true, "allowFractions": false, "showCorrectAnswer": true, "mustBeReducedPC": 0, "correctAnswerFraction": false}, {"correctAnswerStyle": "plain", "type": "numberentry", "minValue": "s", "variableReplacementStrategy": "originalfirst", "mustBeReduced": false, "notationStyles": ["plain", "en", "si-en"], "maxValue": "s", "scripts": {}, "marks": 1, "variableReplacements": [], "showFeedbackIcon": true, "allowFractions": false, "showCorrectAnswer": true, "mustBeReducedPC": 0, "correctAnswerFraction": false}, {"correctAnswerStyle": "plain", "type": "numberentry", "minValue": "t", "variableReplacementStrategy": "originalfirst", "mustBeReduced": false, "notationStyles": ["plain", "en", "si-en"], "maxValue": "t", "scripts": {}, "marks": 1, "variableReplacements": [], "showFeedbackIcon": true, "allowFractions": false, "showCorrectAnswer": true, "mustBeReducedPC": 0, "correctAnswerFraction": false}], "showFeedbackIcon": true, "scripts": {}}, {"type": "gapfill", "variableReplacements": [], "prompt": "\n\n\n

Find all solutions $x$ of the following congruence:

\n\n\n\n

\\[\\var{a}x \\equiv \\var{n} \\mod \\var{b} \\]

\n\n\n\n

The least solution $x$ such that $0 \\lt x \\lt \\var{b}$ is: [[0]]

\n\n\n\n

What is the difference between two successive solutions? [[1]]

\n\n\n ", "showCorrectAnswer": true, "variableReplacementStrategy": "originalfirst", "marks": 0, "gaps": [{"correctAnswerStyle": "plain", "type": "numberentry", "minValue": "{least}", "variableReplacementStrategy": "originalfirst", "mustBeReduced": false, "notationStyles": ["plain", "en", "si-en"], "maxValue": "{least}", "scripts": {}, "marks": 1, "variableReplacements": [], "showFeedbackIcon": true, "allowFractions": false, "showCorrectAnswer": true, "mustBeReducedPC": 0, "correctAnswerFraction": false}, {"correctAnswerStyle": "plain", "type": "numberentry", "minValue": "{diff}", "variableReplacementStrategy": "originalfirst", "mustBeReduced": false, "notationStyles": ["plain", "en", "si-en"], "maxValue": "{diff}", "scripts": {}, "marks": 1, "variableReplacements": [], "showFeedbackIcon": true, "allowFractions": false, "showCorrectAnswer": true, "mustBeReducedPC": 0, "correctAnswerFraction": false}], "showFeedbackIcon": true, "scripts": {}}], "advice": "

a)

\n

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

\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

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$ and $t$ such that
\\[\\var{a}s+\\var{b}t = \\var{d}\\]

\n

{describebezout(a,b)}

\n

So $s = \\var{s}$ and $t = \\var{t}$.

\n
\n

b)

\n

First Step

\n

We would like to find all the solutions $x$ of the equation
\\[\\var{a}x \\equiv \\var{n} \\mod \\var{b}.\\]

\n

In order to solve such an equation first determine if there is a solution at all.

\n
\n
Lemma
\n

An equation of the form $ax \\equiv n \\mod b$ has a solution if and only if $\\operatorname{gcd}(a,b)|n$.

\n
\n

So the first task is to find $\\operatorname{gcd}(a,b)$ and see if it divides $n$. If not, there is no solution.

\n

In the first part, we found that $d = \\operatorname{gcd}(\\var{a},\\var{b}) = \\var{d}$.

\n

$\\var{n} = \\var{d} \\times \\var{k}$, so the equation $\\var{a}x \\equiv \\var{n} \\mod \\var{b}$ has a solution.

\n

Finding a solution

\n

Note that because $d|n$, then $n=kd$ for some integer $k$.

\n

In order to find a solution of $x$ go back to the first part and use the integers $s$ and $t$ such that

\n

\\[ \\var{a}s + \\var{b}t = d. \\]

\n

If we multiply both sides of this equation by $k$ we find that

\n

\\[ \\var{a}ks + \\var{b}kt = kd = n, \\]

\n

and by taking both sides modulo $\\var{b}$ we see that

\n

\\[ \\var{a}ks \\equiv n \\mod \\var{b}. \\]

\n

So $x = ks = \\var{k*s}$ is a solution of the equation.

\n

The difference between successive terms is $\\frac{\\var{b}}{\\var{d}} = \\var{diff}$.

\n

{describeLeast}

", "variablesTest": {"maxRuns": 100, "condition": ""}, "rulesets": {}, "functions": {"describebezout": {"type": "html", "parameters": [["a", "number"], ["b", "number"]], "definition": "var list = $('
    ');\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 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 list.append('
  1. $'+old_r+' = '+expr+'$
  2. ');\n}\nreturn list;", "language": "javascript"}, "extendedgcd1": {"type": "number", "parameters": [["a", "number"], ["b", "number"]], "definition": "\n\n\nif((a|b) or (b|a),\n\n0\n\n,\n\nextendedgcd2(b,mod(a,b))\n\n)\n\n\n ", "language": "jme"}, "describegcd": {"type": "html", "parameters": [["a", "number"], ["b", "number"]], "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;", "language": "javascript"}, "extendedgcd2": {"type": "number", "parameters": [["a", "number"], ["b", "number"]], "definition": "\n\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\n ", "language": "jme"}, "randompow": {"type": "number", "parameters": [["n", "number"]], "definition": "\n\n\nif(n>0,\n\nrandom(2,3,5,7,11,13,17,19,23)*randompow(n-1),\n\n1)\n\n\n ", "language": "jme"}}, "variables": {"t": {"templateType": "anything", "name": "t", "group": "Ungrouped variables", "definition": "extendedgcd2(max(a,b),min(a,b))", "description": ""}, "a1": {"templateType": "anything", "name": "a1", "group": "Ungrouped variables", "definition": "randompow(3)*c", "description": ""}, "bb": {"templateType": "anything", "name": "bb", "group": "Ungrouped variables", "definition": "randompow(3)*c", "description": ""}, "b1": {"templateType": "anything", "name": "b1", "group": "Ungrouped variables", "definition": "if(bb=a1,bb*randompow(2),bb)", "description": ""}, "d": {"templateType": "anything", "name": "d", "group": "Ungrouped variables", "definition": "gcd(a,b)", "description": ""}, "s": {"templateType": "anything", "name": "s", "group": "Ungrouped variables", "definition": "extendedgcd1(max(a,b),min(a,b))", "description": ""}, "c": {"templateType": "anything", "name": "c", "group": "Ungrouped variables", "definition": "random(5..29)", "description": ""}, "b": {"templateType": "anything", "name": "b", "group": "Ungrouped variables", "definition": "min(a1,b1)", "description": ""}, "k": {"templateType": "anything", "name": "k", "group": "Ungrouped variables", "definition": "random(2..7)", "description": ""}, "describeleast": {"templateType": "anything", "name": "describeleast", "group": "Ungrouped variables", "definition": "if(s<0,'So, the first positive solution is \\\\[ x = \\\\simplify[]{{k*s} + {diff}*{ceil(-k*s/diff)} } = \\\\var{least}.\\\\]','')", "description": ""}, "least": {"templateType": "anything", "name": "least", "group": "Ungrouped variables", "definition": "k*s+diff*ceil(-k*s/diff)", "description": ""}, "n": {"templateType": "anything", "name": "n", "group": "Ungrouped variables", "definition": "k*d", "description": ""}, "diff": {"templateType": "anything", "name": "diff", "group": "Ungrouped variables", "definition": "b/d", "description": ""}, "a": {"templateType": "anything", "name": "a", "group": "Ungrouped variables", "definition": "max(a1,b1)", "description": ""}}, "type": "question", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}]}
    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)+'},$