Find $d$, using the Euclidean algorithm.
\n$d=$ [[0]]
", "sortAnswers": false, "showFeedbackIcon": true, "type": "gapfill", "customMarkingAlgorithm": "", "gaps": [{"variableReplacements": [], "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "marks": "10", "allowFractions": false, "mustBeReduced": false, "showFeedbackIcon": true, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "mustBeReducedPC": 0, "minValue": "{hcf}", "customMarkingAlgorithm": "", "maxValue": "{hcf}", "correctAnswerFraction": false, "unitTests": [], "showCorrectAnswer": true, "correctAnswerStyle": "plain", "scripts": {}}], "unitTests": [], "showCorrectAnswer": true, "scripts": {}}, {"variableReplacements": [], "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "marks": 0, "prompt": "Find integers $x$ and $y$ such that $\\simplify{d={sa}*x+{sb}*y }$.
\n$x=$ [[0]]
\n$y=$ [[1]]
\nIf 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$.
\nAfter you finish the question, \"Reveal answers\" will give you a completely worked solution.
", "sortAnswers": false, "showFeedbackIcon": true, "type": "gapfill", "customMarkingAlgorithm": "", "gaps": [{"variableReplacements": [], "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "marks": "10", "allowFractions": false, "mustBeReduced": false, "showFeedbackIcon": true, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "mustBeReducedPC": 0, "minValue": "{csa}", "customMarkingAlgorithm": "", "maxValue": "{csa}", "correctAnswerFraction": false, "unitTests": [], "showCorrectAnswer": true, "correctAnswerStyle": "plain", "scripts": {}}, {"variableReplacements": [], "extendBaseMarkingAlgorithm": true, "variableReplacementStrategy": "originalfirst", "marks": "10", "allowFractions": false, "mustBeReduced": false, "showFeedbackIcon": true, "type": "numberentry", "notationStyles": ["plain", "en", "si-en"], "mustBeReducedPC": 0, "minValue": "{csb}", "customMarkingAlgorithm": "", "maxValue": "{csb}", "correctAnswerFraction": false, "unitTests": [], "showCorrectAnswer": true, "correctAnswerStyle": "plain", "scripts": {}}], "unitTests": [], "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"}}}], "rulesets": {"std": ["all", "fractionNumbers", "!collectNumbers", "!noLeadingMinus"]}, "variablesTest": {"condition": "", "maxRuns": 100}, "metadata": {"licence": "Creative Commons Attribution 4.0 International", "description": "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.
"}, "advice": "We use the extended Euclidean Algorithm to get:
\n{mdescextGCD(sa,sb,1,0,0,1)}
\nHence $d=\\var{hcf}$ and we have
\n\\[ x= \\var{csa}, \\quad y=\\var{csb}\\]
\nThat is,
\n\\[ \\simplify[!basic]{{sa}*{csa}+{sb}*{csb} = {hcf}} \\]
", "variable_groups": [], "statement": "Let $d=\\text{gcd}(\\var{sa},\\var{sb})$.
\nThese numbers will differ each time you start this question anew, so you can practice this question as often as you want by clicking \"Try another question like this one\" below.
", "name": "Apply extended Euclidean algorithm to find gcd", "ungrouped_variables": ["bsa", "bsb", "csa", "csb", "hcf", "l1a", "l1b", "l2a", "l2b", "la", "lb", "sa", "sb", "ua", "ub"], "preamble": {"js": "", "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}"}, "functions": {"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=$('| $\\\\var{'+a+'}$ | $\\\\var{'+b+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ | $\\\\var{'+a+'}$ | $\\\\var{'+b+'}-\\\\var{'+fl+'}\\\\times\\\\var{'+a+'}$ | $'+ disp(c1+'a+'+c2+'b')+'$ | $'+disp(d1+'a+'+d2+'b-'+fl+'('+c1+'a+'+c2+'b'+')')+'$ | ');\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('
| $\\\\var{'+a+'}-\\\\var{'+fl1+'}\\\\times\\\\var{'+b+'}$ | $\\\\var{'+b+'}$ | $'+disp(c1+'a+'+c2+'b-'+fl1+'('+d1+'a+'+d2+'b'+')')+'$ | $'+ disp(d1+'a+'+d2+'b')+'$ |