// Numbas version: finer_feedback_settings
{"name": "Greatest common divisor and congruences", "navigation": {"onleave": {"action": "none", "message": ""}, "reverse": true, "allowregen": true, "preventleave": false, "browse": true, "showfrontpage": false, "showresultspage": "never"}, "duration": 0.0, "metadata": {"notes": "", "description": "", "licence": null}, "timing": {"timeout": {"action": "none", "message": ""}, "timedwarning": {"action": "none", "message": ""}}, "shufflequestions": false, "questions": [], "percentpass": 50.0, "allQuestions": true, "pickQuestions": 0, "type": "exam", "feedback": {"showtotalmark": true, "advicethreshold": 0.0, "showanswerstate": true, "showactualmark": true, "allowrevealanswer": true, "enterreviewmodeimmediately": false, "showexpectedanswerswhen": "never", "showpartfeedbackmessageswhen": "always", "showactualmarkwhen": "always", "showtotalmarkwhen": "always", "showanswerstatewhen": "always", "showadvicewhen": "never"}, "showQuestionGroupNames": false, "question_groups": [{"name": "", "pickingStrategy": "all-ordered", "pickQuestions": 0, "questions": [{"name": "Greatest common divisor and B\u00e9zout's algorithm", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}], "ungrouped_variables": ["s", "diff", "b1", "b", "n", "t", "a1", "bb", "c", "describeleast", "a", "least", "d", "k"], "variable_groups": [], "preamble": {"css": "", "js": ""}, "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Given two numbers, find the gcd, then use B&eacute;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$.</p>"}, "statement": "", "tags": ["euclidean algorithm", "gcd", "greatest common divisor", "Number theory", "number theory"], "parts": [{"type": "gapfill", "variableReplacements": [], "prompt": "\n\n\n<p>Find $d = \\operatorname{gcd}(\\var{a},\\var{b})$, the greatest common divisor of $\\var{a}$ and $\\var{b}$:</p>\n\n\n\n<p>$d = \\phantom{{}}$[[0]]</p>\n\n\n\n<p>Now find integers $s$ and $t$ such that:</p>\n\n\n\n<p>\\[\\var{a}s+\\var{b}t = d\\]</p>\n\n\n\n<p>$s = \\phantom{{}}$[[1]] $, t = \\phantom{{}}$[[2]]$.$</p>\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<p>Find all solutions $x$ of the following congruence:</p>\n\n\n\n<p>\\[\\var{a}x \\equiv \\var{n} \\mod \\var{b} \\]</p>\n\n\n\n<p>The least solution $x$ such that $0 \\lt x \\lt \\var{b}$ is: [[0]]</p>\n\n\n\n<p>What is the difference between two successive solutions? [[1]]</p>\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": "<h4>a)</h4>\n<p>On applying the standard method for finding the $\\operatorname{gcd}$ of two numbers we have the following sequence:</p>\n<p>{describegcd(a,b)}</p>\n<p>The last non-zero remainder is $\\var{d}$, so this is the $\\operatorname{gcd}$ of $\\var{a}$ and $\\var{b}$.</p>\n<p>Now work backwards through those steps, rearranging them to find the remainders as linear combinations of the other numbers.</p>\n<p>When you reach the last line you will have found $s$ and $t$ such that <br/>\\[\\var{a}s+\\var{b}t = \\var{d}\\]</p>\n<p>{describebezout(a,b)}</p>\n<p>So $s = \\var{s}$ and $t = \\var{t}$.</p>\n<hr/>\n<h4>b)</h4>\n<h3 style=\"text-align: center;\">First Step</h3>\n<p>We would like to find all the solutions $x$ of the equation<br/>\\[\\var{a}x \\equiv \\var{n} \\mod \\var{b}.\\]</p>\n<p>In order to solve such an equation first determine if there is a solution at all.</p>\n<hr/>\n<h5>Lemma</h5>\n<p>An equation of the form $ax \\equiv n \\mod b$ has a solution if and only if $\\operatorname{gcd}(a,b)|n$.</p>\n<hr/>\n<p>So the first task is to find $\\operatorname{gcd}(a,b)$ and see if it divides $n$. If not, there is no solution.</p>\n<p>In the first part, we found that $d = \\operatorname{gcd}(\\var{a},\\var{b}) = \\var{d}$.</p>\n<p>$\\var{n} = \\var{d} \\times \\var{k}$, so the equation $\\var{a}x \\equiv \\var{n} \\mod \\var{b}$ has a solution.</p>\n<h3 style=\"text-align: center;\">Finding a solution</h3>\n<p>Note that because $d|n$, then $n=kd$ for some integer $k$.</p>\n<p>In order to find a solution of $x$ go back to the first part and use the integers $s$ and $t$ such that</p>\n<p>\\[ \\var{a}s + \\var{b}t = d. \\]</p>\n<p>If we multiply both sides of this equation by $k$ we find that</p>\n<p>\\[ \\var{a}ks + \\var{b}kt = kd = n, \\]</p>\n<p>and by taking both sides modulo $\\var{b}$ we see that</p>\n<p>\\[ \\var{a}ks \\equiv n \\mod \\var{b}. \\]</p>\n<p>So $x = ks = \\var{k*s}$ is a solution of the equation.</p>\n<p>The difference between successive terms is $\\frac{\\var{b}}{\\var{d}} = \\var{diff}$.</p>\n<p>{describeLeast}</p>", "variablesTest": {"maxRuns": 100, "condition": ""}, "rulesets": {}, "functions": {"describebezout": {"type": "html", "parameters": [["a", "number"], ["b", "number"]], "definition": "var list = $('<ol>');\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('<li>$'+old_r+' = '+expr+'$</li>');\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 = $('<table>');\nfunction describegcd(a,b) {\nif(a<b) {\ntable.append('<tr><td style=\"text-align:left;\"> First of all, the biggest number needs to go first: </td><td> $\\\\operatorname{gcd}(\\\\var{'+a+'},\\\\var{'+b+'}) = \\\\operatorname{gcd}(\\\\var{'+b+'},\\\\var{'+a+'}), $ </td></tr>');\nreturn describegcd(b,a);\n}\n\nif(a%b==0) {\ntable.append('<tr><td style=\"text-align:left;\"> Finally, $\\\\var{'+b+'}$ divides into $\\\\var{'+a+'}$ exactly $\\\\var{'+a/b+'}$ times: </td><td> $\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+a/b+'}.$ </td></tr>');\n}\nelse {\ntable.append('<tr><td style=\"text-align:left;\"> Divide $\\\\var{'+a+'}$ by $\\\\var{'+b+'}$ with remainder $\\\\var{'+(a%b)+'}$: </td><td> $\\\\var{'+a+'} = \\\\var{'+b+'} \\\\times \\\\var{'+Math.floor(a/b)+'} + \\\\var{'+(a%b)+'},$ </td></tr>');\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/"}], "extensions": [], "custom_part_types": [], "resources": []}