// Numbas version: exam_results_page_options {"name": "Quadratische Gleichungen in $\\mathbb F_p$", "extensions": [], "custom_part_types": [], "resources": [], "navigation": {"allowregen": true, "showfrontpage": false, "preventleave": false, "typeendtoleave": false}, "question_groups": [{"pickingStrategy": "all-ordered", "questions": [{"name": "Quadratische Gleichungen in $\\mathbb F_p$", "tags": [], "metadata": {"description": "

Questions around quadratic equations over finite fields of the form $\\mathbb F_p$, $p$ a prime number.

", "licence": "Creative Commons Attribution 4.0 International"}, "statement": "

Aufgaben rund um das Thema \"quadratische Gleichungen\" mit Koeffizienten in einem Körper der Form $\\mathbb F_p$ ($p$ eine Primzahl).

", "advice": "

Es ist hier am besten, alle Quadratzahlen in $\\mathbb F_{\\var{p1}}$ zu berechnen: $0^2 = 0$, $1^2 = 1$, $2^2 = 4$, $\\dots$, $\\var{(p1-1)/2}^2 = \\var{mod(((p1-1)/2)^2, p1)}$. Danach wiederholen sich die Werte, weil $\\var{(p1+1)/2}^2 = (-\\var{(p1+1)/2})^2 = \\var{(p1-1)/2}^2$, usw. Insbesondere: Wenn man den ersten Wert gefunden hat, ist die zweite Antwort dessen Negatives (in $\\mathbb F_{\\var{p1}}$).

Hier ist auch (mit dem momentanen Kenntnisstand) Ausprobieren am einfachsten, und machbar, weil wie in Teil a) erklärt nur $\\var{(p2+1)/2}$ Werte berechnet werden müssen (und von denen sind die Quadrate von $0$, $1$, $2$ und $3$ direkt klar). Man erhält als die Menge aller Quadrate in $\\mathbb F_{\\var{p2}}$ die Menge $\\var{squares}$, und als die Menge aller Nicht-Quadrate die Menge $\\var{nonsquares}$. Jedes Element dieser zweiten Menge ist also eine richtige Antwort.

Ergänzung: Für größere Primzahlen ist das Quadratische Reziprozitätsgesetz, dessen ersten Beweis Gauß um 1800 veröffentlichte, die Methode der Wahl, ob ein Element $x\\in\\mathbb F_p$ das Quadrat eines anderen Elements ist, oder nicht. Das ist aber ein Thema für die Algebra oder die Algebraische Zahlentheorie.

Gegeben ist die Gleichung $x^2 + \\var{mod(-c1-c2, p3)} x + \\var{mod(c1*c2, p3)} = 0$ über $\\mathbb F_{\\var{p3}}$.

Wir verwenden die Methode der quadratischen Ergänzung.

Zunächst gilt in $\\mathbb F_{\\var{p3}}$, dass $\\frac 12 = \\var{(p3+1)/2}$, denn das Produkt $2\\cdot \\var{(p3+1)/2}$ in $\\mathbb F_{\\var{p3}}$ ist $1$.

Wir schreiben die gegebene Gleichung also wie üblich um als

\\[\\left(x + \\frac{ \\var{mod(-c1-c2, p3)} }{2}\\right)^2 = \\left(\\frac{ \\var{mod(-c1-c2, p3)} }{2}\\right)^2 - \\var{mod(c1*c2, p3)},\\]

das bedeutet (wenn wir $\\frac 12 = \\var{(p3+1)/2}$ ausnutzen - im konkreten Fall hier ist $\\var{mod(-c1-c2, p3)}$ eine gerade Zahl, also gilt $2 \\cdot \\var{mod(-c1-c2, p3)/2} = \\var{mod(-c1-c2, p3)}$ in $\\mathbb Z$ und damit auch in $\\mathbb F_{\\var{p3}}$, Sie können daher in diesem Fall auch direkt $\\frac{ \\var{mod(-c1-c2, p3)} }{2}$ durch $\\var{mod(-c1-c2, p3)/2}$ ersetzen; das vereinfacht die Rechnung etwas):

\\[\\left(x + \\var{mod((-c1-c2)*(p3+1)/2, p3)} \\right)^2 = \\var{(p3+1)/2}^2\\cdot \\var{mod(-c1-c2, p3)}^2 - \\var{mod(c1*c2, p3)},\\]

Nun gilt $\\var{(p3+1)/2}^2 \\cdot \\var{mod(-c1-c2, p3)}^2 - \\var{mod(c1*c2, p3)} = \\var{mod(((c1+c2)*(p3+1)/2)^2 - c1*c2, p3)}$, und die Quadratwurzeln von diesem Ausdruck in $\\mathbb F_{\\var{p3}}$ sind $\\var{mod((c1-c2)*(p3+1)/2, p3)}$ und $\\var{mod((c2-c1)*(p3+1)/2, p3)}$.

Wir erhalten also als Lösungen die Werte $-\\var{mod((-c1-c2)*(p3+1)/2, p3)} + \\var{mod((c1-c2)*(p3+1)/2, p3)} = \\var{c1}$ und $-\\var{mod((-c1-c2)*(p3+1)/2, p3)} + \\var{mod((c2-c1)*(p3+1)/2, p3)} = \\var{c2}$.

", "rulesets": {}, "extensions": [], "variables": {"p1": {"name": "p1", "group": "Part a)", "definition": "random(11, 13, 17, 19)", "description": "", "templateType": "anything"}, "a1": {"name": "a1", "group": "Part a)", "definition": "random(2..p1-2)", "description": "", "templateType": "anything"}, "p2": {"name": "p2", "group": "Part b)", "definition": "random([7, 11, 13, 17])", "description": "", "templateType": "anything"}, "squares": {"name": "squares", "group": "Part b)", "definition": "set(map(mod(x^2, p2), x, 0..p2-1))", "description": "", "templateType": "anything"}, "nonsquares": {"name": "nonsquares", "group": "Part b)", "definition": "set(0..p2-1) - squares", "description": "", "templateType": "anything"}, "p3": {"name": "p3", "group": "Part c)", "definition": "random(11, 13, 17, 19, 23)", "description": "", "templateType": "anything"}, "c1": {"name": "c1", "group": "Part c)", "definition": "random(1..p3-1)", "description": "", "templateType": "anything"}, "c2": {"name": "c2", "group": "Part c)", "definition": "random(1..p3-1 except [c1, p3-c1])", "description": "", "templateType": "anything"}, "s1": {"name": "s1", "group": "Part c)", "definition": "if(mod(((c1+c2)*(p3+1)/2)^2 - c1*c2, p3) in [1, 4, 9, 16, 25, 36, 49], int(sqrt(mod(((c1+c2)*(p3+1)/2)^2 - c1*c2, p3))), 0)", "description": "

Detect whether mod(((c1+c2)*(p3+1)/2)^2 - c1*c2, p3) is a square in $\\mathbb Z$, and in that case let $s1$ be its square root in $\\mathbb N$. Otherwise $s1$ is $0$.

", "templateType": "anything"}, "c1pc2even": {"name": "c1pc2even", "group": "Part c)", "definition": "2 | mod(-c1-c2, p3)", "description": "", "templateType": "anything"}, "cp": {"name": "cp", "group": "Part c)", "definition": "mod(-c1-c2, p3)", "description": "", "templateType": "anything"}, "cq": {"name": "cq", "group": "Part c)", "definition": "mod(c1*c2, p3)", "description": "", "templateType": "anything"}}, "variablesTest": {"condition": "!(mod(a1^2, p1) in [1, 4, 9, 16, 25])", "maxRuns": 100}, "ungrouped_variables": [], "variable_groups": [{"name": "Part a)", "variables": ["p1", "a1"]}, {"name": "Part b)", "variables": ["p2", "squares", "nonsquares"]}, {"name": "Part c)", "variables": ["p3", "c1", "c2", "s1", "c1pc2even", "cp", "cq"]}], "functions": {}, "preamble": {"js": "", "css": ""}, "parts": [{"type": "gapfill", "useCustomName": false, "customName": "", "marks": 0, "scripts": {"mark": {"script": "var sol1 = Numbas.jme.unwrapValue(this.question.scope.variables.a1);\nvar p = Numbas.jme.unwrapValue(this.question.scope.variables.p1);\nvar sol2 = p - sol1;\n\nvalues = [];\nfor(var i=0; i<2; i++) {\n var v = parseInt(this.studentAnswer[i]);\n if(this.studentAnswer[i].includes(\".\") || isNaN(v)) {\n this.setCredit(0, \"Sie haben nicht 2 ganze Zahlen eingetragen.\");\n return;\n }\n if (v < 0 || v > p-1) {\n this.setCredit(0, \"Bitte geben Sie die Antworten als Zahlen zwischen 0 und \" + p + \" an.\");\n return;\n }\n values.push(v);\n}\n\nthis.answered = true;\n\nif (values[0] == sol1 && values[1] == sol2) {\n this.setCredit(1, \"Prima, richtig gerechnet.\");\n return;\n}\nif (values[0] == sol2 && values[1] == sol1) {\n this.setCredit(1, \"Prima, richtig gerechnet.\");\n return;\n}\nif (values[0] == sol1 || values[0] == sol2) {\n this.setCredit(0.5, \"Die erste angegebene L\u00f6sung ist korrekt, die andere nicht.\");\n return;\n}\nif (values[1] == sol1 || values[1] == sol2) {\n this.setCredit(0.5, \"Die zweite angegebene L\u00f6sung ist korrekt, die andere nicht.\");\n return;\n}", "order": "instead"}}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Wir rechnen in $\\mathbb F_{\\var{p1}}$. Geben Sie die beiden Elemente in $\\mathbb F_{\\var{p1}}$ an, deren Quadrat gleich $\\var{mod(a1^2, p1)}$ ist:

$a = $ [[0]], $b=$ [[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": "{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, "scripts": {}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{p1-a1}", "maxValue": "{p1-a1}", "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": "

Geben Sie ein Element $x$ von $\\mathbb F_{\\var{p2}}$ an, das nicht die Form $a^2$ für $a\\in \\mathbb F_{\\var{p2}}$ hat.

$x=$ [[0]]

", "gaps": [{"type": "numberentry", "useCustomName": false, "customName": "", "marks": 1, "scripts": {}, "customMarkingAlgorithm": "mark:\n if(0 > interpreted_answer or interpreted_answer > p2-1,\n warn(\"Geben Sie eine Zahl zwischen 0 und {p2-1} ein\"),\n correctif(interpreted_answer in nonsquares))", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "minValue": "{nonsquares[0]}", "maxValue": "{nonsquares[0]}", "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": {"mark": {"script": "var sol1 = Numbas.jme.unwrapValue(this.question.scope.variables.c1);\nvar sol2 = Numbas.jme.unwrapValue(this.question.scope.variables.c2);\nvar p = Numbas.jme.unwrapValue(this.question.scope.variables.p3);\n\nvalues = [];\nfor(var i=0; i<2; i++) {\n var v = parseInt(this.studentAnswer[i]);\n if(this.studentAnswer[i].includes(\".\") || isNaN(v)) {\n this.setCredit(0, \"Sie haben nicht 2 ganze Zahlen eingetragen.\");\n return;\n }\n if (v < 0 || v > p-1) {\n this.setCredit(0, \"Bitte geben Sie die Antworten als Zahlen zwischen 0 und \" + p + \" an.\");\n return;\n }\n values.push(v);\n}\n\nthis.answered = true;\n\nif (values[0] == sol1 && values[1] == sol2) {\n this.setCredit(1, \"Prima, richtig gerechnet.\");\n return;\n}\nif (values[0] == sol2 && values[1] == sol1) {\n this.setCredit(1, \"Prima, richtig gerechnet.\");\n return;\n}\nif (values[0] == sol1 || values[0] == sol2) {\n this.setCredit(0.5, \"Die erste angegebene L\u00f6sung ist korrekt, die andere nicht.\");\n return;\n}\nif (values[1] == sol1 || values[1] == sol2) {\n this.setCredit(0.5, \"Die zweite angegebene L\u00f6sung ist korrekt, die andere nicht.\");\n return;\n}", "order": "instead"}}, "customMarkingAlgorithm": "", "extendBaseMarkingAlgorithm": true, "unitTests": [], "showCorrectAnswer": true, "showFeedbackIcon": true, "variableReplacements": [], "variableReplacementStrategy": "originalfirst", "nextParts": [], "suggestGoingBack": false, "adaptiveMarkingPenalty": 0, "exploreObjective": null, "prompt": "

Geben Sie die beiden Lösungen der quadratischen Gleichung $\\simplify[all]{x^2 + {cp} x + {cq}} = 0$ in $\\mathbb F_{\\var{p3}}$ an.

$x_1 = $ [[0]], $x_2 = $ [[1]].

", "stepsPenalty": 0, "steps": [{"type": "information", "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": "

Diese Aufgabe ist ein bisschen aufwändiger. Sie können die Methode der quadratischen Ergänzung verwenden.

Zunächst gilt in $\\mathbb F_{\\var{p3}}$, dass $\\frac 12 = \\var{(p3+1)/2}$, denn das Produkt $2\\cdot \\var{(p3+1)/2}$ in $\\mathbb F_{\\var{p3}}$ ist $1$.

Sie müssen dann (notfalls durch Ausprobieren wie in Teil a)) die beiden Quadratwurzeln von $\\var{(p3+1)/2}^2 \\cdot \\var{mod(-c1-c2, p3)}^2 - \\var{mod(c1*c2, p3)} = \\var{mod(((c1+c2)*(p3+1)/2)^2 - c1*c2, p3)}$ finden. Weil in jedem Körper $a^2 = (-a)^2$ für alle Elemente $a$ gilt, genügt es hier, die Quadrate von $1, 2, \\dots, \\var{(p3-1)/2}$ zu berechnen, denn $\\var{p3-1} = -1$, $\\var{p3-2} = -2$, $\\dots$.

(In diesem konkreten Fall ist allerdings $\\var{mod(((c1+c2)*(p3+1)/2)^2 - c1*c2, p3)}$ eine Quadratzahl on $\\mathbb Z$, daher ist klar, dass die beiden Wurzeln gerade $\\var{s1}$ und $-\\var{s1} = \\var{p3}-\\var{s1} = \\var{p3-s1}$ sind.)

"}], "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": "{c1}", "maxValue": "{c1}", "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": "{c2}", "maxValue": "{c2}", "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/"}]}