// Numbas version: exam_results_page_options
{"name": "Modular Arithmetic: Extended Euclidean Algorithm", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Modular Arithmetic: Extended Euclidean Algorithm", "tags": [], "metadata": {"description": "<p>Full worked solution using the Extended Euclidian Algorithm</p>", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "<p>The general method for solving an equation of the form $ax \\equiv c \\pmod{b}$ is called the <strong>Extended Euclidean Algorithm</strong>, which is procedure for finding $\\gcd(a,b)$ along with the integers $x,y$ such that</p>\n<p style=\"text-align: center;\">$ax + by = \\gcd(a,b).$</p>", "advice": "<p>This question shows the full Extended Euclidean Algorithm.</p>\n<p>Part (a) shows a shortcut to determine if there are no solutions to a given equation. $\\var{a}x\\pmod{\\var{2*a}}$ can only be equal to a mutliple of $\\gcd(\\var{a},\\var{2*a}) = \\var{a}$, and the multiples in modulo $\\var{2a}$ are $0$ and $\\var{a}$.</p>\n<p>So $\\var{a}x&nbsp; \\mod{\\var{2*a}} \\neq 1$ because $1$ is not a multiple of $\\var{a}$.</p>\n<p>Part (b) shows the full working for the Extended Euclidean Algorithm.</p>", "rulesets": {}, "extensions": [], "variables": {"q2": {"name": "q2", "group": "Ungrouped variables", "definition": "random(2..19)", "description": "", "templateType": "anything"}, "r1": {"name": "r1", "group": "Ungrouped variables", "definition": "q3*r2", "description": "", "templateType": "anything"}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "q0*b +r0", "description": "", "templateType": "anything"}, "q0": {"name": "q0", "group": "Ungrouped variables", "definition": "random(2..9)", "description": "", "templateType": "anything"}, "b": {"name": "b", "group": "Ungrouped variables", "definition": "q1*r0+r1", "description": "", "templateType": "anything"}, "r0": {"name": "r0", "group": "Ungrouped variables", "definition": "q2*r1 + r2", "description": "", "templateType": "anything"}, "r2": {"name": "r2", "group": "Ungrouped variables", "definition": "random(2..10)", "description": "<p>r2 is the gcd</p>", "templateType": "anything"}, "q1": {"name": "q1", "group": "Ungrouped variables", "definition": "random((r1+1)..19)", "description": "", "templateType": "anything"}, "q3": {"name": "q3", "group": "Ungrouped variables", "definition": "random(2..10)", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["r2", "q3", "r1", "q2", "q1", "r0", "b", "a", "q0"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>Remember that $ax \\mod{b}$ will always a multiple of the $\\gcd(a,b)$.</p>\n<p>So it's possible to tell straight away that there are no solutions to the equation $\\var{a}x \\equiv 1 \\pmod{\\var{2a}}$, because $1$ is not a multiple of $\\gcd(\\var{a},\\var{2a}) = $ [[0]].</p>", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "minValue": "{a}", "maxValue": "{a}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "sortAnswers": false}, {"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>The Extended Euclidean Algorithm can be used to solve $\\var{a}x\\equiv \\var{r2} \\pmod{\\var{b}}$ by reducing the problem via modular arithmetic. This is a similar method to the previous question, except this time we keep track of the quotients:</p>\n<table style=\"margin-left: auto; margin-right: auto;\">\n<tbody>\n<tr>\n<td>$\\var{a} = $</td>\n<td style=\"text-align: left;\">$\\var{b}q_0 + \\var{r0}$</td>\n<td style=\"text-align: right;\">where $q_0 = $ [[0]]</td>\n</tr>\n<tr>\n<td>$\\var{b} = $</td>\n<td style=\"text-align: left;\">$\\var{r0}q_1 + \\var{r1}$</td>\n<td style=\"text-align: right;\">where $q_1 = $ [[1]]</td>\n</tr>\n<tr>\n<td>$\\var{r0} = $</td>\n<td style=\"text-align: left;\">$\\var{r1}q_2 + \\var{r2}$</td>\n<td style=\"text-align: right;\">where $q_2 = $ [[2]]</td>\n</tr>\n<tr>\n<td>$\\var{r1} = $</td>\n<td style=\"text-align: left;\">$\\var{r2}\\times\\var{q3} + 0$.</td>\n<td style=\"text-align: right;\"></td>\n</tr>\n</tbody>\n</table>\n<p>Stop when you see a remainder of zero, because this means that the $\\gcd(\\var{a},\\var{b}) = \\gcd(\\var{r2},0) = \\var{r2}$. Treat the numbers as symbols (no simplification) and use back-substitution to eliminate the remainders $\\var{r1}$ and $\\var{r0}$. The result is an expression of the $\\gcd$ in the form $\\var{a}x + \\var{b}y$.</p>\n<table style=\"margin-left: auto; margin-right: auto;\">\n<tbody>\n<tr>\n<td style=\"text-align: right;\">$\\var{r2}$</td>\n<td style=\"text-align: left;\">$ = \\var{r0} - \\var{r1} q_2$</td>\n<td style=\"text-align: left;\">substitute $\\var{r1} = \\var{b} - \\var{r0}q_1$</td>\n</tr>\n<tr>\n<td style=\"text-align: right;\"></td>\n<td style=\"text-align: left;\">$ = \\var{r0} - (\\var{b} - \\var{r0}q_1) q_2$</td>\n<td style=\"text-align: left;\">collect like terms</td>\n</tr>\n<tr>\n<td></td>\n<td style=\"text-align: left;\">$ = \\var{r0}(1+q_1q_2) - \\var{b}q_2$</td>\n<td style=\"text-align: left;\">substitute $\\var{r0} = \\var{a} -\\var{b}q_0 $</td>\n</tr>\n<tr>\n<td></td>\n<td style=\"text-align: left;\">$ = (\\var{a} -\\var{b}q_0)(1+q_1q_2) - \\var{b}q_2$</td>\n<td style=\"text-align: left;\">collect like terms</td>\n</tr>\n<tr>\n<td></td>\n<td style=\"text-align: left;\">$ = \\var{a}(1+q_1q_2) - \\var{b}(q_2+q_0(1+q_1q_2))$</td>\n<td></td>\n</tr>\n</tbody>\n</table>\n<p>Now, using the values of the quotients $q_0,q_1,q_2$ you computed earlier, this means:</p>\n<p style=\"text-align: center;\">$\\var{r2} = \\var{a}\\times\\var{1+q1*q2} - \\var{b}\\times\\var{q2+q0*(1+q1*q2)}$.</p>\n<p>So the solution to $\\var{a}x\\equiv \\var{r2} \\pmod{\\var{b}}$ is $x = $ [[3]]</p>", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "minValue": "{q0}", "maxValue": "{q0}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "minValue": "{q1}", "maxValue": "{q1}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "minValue": "{q2}", "maxValue": "{q2}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "minValue": "{1+q1*q2}", "maxValue": "{1+q1*q2}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "sortAnswers": false}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}]}], "contributors": [{"name": "Daniel Mansfield", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/743/"}, {"name": "Sean Gardiner", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/2443/"}]}