Simple direct computations in $\\mathbb Z/n$.
", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "In dieser Aufgabe soll das Rechnen mit Restklassen in $\\mathbb Z/n$ geübt werden. Die Elemente von $\\mathbb Z/n$ werden hier einfach als $0, 1, 2, \\dots, n-1$ notiert, also ohne Überstrich oder eckige Klammern.
", "advice": "a)
\nIn diesen Fällen kann man zuerst das Ergebnis der Rechnung in $\\mathbb Z$ ausrechnen, und dann den Rest bei Division durch $n$ bilden.
\nb)
\nBei den höheren Potenzen ist es wichtig auszunutzen, dass man \"zwischendurch\" jederzeit zum Rest bei Division durch $\\var{m}$ übergehen kann, und vorherige Schritte benutzen kann, zum Beispiel gilt in $\\mathbb Z/\\var{m}$:
\n\\[ \\var{bm}^2 = \\var{bm2},\\quad \\var{bm}^3 = \\var{bm2} \\cdot \\var{bm} = \\var{bm3}, \\quad \\var{bm}^4 = \\var{bm2}^2 = \\var{bm4}, \\dots \\]
\nc)
\nMit den Methoden, die wir im Moment kennen, ist hier (geschicktes) Ausprobieren angesagt. (Und wie in Teil b) ist es sinnvoll, Zwischenergebnisse durch die Restklasse modulo $\\var{p}$, also den Rest bei Division durch $\\var{p}$ zu ersetzen.) Wenn Sie nicht direkt eine Zahl $b$ mit $\\var{ap}b = 1$ in $\\mathbb Z/p$ (also so dass $\\var{ap}b-1$ durch $p$ teilbar ist) finden, ist es zum Beispiel auch nützlich, wenn Sie auf $\\var{ap}b = -1$ in $\\mathbb Z/p$ kommen, denn dann ist $(\\var{ap}b)^2 = 1$, also $\\var{ap}^{-1} = \\var{ap}b^2$.
\nFür die zweite Rechnung sollten Sie natürlich ausnutzen, dass Sie im ersten Schritt $\\var{ap}^{-1}$ bereits ausgerechnet haben.
\nErgänzung: Der Euklidische Algorithmus (den wir in der Linearen Algebra 2 behandeln werden) ist eine Möglichkeit, in systematischer Weise ein Inverses von $\\var{ap}$ zu finden, da er erlaubt, den ggT von $\\var{ap}$ und $\\var{p}$ (das ist $1$) in der Form $\\var{ap}b + \\var{p}c$ mit ganzen Zahlen $b$ und $c$ auszudrücken, und dann gilt in $\\mathbb Z/\\var{p}$, dass $\\var{ap}b = 1$, also $\\var{ap}^{-1} = b$.
\nd)
\nEine Gleichung (dieser einfachen Form) zu lösen, geht im Körper $\\mathbb Z/\\var{psm}$ im Prinzip wie in jedem anderen Körper. Die Lösung der Gleichung $ax=b$ ist $x=ba^{-1}$. Die Schwierigkeit ist hier also vor allem wieder, die multiplikativen Inversen auszurechnen. Bei der zweiten Gleichung ist es wahrscheinlich nützlich, zuerst mit $\\var{fpsm}$ durchzumultiplizieren, und dann zu den Resten nach Division durch $\\var{psm}$ überzugehen.
", "rulesets": {}, "extensions": [], "variables": {"n": {"name": "n", "group": "Group 1 - mod n", "definition": "random(7..22)", "description": "", "templateType": "anything"}, "p": {"name": "p", "group": "Group 2 - mod p prime", "definition": "random(primes)", "description": "", "templateType": "anything"}, "primes": {"name": "primes", "group": "Group 2 - mod p prime", "definition": "[7, 11, 13, 17, 19, 23]", "description": "", "templateType": "anything"}, "a": {"name": "a", "group": "Group 1 - mod n", "definition": "random(2..n-1)", "description": "", "templateType": "anything"}, "b": {"name": "b", "group": "Group 1 - mod n", "definition": "random(5..n-1)", "description": "", "templateType": "anything"}, "c": {"name": "c", "group": "Group 1 - mod n", "definition": "random(0..n-1)", "description": "", "templateType": "anything"}, "e1": {"name": "e1", "group": "Group 1 - mod n", "definition": "random(3..5)", "description": "", "templateType": "anything"}, "d": {"name": "d", "group": "Group 1 - mod n", "definition": "random(3..n-1)", "description": "", "templateType": "anything"}, "m": {"name": "m", "group": "Group 1 - mod n", "definition": "random(8..14 except n)", "description": "", "templateType": "anything"}, "am": {"name": "am", "group": "Group 1 - mod n", "definition": "random(3..m-1)", "description": "", "templateType": "anything"}, "bm": {"name": "bm", "group": "Group 1 - mod n", "definition": "random(4..m-1 except am)", "description": "", "templateType": "anything"}, "e2": {"name": "e2", "group": "Group 1 - mod n", "definition": "random(12..25 except e1)", "description": "", "templateType": "anything"}, "psm": {"name": "psm", "group": "Group 3 - mod psm a small prime", "definition": "random([7, 11, 13])", "description": "", "templateType": "anything"}, "ap": {"name": "ap", "group": "Group 2 - mod p prime", "definition": "random(2..p-2)", "description": "", "templateType": "anything"}, "bp": {"name": "bp", "group": "Group 2 - mod p prime", "definition": "random(2..p-1)", "description": "", "templateType": "anything"}, "cp": {"name": "cp", "group": "Group 2 - mod p prime", "definition": "random(1..p-1)", "description": "", "templateType": "anything"}, "apsm": {"name": "apsm", "group": "Group 3 - mod psm a small prime", "definition": "random(2..psm-2)", "description": "", "templateType": "anything"}, "bpsm": {"name": "bpsm", "group": "Group 3 - mod psm a small prime", "definition": "random(1..psm-1)", "description": "", "templateType": "anything"}, "cpsm": {"name": "cpsm", "group": "Group 3 - mod psm a small prime", "definition": "random(2..psm-2)", "description": "", "templateType": "anything"}, "dpsm": {"name": "dpsm", "group": "Group 3 - mod psm a small prime", "definition": "random(3..psm-3)", "description": "", "templateType": "anything"}, "epsm": {"name": "epsm", "group": "Group 3 - mod psm a small prime", "definition": "random(2..psm-2)", "description": "", "templateType": "anything"}, "fpsm": {"name": "fpsm", "group": "Group 3 - mod psm a small prime", "definition": "random(2..psm-2)", "description": "", "templateType": "anything"}, "bm2": {"name": "bm2", "group": "Group 1 - mod n", "definition": "powmod(bm, 2, m)", "description": "", "templateType": "anything"}, "bm3": {"name": "bm3", "group": "Group 1 - mod n", "definition": "powmod(bm, 3, m)", "description": "", "templateType": "anything"}, "bm4": {"name": "bm4", "group": "Group 1 - mod n", "definition": "powmod(bm, 4, m)", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [{"name": "Group 1 - mod n", "variables": ["n", "a", "b", "c", "e1", "d", "m", "am", "bm", "e2", "bm2", "bm3", "bm4"]}, {"name": "Group 2 - mod p prime", "variables": ["p", "primes", "ap", "bp", "cp"]}, {"name": "Group 3 - mod psm a small prime", "variables": ["psm", "apsm", "bpsm", "cpsm", "dpsm", "epsm", "fpsm"]}], "functions": {"powmod": {"parameters": [["a", "number"], ["e", "number"], ["n", "number"]], "type": "number", "language": "javascript", "definition": "var result = 1;\nwhile (e) {\n result = (a*result) % n;\n e -= 1\n}\nreturn result;"}, "invmod": {"parameters": [["a", "number"], ["p", "number"]], "type": "number", "language": "javascript", "definition": "if (Numbas.math.gcd(a, p) > 1) return NaN;\n\nfunction express_gcd(a, b) {\n // returns [x,y] where xa+yb = gcd(a,b)\n // assume a, b > 0\n \n var swap = false;\n if (a < b) {\n var c = a;\n a = b;\n b = c;\n swap = true;\n }\n if (a % b == 0) // b divides a\n return swap ? [1, 0] : [0, 1];\n\n var l = express_gcd(a-b, b);\n return swap ? [l[1]-l[0], l[0]] : [l[0], l[1]-l[0]];\n}\n\nvar res = express_gcd(a,p)[0];\nwhile (res<0) res += p;\nreturn res;"}}, "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": "Rechnen Sie in $\\mathbb Z/\\var{n}$. Geben Sie alle Ergebnisse als Zahlen zwischen $0$ und $\\var{n-1}$ an.
\n$\\var{a} + \\var{b} = $ [[0]]
\n$(\\var{a} - \\var{c})\\cdot \\var{d}$ = [[1]]
\n$\\var{b} + \\var{d}\\cdot \\var{b}$ = [[2]]
", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{mod(a+b,n)}", "maxValue": "{mod(a+b,n)}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{mod((a-c)*d, n)}", "maxValue": "{mod((a-c)*d, n)}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{mod(b+b*d, n)}", "maxValue": "{mod(b+b*d, n)}", "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, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Rechnen Sie in $\\mathbb Z/\\var{m}$. Geben Sie alle Ergebnisse als Zahlen zwischen $0$ und $\\var{m-1}$ an.
\n$\\var{am}^\\var{e1} = $ [[0]]
\n$\\var{bm}^\\var{e2} = $ [[1]]
", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{powmod(am, e1, m)}", "maxValue": "{powmod(am, e1, m)}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{powmod(bm, e2, m)}", "maxValue": "{powmod(bm, e2, m)}", "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, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Rechnen Sie im Körper $\\mathbb F_p = \\mathbb Z/\\var{p}$. Geben Sie alle Ergebnisse als Zahlen zwischen $0$ und $\\var{p-1}$ an.
\n$\\var{ap}^{-1} = $ [[0]]
\n$\\frac{\\var{bp}-\\var{cp}}{\\var{ap}} =$ [[1]]
", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{invmod(ap, p)}", "maxValue": "{invmod(ap, p)}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{mod((bp-cp)*invmod(ap,p), p)}", "maxValue": "{mod((bp-cp)*invmod(ap,p), p)}", "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, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "Rechnen Sie im Körper $\\mathbb F_p = \\mathbb Z/\\var{psm}$. Geben Sie alle Ergebnisse als Zahlen zwischen $0$ und $\\var{psm-1}$ an.
\n\nLösen Sie die Gleichung $\\simplify{{apsm}*x + {bpsm} = {cpsm}}$ nach $x$ auf.
\n$x=$ [[0]]
\n\nLösen Sie die Gleichung $\\simplify{{dpsm}*x + {epsm}} = \\frac{1}{\\var{fpsm}}$ nach $x$ auf.
\n$x=$ [[1]]
", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{mod((cpsm-bpsm)*invmod(apsm, psm), psm)}", "maxValue": "{mod((cpsm-bpsm)*invmod(apsm, psm), psm)}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}, {"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{mod((invmod(fpsm, psm)-epsm)*invmod(dpsm, psm), psm)}", "maxValue": "{mod((invmod(fpsm, psm)-epsm)*invmod(dpsm, psm), psm)}", "correctAnswerFraction": false, "allowFractions": false, "mustBeReduced": false, "mustBeReducedPC": 0, "showFractionHint": true, "notationStyles": ["plain", "en", "si-en"], "correctAnswerStyle": "plain"}], "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/"}]}