// Numbas version: finer_feedback_settings
{"name": "Modular Arithmetic: Greatest Common Divisor", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Modular Arithmetic: Greatest Common Divisor", "tags": [], "metadata": {"description": "<p>Introduces the GCD and a simple form of the Euclidian Algorithm</p>", "licence": "Creative Commons Attribution-ShareAlike 4.0 International"}, "statement": "<p>A number $n$ <strong>divides</strong> $a$ when $a = nq$ for some $q$.</p>\n<p>Any number which divides both $a$ and $b$ is called a <strong>common d</strong><strong>ivisor</strong> of $a$ and $b$, the largest common divisor is called the <strong>greatest common divisor</strong> and is denoted $\\gcd(a,b)$.</p>", "advice": "<p>Every number divides zero, so the largest number to divide $\\var{a1}$ is the greatest common divisor of $0$ and $\\var{a1}$. This means that $\\gcd(\\var{a1},0) = \\var{a1}$.</p>\n<hr/>\n<p>The Euclidian Algorithm presented here is a variation on the usual presentation. Another common method keeps track of the quotients:</p>\n<p style=\"text-align: center;\">$ \\var{gcd*(1+b*(1+a))} = \\var{b}\\times (\\var{gcd*(1+a)}) + \\var{a1} $</p>\n<p style=\"text-align: center;\">$ \\var{gcd*(1+a)} = \\var{gcd*(1+a)/a1}\\times (\\var{a1}) + 0 $</p>\n<p>to write the $\\gcd$ in the form of <a href=\"https://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity\" target=\"_blank\" rel=\"noopener noreferrer\" title=\"B&eacute;zout's identity\">B&eacute;zout's identity</a></p>\n<p style=\"text-align: center;\">$ \\var{gcd*(1+b*(1+a))} - \\var{b}\\times (\\var{gcd*(1+a)}) = \\var{a1}$.</p>", "rulesets": {}, "extensions": [], "variables": {"a2": {"name": "a2", "group": "Ungrouped variables", "definition": "mod(gcd*(a+1),a1)", "description": "", "templateType": "anything"}, "b": {"name": "b", "group": "Ungrouped variables", "definition": "random(2..9 except [a,gcd])", "description": "", "templateType": "anything"}, "a1": {"name": "a1", "group": "Ungrouped variables", "definition": "mod(gcd*(1+b*(1+a)),gcd*(1+a))", "description": "", "templateType": "anything"}, "big": {"name": "big", "group": "Ungrouped variables", "definition": "random(100..199)", "description": "", "templateType": "anything"}, "gcd": {"name": "gcd", "group": "Ungrouped variables", "definition": "random(3..19)", "description": "", "templateType": "anything"}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "random(2..9 except gcd)", "description": "", "templateType": "anything"}, "c": {"name": "c", "group": "Ungrouped variables", "definition": "gcd*(1+a)/a1", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": ["a", "b", "gcd", "a1", "a2", "c", "big"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>As a consequence of these definitions, every number $n$ divides zero because $0 = n\\times 0$.</p>\n<p>So $\\gcd(\\var{big},0)$ is</p>", "minValue": "{big}", "maxValue": "{big}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": "3", "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>What is $\\gcd(\\var{gcd*(1+b*(1+a))},\\var{gcd*(1+a)})$?</p>", "stepsPenalty": 0, "steps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p>The procedure is to use the identity</p>\n<p style=\"text-align: center;\">&nbsp;$\\gcd(a,b) = \\gcd(a\\mod b, b)$.</p>\n<p style=\"text-align: left;\">to simplify the question.</p>\n<p>Compute $\\var{gcd*(1+b*(1+a))} \\mod{\\var{gcd*(1+a)}}$.</p>", "minValue": "{a1}", "maxValue": "{a1}", "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": [], "prompt": "<p>Hence $\\gcd(\\var{gcd*(1+b*(1+a))},\\var{gcd*(1+a)}) = \\gcd(\\var{a1},\\var{gcd*(1+a)})$. We can simplify this again using the identity</p>\n<p style=\"text-align: center;\">&nbsp;$\\gcd(a,b) = \\gcd(a, b\\mod a)$.</p>\n<p style=\"text-align: left;\">Compute $\\var{gcd*(a+1)} \\mod{\\var{a1}} $.</p>", "minValue": "{a2}", "maxValue": "{a2}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "information", "useCustomName": false, "customName": "", "marks": 0, "showCorrectAnswer": true, "showFeedbackIcon": true, "scripts": {}, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "adaptiveMarkingPenalty": 0, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "prompt": "<p style=\"text-align: left;\">By re-applying these identities, the question has been simplified to something managable:</p>\n<p style=\"text-align: center;\">$\\gcd(\\var{gcd*(1+b*(1+a))},\\var{gcd*(1+a)}) = \\gcd(\\var{a1},\\var{gcd*(1+a)}) = \\gcd(\\var{a1}, 0)$.</p>"}], "minValue": "{gcd}", "maxValue": "{gcd}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "type": "question", "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/"}], "resources": []}]}], "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/"}]}