// Numbas version: exam_results_page_options
{"name": "Teilbarkeitsaussage", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Teilbarkeitsaussage", "tags": [], "metadata": {"description": "<p>Guided induction proof of a divisibility statement (with moderate randomization).</p>", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "<p>In dieser Aufgabe m&uuml;ssen Sie einige L&uuml;cken in einem Induktionsbeweis f&uuml;llen. Um die Aufgabe optimal zu nutzen, sollten Sie aber als erstes versuchen, selbst einen Beweis der genannten Aussage zu verfassen! Man braucht einen kleinen Trick, um den Induktionsschritt zu beweisen. Wenn Sie nicht direkt darauf kommen, dann schauen Sie sich den L&uuml;ckentext an, und erzeugen danach eine neue Aufgabe nach demselben Prinzip, aber mit anderen Zahlen, an der Sie sich dann noch einmal selbst versuchen k&ouml;nnen.</p>", "advice": "<p>Hier noch einmal der vollst&auml;ndige Beweis.</p>\n<p>Behauptung: F&uuml;r alle nat&uuml;rlichen Zahlen $n$ ist $\\var{b}^{\\simplify{{r}n + {2*r*k}}} - \\var{l*a-1}^n$ durch $\\var{a}$ teilbar.</p>\n<p>Beweis durch vollst&auml;ndige Induktion nach $n$.</p>\n<p>Induktionsanfang $n=0$. Dann ist $\\var{b}^{\\simplify{{r}n + 2*{k*r}}} - \\var{l*a-1}^n$ = $\\var{b}^\\var{2*k*r} - \\var{l*a-1}^0$ =$\\simplify{ {b^(2*k*r)}} - 1 = \\simplify{ {b^(2*k*r)} - 1}$, und dies ist durch $\\var{a}$ teilbar.</p>\n<p>Induktionsschritt $n&gt;0$. Wir m&uuml;ssen nun zeigen, dass $\\var{b}^{\\simplify{{r}n + {2*r*k}}} - \\var{l*a-1}^n$ durch $\\var{a}$ teilbar ist, und d&uuml;rfen dabei benutzen:</p>\n<p>Induktionsvoraussetzung: $\\displaystyle{\\quad\\var{b}^{\\simplify{{r}(n-1) + {2*r*k}}} - \\var{l*a-1}^{n-1}}$ ist durch $\\var{a}$ teilbar.</p>\n<p>Wir schreiben den Ausdruck, um den es geht, so um, dass wir den Term aus der Induktionsvoraussetzung dort wiederfinden:</p>\n<p>\\[ &nbsp;\\var{b}^{\\simplify{{r}n + {2*r*k}}} - \\var{l*a-1}^n =&nbsp; \\var{b}^{\\simplify{{r}(n-1) + {2*r*k}}}\\cdot \\var{b}^{\\var{r}}&nbsp; - \\var{l*a-1}^n&nbsp; =&nbsp;\\var{b}^{\\simplify{{r}(n-1) + {2*r*k}}}\\cdot \\var{b}^{\\var{r}}&nbsp; -\\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} +&nbsp; &nbsp;\\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} &nbsp; - \\var{l*a-1}^n = \\var{b}^{\\var{r}}\\cdot A +&nbsp;&nbsp;\\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} &nbsp; - \\var{l*a-1}^n, \\]</p>\n<p>wobei $A := \\var{b}^{\\simplify{{r}(n-1) + {2*r*k}}} - \\var{l*a-1}^{n-1}$ der Term aus der Induktionsvoraussetzung ist, von dem wir bereits wissen, dass er ein Vielfaches von $\\var{a}$ ist. Es gen&uuml;gt daher zu zeigen, dass auch $\\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} &nbsp; - \\var{l*a-1}^n$ ein Vielfaches von $\\var{a}$ ist, denn die Summe von zwei Vielfachen von $\\var{a}$ ist wieder ein Vielfaches von $\\var{a}$. Wir formen dies um zu</p>\n<p>\\[ \\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} &nbsp; - \\var{l*a-1}^n = \\var{l*a-1}^{n-1}\\cdot (\\simplify{{b}^{r}} - \\simplify{{l*a-1}}),\\]</p>\n<p>und dies ist offensichtlich ein Vielfaches von $\\var{a}$, weil $\\simplify{{b}^{r}} - \\simplify{{l*a-1}} = \\simplify{{b}^{r}-{l*a-1}} = \\simplify{({b}^{r}-{l*a-1})/{a}} \\cdot \\var{a}$ ein Vielfaches von $\\var{a}$ ist.</p>\n<p></p>\n<p><em>Bemerkung:</em> Wir werden sp&auml;ter mit dem \"Rechnen mit Restklassen\" eine andere, einfachere M&ouml;glichkeit kennenlernen, um diese und viele &auml;hnliche Aussagen zu beweisen.</p>", "rulesets": {}, "extensions": [], "variables": {"base_data": {"name": "base_data", "group": "Ungrouped variables", "definition": "[[5, 2, 2], [6, 5, 3], [7, 6, 3], [7,5,3], [13, 5, 2], [17, 4, 2], [10, 3, 2]]", "description": "<p>List of tuples (a, b, r) where a is a natural number, r is not too large, and $b^r \\equiv -1 \\mod a$.</p>", "templateType": "anything"}, "entry": {"name": "entry", "group": "Ungrouped variables", "definition": "random(0..length(base_data)-1)", "description": "", "templateType": "anything"}, "a": {"name": "a", "group": "Ungrouped variables", "definition": "base_data[entry][0]", "description": "", "templateType": "anything"}, "b": {"name": "b", "group": "Ungrouped variables", "definition": "base_data[entry][1]", "description": "", "templateType": "anything"}, "r": {"name": "r", "group": "Ungrouped variables", "definition": "base_data[entry][2]", "description": "", "templateType": "anything"}, "l": {"name": "l", "group": "Ungrouped variables", "definition": "random(1..3)", "description": "", "templateType": "anything"}, "k": {"name": "k", "group": "Ungrouped variables", "definition": "random(0..1)", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "(mod(b^r, a)=a-1) && !(b^r = l*a-1) && !(b = l*a-1)", "maxRuns": "100"}, "ungrouped_variables": ["base_data", "entry", "a", "b", "r", "l", "k"], "variable_groups": [], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"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": "<p>Beweisen Sie durch vollst&auml;ndige Induktion, dass f&uuml;r alle nat&uuml;rlichen Zahlen $n$ die Zahl $\\var{b}^{\\simplify{{r}n + 2*{k}}} - \\var{l*a-1}^n$ durch $\\var{a}$ teilbar ist.</p>\n<p></p>\n<p>Behauptung: F&uuml;r alle nat&uuml;rlichen Zahlen $n$ ist $\\var{b}^{\\simplify{{r}n + {2*r*k}}} - \\var{l*a-1}^n$ durch $\\var{a}$ teilbar.</p>\n<p>Beweis durch vollst&auml;ndige Induktion nach $n$.</p>\n<p>Induktionsanfang [[0]]. Dann ist $\\var{b}^{\\simplify{{r}n + 2*{k*r}}} - \\var{l*a-1}^n$ = $\\var{b}^\\var{2*k*r} - \\var{l*a-1}^0$ =$\\simplify{ {b^(2*k*r)}} - 1 = \\simplify{ {b^(2*k*r)} - 1}$, und dies ist durch $\\var{a}$ teilbar.</p>\n<p>Induktionsschritt $n&gt;0$. Wir m&uuml;ssen nun zeigen, dass $\\var{b}^{\\simplify{{r}n + {2*r*k}}} - \\var{l*a-1}^n$ durch $\\var{a}$ teilbar ist, und d&uuml;rfen dabei benutzen:</p>\n<p>[[1]]: &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; [[2]] ist durch $\\var{a}$ teilbar.</p>\n<p>Wir schreiben den Ausdruck, um den es geht, so um, dass wir den Term aus der Induktionsvoraussetzung dort wiederfinden:</p>\n<p>\\[ &nbsp;\\var{b}^{\\simplify{{r}n + {2*r*k}}} - \\var{l*a-1}^n =&nbsp; \\var{b}^{\\simplify{{r}(n-1) + {2*r*k}}}\\cdot \\var{b}^{\\var{r}}&nbsp; - \\var{l*a-1}^n&nbsp; \\]</p>\n<p>$\\displaystyle{ =&nbsp;\\var{b}^{\\simplify{{r}(n-1) + {2*r*k}}}\\cdot \\var{b}^{\\var{r}}&nbsp; -\\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} + }$ [[3]] $\\displaystyle{ - \\var{l*a-1}^n = \\var{b}^{\\var{r}}\\cdot A +&nbsp;&nbsp;\\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} &nbsp; - \\var{l*a-1}^n, }$</p>\n<p>wobei $A := $ [[4]] der Term aus der Induktionsvoraussetzung ist, von dem wir bereits wissen, dass er ein Vielfaches von $\\var{a}$ ist. Es gen&uuml;gt daher zu zeigen, dass auch [[5]]&nbsp; ein Vielfaches von $\\var{a}$ ist, denn die Summe von zwei Vielfachen von $\\var{a}$ ist wieder ein Vielfaches von $\\var{a}$. Wir formen dies um zu</p>\n<p>$\\displaystyle{ \\var{l*a-1}^{n-1}\\cdot\\var{b}^{\\var{r}} &nbsp; - \\var{l*a-1}^n = \\var{l*a-1}^{n-1}\\cdot( }$ [[6]] $\\displaystyle{)}$,</p>\n<p>und dies ist offensichtlich ein Vielfaches von $\\var{a}$, weil $\\simplify{{b}^{r}} - \\simplify{{l*a-1}} = \\simplify{{b}^{r}-{l*a-1}} = \\simplify{({b}^{r}-{l*a-1})/{a}} \\cdot \\var{a}$ ein Vielfaches von $\\var{a}$ ist.</p>\n<p></p>", "gaps": [{"type": "patternmatch", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": " *n *= *0 *", "displayAnswer": "n=0", "matchMode": "regex"}, {"type": "patternmatch", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "Induktionsvoraussetzung", "displayAnswer": "", "matchMode": "exact"}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "{b}^({r}(n-1) + {2*r*k}) - {l*a-1}^(n-1)", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": "1", "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "{l*a-1}^(n-1)*{b}^{r}", "answerSimplification": "basic, timesdot", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": "0.001", "failureRate": "1", "vsetRangePoints": "5", "vsetRange": ["0", "1"], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "maxlength": {"length": "0", "partialCredit": "0", "message": ""}, "minlength": {"length": "0", "partialCredit": "0", "message": ""}, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "{b}^({r}(n-1) + {2*r*k}) - {l*a-1}^(n-1)", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "{l*a-1}^(n-1)*{b}^{r}  - {l*a-1}^n", "answerSimplification": "basic, timesdot", "showPreview": false, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": [{"name": "n", "value": ""}]}, {"type": "jme", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "answer": "{b}^{r} - {l*a-1}", "answerSimplification": "basic", "showPreview": true, "checkingType": "absdiff", "checkingAccuracy": 0.001, "failureRate": 1, "vsetRangePoints": 5, "vsetRange": [0, 1], "checkVariableNames": false, "singleLetterVariables": false, "allowUnknownFunctions": true, "implicitFunctionComposition": false, "valuegenerators": []}], "sortAnswers": false}], "partsMode": "all", "maxMarks": 0, "objectives": [], "penalties": [], "objectiveVisibility": "always", "penaltyVisibility": "always", "contributors": [{"name": "Ulrich G\u00f6rtz", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7603/"}]}]}], "contributors": [{"name": "Ulrich G\u00f6rtz", "profile_url": "https://numbas.mathcentre.ac.uk/accounts/profile/7603/"}]}