// Numbas version: finer_feedback_settings
{"name": "Blathnaid's copy of Apply extended Euclidean algorithm to find gcd", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"tags": [], "parts": [{"variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "scripts": {}, "variableReplacements": [], "prompt": "<p>Find $d$, using the Euclidean algorithm.</p>\n<p>$d=$ [[0]]</p>", "type": "gapfill", "marks": 0, "showFeedbackIcon": true, "gaps": [{"correctAnswerFraction": false, "variableReplacementStrategy": "originalfirst", "integerPartialCredit": 0, "minValue": "{hcf}", "variableReplacements": [], "marks": "10", "maxValue": "{hcf}", "notationStyles": ["plain", "en", "si-en"], "integerAnswer": true, "showCorrectAnswer": true, "allowFractions": false, "scripts": {"mark": {"script": "this.__proto__.mark.apply(this);\n", "order": "instead"}}, "type": "numberentry", "showFeedbackIcon": true, "correctAnswerStyle": "plain"}]}, {"variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "scripts": {"mark": {"script": "this.setCredit(0);\nthis.markingFeedback = [];\n\nvar x = parseFloat(this.gaps[0].studentAnswer);\nvar y = parseFloat(this.gaps[1].studentAnswer);\nvar total = variables.sa*x + variables.sb*y;\nif(total==variables.hcf) {\n  this.setCredit(1,'Your answer is correct');\n  this.gaps[0].settings.minvalue = this.gaps[0].settings.maxvalue = x;\n  this.gaps[1].settings.minvalue = this.gaps[1].settings.maxvalue = y;\n} else {\n  this.setCredit(0,'Your values of $x$ and $y$ give $\\\\simplify[]{{sa}'+x+' + {sb}'+y+'} = '+total+' \\\\neq h$');\n  this.gaps[0].settings.minvalue = this.gaps[0].settings.maxvalue = x+1;\n  this.gaps[1].settings.minvalue = this.gaps[1].settings.maxvalue = y+1;\n}\nthis.gaps[0].submit();\nthis.gaps[1].submit();", "order": "instead"}}, "variableReplacements": [], "prompt": "<p>Find integers $x$ and $y$ such that $\\simplify{d={sa}*x+{sb}*y }$.</p>\n<p>$x=$ [[0]]</p>\n<p>$y=$ [[1]]</p>\n<p>If you use the extended Euclidean Algorithm, or, essentially equivalently, work backwards from the solution you found in a), then you will obtain suitable values for $x$ and $y$.</p>\n<p></p>", "type": "gapfill", "marks": 0, "showFeedbackIcon": true, "gaps": [{"correctAnswerFraction": false, "variableReplacementStrategy": "originalfirst", "integerPartialCredit": 0, "minValue": "{csa}", "variableReplacements": [], "marks": "10", "maxValue": "{csa}", "notationStyles": ["plain", "en", "si-en"], "integerAnswer": true, "showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "showFeedbackIcon": true, "correctAnswerStyle": "plain"}, {"correctAnswerFraction": false, "variableReplacementStrategy": "originalfirst", "integerPartialCredit": 0, "minValue": "{csb}", "variableReplacements": [], "marks": "10", "maxValue": "{csb}", "notationStyles": ["plain", "en", "si-en"], "integerAnswer": true, "showCorrectAnswer": true, "allowFractions": false, "scripts": {}, "type": "numberentry", "showFeedbackIcon": true, "correctAnswerStyle": "plain"}]}], "variables": {"bsb": {"name": "bsb", "group": "Ungrouped variables", "templateType": "anything", "definition": "round(sa/hcf)", "description": ""}, "ub": {"name": "ub", "group": "Ungrouped variables", "templateType": "anything", "definition": "random(l1b..l2b)", "description": ""}, "l2b": {"name": "l2b", "group": "Ungrouped variables", "templateType": "anything", "definition": "floor(3*bsb/4)", "description": ""}, "l1a": {"name": "l1a", "group": "Ungrouped variables", "templateType": "anything", "definition": "floor(bsa/4)", "description": ""}, "csb": {"name": "csb", "group": "Ungrouped variables", "templateType": "anything", "definition": "extendedgcd2(sa,sb)", "description": ""}, "l1b": {"name": "l1b", "group": "Ungrouped variables", "templateType": "anything", "definition": "floor(bsb/4)", "description": ""}, "l2a": {"name": "l2a", "group": "Ungrouped variables", "templateType": "anything", "definition": "floor(3*bsa/4)", "description": ""}, "csa": {"name": "csa", "group": "Ungrouped variables", "templateType": "anything", "definition": "extendedgcd1(sa,sb)", "description": ""}, "lb": {"name": "lb", "group": "Ungrouped variables", "templateType": "anything", "definition": "random(l1b..l2b)", "description": ""}, "ua": {"name": "ua", "group": "Ungrouped variables", "templateType": "anything", "definition": "random(l1a..l2a)", "description": ""}, "hcf": {"name": "hcf", "group": "Ungrouped variables", "templateType": "anything", "definition": "gcd(sa,sb)", "description": ""}, "bsa": {"name": "bsa", "group": "Ungrouped variables", "templateType": "anything", "definition": "round(sb/hcf)", "description": ""}, "sb": {"name": "sb", "group": "Ungrouped variables", "templateType": "anything", "definition": "random(201..901)", "description": ""}, "la": {"name": "la", "group": "Ungrouped variables", "templateType": "anything", "definition": "random(l1a..l2a)", "description": ""}, "sa": {"name": "sa", "group": "Ungrouped variables", "templateType": "anything", "definition": "random(1001..2001)", "description": ""}}, "statement": "<p>Let $d=\\text{gcd}(\\var{sa},\\var{sb})$.</p>", "ungrouped_variables": ["bsa", "bsb", "csa", "csb", "hcf", "l1a", "l1b", "l2a", "l2b", "la", "lb", "sa", "sb", "ua", "ub"], "extensions": [], "functions": {"mdescextgcd": {"language": "javascript", "type": "html", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]], "definition": "var table=$('<table class=\"extended-gcd\">');\nfunction disp(s){\n  return Numbas.jme.display.exprToLaTeX(s,['unitFactor','zeroFactor','zeroTerm','basic'],scope);\n}\n\nfunction mdescextgcd(a,b,c1,c2,d1,d2){\n  table.append('<tr class=\"state\"><td>$\\\\var{'+a+'}$</td><td>$\\\\var{'+b+'}$</td><td>$'+ disp(c1+'a+'+c2+'b')+'$</td><td>$'+ disp(d1+'a+'+d2+'b')+'$</td></tr>');\n  if((a%b==0) || (b%a==0)) {\n    return;\n  }\n  else {\n    if(a<b){\n      var fl=Math.floor(b/a);\n      table.append('<tr><td>$\\\\var{'+a+'}$</td><td>$\\\\var{'+b+'}-\\\\var{'+fl+'}\\\\times\\\\var{'+a+'}$</td><td>$'+ disp(c1+'a+'+c2+'b')+'$</td><td>$'+disp(d1+'a+'+d2+'b-'+fl+'('+c1+'a+'+c2+'b'+')')+'$</td></tr>');\n      mdescextgcd(a,b%a,c1,c2,d1-fl*c1,d2-fl*c2);\n    }\n    else {\n      var fl1=Math.floor(a/b);\n      table.append('<tr><td>$\\\\var{'+a+'}-\\\\var{'+fl1+'}\\\\times\\\\var{'+b+'}$</td><td>$\\\\var{'+b+'}$</td><td>$'+disp(c1+'a+'+c2+'b-'+fl1+'('+d1+'a+'+d2+'b'+')')+'$</td><td>$'+ disp(d1+'a+'+d2+'b')+'$</td></tr>');\n      mdescextgcd(a%b,b,c1-fl1*d1,c2-fl1*d2,d1,d2);}\n  }\n}\nmdescextgcd(a,b,c1,c2,d1,d2);\n\nreturn table;\n"}, "extendedgcd2": {"language": "jme", "type": "number", "parameters": [["a", "number"], ["b", "number"]], "definition": "if((a|b) or (b|a),\n  1\n,\n  extendedgcd1(b,mod(a,b))-(extendedgcd2(b,mod(a,b))*floor(a/b))\n)"}, "extendedgcd1": {"language": "jme", "type": "number", "parameters": [["a", "number"], ["b", "number"]], "definition": "if((a|b) or (b|a),\n  0\n,\n  extendedgcd2(b,mod(a,b))\n)"}}, "variable_groups": [], "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Find the gcd $d$ of two positive integers $a$ and $b$ also find integers $x,y$ such that $ax+by=d$, using the extended Euclidean algorithm.</p>"}, "advice": "<p>We use the extended Euclidean Algorithm to get:</p>\n<p>{mdescextGCD(sa,sb,1,0,0,1)}</p>\n<p>Hence $d=\\var{hcf}$ and we have</p>\n<p>\\[ x= \\var{csa}, \\quad y=\\var{csb}\\]</p>\n<p>That is,</p>\n<p>\\[ \\simplify[!basic]{{sa}*{csa}+{sb}*{csb} = {hcf}} \\]</p>", "name": "Blathnaid's copy of Apply extended Euclidean algorithm to find gcd", "variablesTest": {"maxRuns": 100, "condition": ""}, "preamble": {"css": ".extended-gcd td:nth-child(2) {\n    border-right: 1px solid black;\n}\n.extended-gcd td {\n    padding-left: 1em;\n    padding-right: 1em;\n}\n.extended-gcd tr.state:not(:last-child) td {\n    border-bottom: 1px dashed #ccc;\n}", "js": ""}, "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "type": "question", "contributors": [{"name": "Blathnaid Sheridan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/447/"}]}]}], "contributors": [{"name": "Blathnaid Sheridan", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/447/"}]}