Tests students' ability to apply the recursive form of the Extended Euclidean Algorithm. Random four-digit inputs are chosen subject to the condition that the Euclidean Algorithm terminates in seven steps.
", "licence": "Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International"}, "statement": "Applying the Euclidean Algorithm to the integers $\\var{a}$ and $\\var{b}$ yields the equations \\[\\var{calcs[0][1]}=\\var{calcs[0][0]}\\times\\var{calcs[0][2]}+\\var{calcs[1][2]},\\] \\[\\var{calcs[1][1]}=\\var{calcs[1][0]}\\times\\var{calcs[1][2]}+\\var{calcs[2][2]},\\] \\[\\var{calcs[2][1]}=\\var{calcs[2][0]}\\times\\var{calcs[2][2]}+\\var{calcs[3][2]},\\]\\[\\var{calcs[3][1]}=\\var{calcs[3][0]}\\times\\var{calcs[3][2]}+\\var{calcs[4][2]},\\]\\[\\var{calcs[4][1]}=\\var{calcs[4][0]}\\times\\var{calcs[4][2]}+\\var{calcs[5][2]},\\]\\[\\var{calcs[5][1]}=\\var{calcs[5][0]}\\times\\var{calcs[5][2]}+\\var{calcs[6][2]},\\]\\[\\var{calcs[6][1]}=\\var{calcs[6][0]}\\times\\var{calcs[6][2]}+\\var{calcs[7][2]}.\\]
", "advice": "a) As per the notes, we determine the values of $s_i$ by using the formula $s_i=s_{i-2}-qs_{i-1}$, with $s_0=1$ and $s_1=0$.
\nb) As per the notes, we determine the values of $t_i$ by using the formula $t_i=t_{i-2}-qt_{i-1}$, with $t_0=0$ and $t_1=1$.
\nc) The required values are $s_7$ and $t_7$, i.e. $\\var{smatrix[0][k]}$ and $\\var{tmatrix[0][k]}$. We can check that these values are correct by observing that $\\var{smatrix[0][k]}\\cdot\\var{a}+\\var{tmatrix[0][k]}\\cdot\\var{b}=\\var{gcd(a,b)}$ as required.
", "rulesets": {}, "extensions": [], "builtin_constants": {"e": true, "pi,\u03c0": true, "i": true}, "constants": [], "variables": {"a": {"name": "a", "group": "Ungrouped variables", "definition": "random(1000 .. 9999#1)", "description": "", "templateType": "randrange", "can_override": false}, "b": {"name": "b", "group": "Ungrouped variables", "definition": "random(1000 .. 9999#1)", "description": "", "templateType": "randrange", "can_override": false}, "calcs": {"name": "calcs", "group": "Ungrouped variables", "definition": "iterate_until([(r2-mod(r2,mod(r1,r2)))/mod(r1,r2),r2,mod(r1,r2),s2,s1-q*s2,t2,t1-q*t2],[q,r1,r2,s1,s2,t1,t2],[(a-mod(a,b))/b,a,b,1,0,0,1],[q,r1,r2,s1,s2,t1,t2][2]=0)", "description": "", "templateType": "anything", "can_override": false}, "quotients": {"name": "quotients", "group": "Ungrouped variables", "definition": "map(calcs[i][0],i,0..k-1\n)", "description": "", "templateType": "anything", "can_override": false}, "k": {"name": "k", "group": "Ungrouped variables", "definition": "len(calcs)-1", "description": "", "templateType": "anything", "can_override": false}, "smatrix": {"name": "smatrix", "group": "Ungrouped variables", "definition": "matrix(map(calcs[i][3],i,0..k))", "description": "", "templateType": "anything", "can_override": false}, "tmatrix": {"name": "tmatrix", "group": "Ungrouped variables", "definition": "matrix(map(calcs[i][5],i,0..k))", "description": "", "templateType": "anything", "can_override": false}}, "variablesTest": {"condition": "a>b and k=7", "maxRuns": 100}, "ungrouped_variables": ["a", "b", "calcs", "k", "quotients", "smatrix", "tmatrix"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "matrix", "useCustomName": false, "customName": "", "marks": "2", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Compute the values $s_0,s_1,\\dotsc,s_7$ described in Algorithm 2.9 in the Number Theory Unit 1 notes.
", "correctAnswer": "smatrix", "correctAnswerFractions": false, "numRows": 1, "numColumns": "8", "allowResize": false, "tolerance": 0, "markPerCell": true, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"type": "matrix", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Compute the values $t_0,t_1,\\dotsc,t_7$ described in Algorithm 2.9 in the Number Theory Unit 1 notes.
", "correctAnswer": "tmatrix", "correctAnswerFractions": false, "numRows": 1, "numColumns": "8", "allowResize": false, "tolerance": 0, "markPerCell": true, "allowFractions": false, "minColumns": 1, "maxColumns": 0, "minRows": 1, "maxRows": 0, "prefilledCells": ""}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Use your answers to parts a) and b) to find integers $s$ and $t$ such that $\\var{a}\\times s+\\var{b}\\times t=\\var{gcd(a,b)}$.
\n$s=$[[0]] $t=$ [[1]]