// Numbas version: exam_results_page_options
{"name": "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": [{"parts": [{"prompt": "<p>Find $h$</p>\n<p>$h=$ [[0]]</p>", "gaps": [{"correctAnswerFraction": false, "notationStyles": ["plain", "en", "si-en"], "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "maxValue": "{hcf}", "minValue": "{hcf}", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "numberentry", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": 1, "showFeedbackIcon": true}], "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}, {"prompt": "<p>Find integers $x$ and $y$ such that $\\simplify{h={sa}*x+{sb}*y }$</p>\n<p>$x=$ [[0]]</p>\n<p>$y=$ [[1]]</p>\n<p>If you use the extended Euclidean Algorithm as shown in the course then you will obtain the required values of $x$ and $y$.</p>\n<p>You can check your result by using the Maple command <code>igcdex({sa},{sb},'A','B'); A,B</code></p>", "gaps": [{"correctAnswerFraction": false, "notationStyles": ["plain", "en", "si-en"], "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "maxValue": "{csa}", "minValue": "{csa}", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "numberentry", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "1", "showFeedbackIcon": true}, {"correctAnswerFraction": false, "notationStyles": ["plain", "en", "si-en"], "allowFractions": false, "customMarkingAlgorithm": "", "mustBeReduced": false, "maxValue": "{csb}", "minValue": "{csb}", "useCustomName": false, "customName": "", "unitTests": [], "showFractionHint": true, "correctAnswerStyle": "plain", "mustBeReducedPC": 0, "scripts": {}, "extendBaseMarkingAlgorithm": true, "type": "numberentry", "variableReplacementStrategy": "originalfirst", "showCorrectAnswer": true, "variableReplacements": [], "marks": "1", "showFeedbackIcon": true}], "customMarkingAlgorithm": "", "showCorrectAnswer": true, "useCustomName": false, "customName": "", "unitTests": [], "sortAnswers": false, "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"}}, "extendBaseMarkingAlgorithm": true, "type": "gapfill", "variableReplacementStrategy": "originalfirst", "variableReplacements": [], "marks": 0, "showFeedbackIcon": true}], "variables": {"l2b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "floor(3*bsb/4)", "name": "l2b", "description": ""}, "bsb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "round(sa/hcf)", "name": "bsb", "description": ""}, "l1a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "floor(bsa/4)", "name": "l1a", "description": ""}, "la": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(l1a..l2a)", "name": "la", "description": ""}, "sb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(201..901)", "name": "sb", "description": ""}, "ub": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(l1b..l2b)", "name": "ub", "description": ""}, "l1b": {"templateType": "anything", "group": "Ungrouped variables", "definition": "floor(bsb/4)", "name": "l1b", "description": ""}, "l2a": {"templateType": "anything", "group": "Ungrouped variables", "definition": "floor(3*bsa/4)", "name": "l2a", "description": ""}, "hcf": {"templateType": "anything", "group": "Ungrouped variables", "definition": "gcd(sa,sb)", "name": "hcf", "description": ""}, "csb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd2(sa,sb)", "name": "csb", "description": ""}, "csa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "extendedgcd1(sa,sb)", "name": "csa", "description": ""}, "sa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(1001..2001)", "name": "sa", "description": ""}, "bsa": {"templateType": "anything", "group": "Ungrouped variables", "definition": "round(sb/hcf)", "name": "bsa", "description": ""}, "ua": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(l1a..l2a)", "name": "ua", "description": ""}, "lb": {"templateType": "anything", "group": "Ungrouped variables", "definition": "random(l1b..l2b)", "name": "lb", "description": ""}}, "ungrouped_variables": ["bsa", "bsb", "csa", "csb", "hcf", "l1a", "l1b", "l2a", "l2b", "la", "lb", "sa", "sb", "ua", "ub"], "variable_groups": [], "name": "Apply extended Euclidean algorithm to find gcd", "functions": {"extendedgcd1": {"type": "number", "language": "jme", "definition": "if((a|b) or (b|a),\n  0\n,\n  extendedgcd2(b,mod(a,b))\n)", "parameters": [["a", "number"], ["b", "number"]]}, "extendedgcd2": {"type": "number", "language": "jme", "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)", "parameters": [["a", "number"], ["b", "number"]]}, "mdescextgcd": {"type": "html", "language": "javascript", "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", "parameters": [["a", "number"], ["b", "number"], ["c1", "number"], ["c2", "number"], ["d1", "number"], ["d2", "number"]]}}, "variablesTest": {"condition": "", "maxRuns": 100}, "statement": "<p>Let $h=(\\var{sa},\\var{sb})$.&nbsp;</p>", "tags": ["checked2015"], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "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": ""}, "type": "question", "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "<p>Find gcd g of two positive integers x, y and also find integers a, b such that ax+by=g with prescribed intervals for a and b.</p>"}, "extensions": [], "advice": "<p>We use the extended Euclidean Algorithm to get:</p>\n<p>{mdescextGCD(sa,sb,1,0,0,1)}</p>\n<p>Hence $h=\\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>", "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}]}], "contributors": [{"name": "Christian Lawson-Perfect", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7/"}, {"name": "Newcastle University Mathematics and Statistics", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/697/"}]}