Teilbarkeit einer Funktion

06.04.2016, 19:42

Nicht_Adam_Ries

Teilbarkeit einer Funktion

Meine Frage:
Gegeben sei eine Funktion f(x) = x^2 - 5x + 1, und außerdem eine Primzahl m. Es gilt herauszufinden, für welche Werte x letztlich gilt: f(x) mod m^2 = 0.

Meine Ideen:
Im Bezug auf Teilbarkeit von Polynomen hab ich was von Restklassen gelesen. Allerdings komme ich da nicht wirklich weiter. Es ist auch unzweckmäßig, einfach nur Zahlenwerte auszuprobieren.

06.04.2016, 20:52

tatmas

Auf diesen Beitrag antworten »

Hallo,

bitte gib den exakten Originalwortlaut der Aufgabe an.

So wie es Post formuliert wurde ist die Aufgabe ziemlich sinnfrei (und mit seltsamer Notation).

06.04.2016, 21:03

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Praktisch so, wie es da steht. Gegeben ist die Funktion f(x) = x^2 - 5x + 1 und außerdem eine Primzahl m. Finde x, so dass f(x) mod m^2 = 0, sofern ein x existiert.

Für den Fall m = 2 gibt es bspw. kein x, da f(x) immer ungerade wird und somit nie durch 4 teilbar ist.

06.04.2016, 21:11

tatmas

Auf diesen Beitrag antworten »

Zitat:

Praktisch so, wie es da steht.

Exakter Wortlaut, nicht deine Interpretation davon. Die Nachfrage war nicht zum Spass.

Die Aufgabe so wie sie dasteht würde ich jedem Erstsemester um die Ohren hauen.
Da steht keine Funktion:
Für eine Funktion fehlt Def.bereich und Wertebereich.
Daher ist auch völlig unklar wo x lebt.

Sollte x ganzzahlig sein gibt es nie eines. (wobi eine ganze Zahl mit x zu bezeichnen sehr, sehr selten vorkommt)

06.04.2016, 21:27

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

x ist eine Ganzzahl und sollte nach Möglichkeit >= 5 sein, weil f(x) dann 1 bzw. größer ist.
Beispiel: f(5) = 5^2 - 5*5 + 1 = 25 - 25 + 1 = 1.

Zur Primzahl m. Gesetzt den Fall m = 5, dann ist m^2 = 25. Die Frage ist: Für welches x ist f(x) restfrei durch m^2 teilbar?
Antwort: x = 8. Denn 8^2 - 5*8 + 1 = 64 - 40 + 1 = 25. Und 25 mod 25 = 0.

Die Lösung hierfür habe ich durch einfaches Hochzählen von x gefunden.

Wenn ich m = 11 setze, dann ist m^2 = 121. Wenn ich nun für x egal welchen Wert zwischen 5 und 10.000.000 einsetze, erhalte ich als Ergebnis von f(x) niemals einen Wert, der sich restfrei durch 121 dividieren lässt.

Und nun zurück zur eigentlichen Frage: Wenn ich eine Primzahl m gegeben habe, kann ich dann absehen, ob es ein x gibt, so dass f(x) letztlich durch m^2 restfrei teilbar ist, ohne unzählige Werte von x auszuprobieren?

06.04.2016, 21:35

tatmas

Auf diesen Beitrag antworten »

Zitat:

Und nun zurück zur eigentlichen Frage

Und was ist die jetzt eigentlich?

Zitat:

x ist eine Ganzzahl und sollte nach Möglichkeit >= 5 sein

ist ja eine neue Information.

Es macht keinerlei Sinn hier scheibchenweise "Was ist jetzt wirklich gefragt" zu spielen.

06.04.2016, 21:36

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Ein weiteres Beispiel: m = 17, also m^2 = 289.
Für x = 114 ergibt sich dann f(x) = 114^2 - 5*114 + 1 = 12996 - 570 + 1 = 12427.

Und: 12427 mod 289 = 0, denn 12427 / 289 = 43 Rest 0.

06.04.2016, 21:38

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Zitat:

Original von tatmas

Zitat:

Und nun zurück zur eigentlichen Frage

Und was ist die jetzt eigentlich?

Wenn ich eine Primzahl m gegeben habe, kann ich dann absehen, ob es ein x gibt, so dass f(x) letztlich durch m^2 restfrei teilbar ist, ohne unzählige Werte von x auszuprobieren?

06.04.2016, 21:41

tatmas

Auf diesen Beitrag antworten »

Das ist ein Beispiel, nicht die Aufgabenstellung.
Was ist die exakte Aufgabenstellung?

Kontext wär auch sinnvoll, was für Werkzeuge stehen zur Verfügung? (Jacobi-Symbol z.B.?)

06.04.2016, 21:43

tatmas

Auf diesen Beitrag antworten »

Nicht eher doch evtl.

Zitat:

Wenn ich eine Primzahl m gegeben habe, kann ich dann absehen, ob es eine natürliche Zahl x>4 gibt so, dass f(x) letztlich durch m^2 restfrei teilbar ist, ohne unzählige Werte von x auszuprobieren?

06.04.2016, 21:45

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Es stehen alle Möglichkeiten offen. Und die Beispiele m = 5 und m = 17 sind tatsächlich nur Beispiele. Ich hatte bereits gesagt, dass m eine Primzahl ist. Es könnte also ebenso den Wert 997 oder 10,151 annehmen, solange es eben eine Primzahl ist.

Und die exakte Aufgabenstellung steht schon da.

06.04.2016, 21:50

tatmas

Auf diesen Beitrag antworten »

Was denn jetzt:

Zitat:

Es stehen alle Möglichkeiten offen

oder

Zitat:

Und die exakte Aufgabenstellung steht schon da.

?

Ich wiederhole nochmal meine Frage:

Zitat:

Kontext wär auch sinnvoll, was für Werkzeuge stehen zur Verfügung? (Jacobi-Symbol z.B.?)

Denn damit könnte man schon eine schöne Bedingung aufstellen.

Und man muss maximal m² Zahlen durchprobieren.

06.04.2016, 21:55

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Dann mach das doch mal.

06.04.2016, 21:57

tatmas

Auf diesen Beitrag antworten »

Wie bitte?

06.04.2016, 22:20

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Wir wissen, dass ich nicht weiß, wie ich die Sache angehen soll. Du anscheinend schon. Die Formalitäten zur Aufgabenstellung sind m. E. geklärt. Und ich dachte, du könntest mir, und evtl auch anderen Interessierten aber Unwissenden, einen Hinweis geben, wie man das Problem in den Griff bekommt.

06.04.2016, 22:26

tatmas

Auf diesen Beitrag antworten »

Ich würde dir gerne helfen.
Dazu gehört es aber auch, dass du meine Rückfragen beantwortest.
Denn sonst weiß ich nicht wie ausführlich meine Antworten sein sollen.

06.04.2016, 22:52

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Die Antwort darf gern ausführlich sein, weil ich immer an Hintergrundwissen interessiert bin. Allerdings bin ich kein Matheass, so dass die Erläuterungen auch für weniger Betuchte nachvollziehbar sein sollten, sofern das machbar ist.

06.04.2016, 22:54

HAL 9000

Auf diesen Beitrag antworten »

Die übliche Technik wäre, von $\begin{align*} x^2-5x+1 \end{align*}$ zunächst zu einem vollständigen Quadrat überzugehen, via quadratische Ergänzung - damit man überhaupt erstmal einen Angriffspunkt für die diversen Aussagen über quadratische Reste hat! Als Vorbereitung für diese quadratische Ergänzung nutzt man, dass für ungerade $\begin{align*} m \end{align*}$ die Kongruenz $\begin{align*} x^2-5x+1\equiv 0\bmod m^2 \end{align*}$ äquivalent zu $\begin{align*} 4(x^2-5x+1)\equiv 0\bmod m^2 \end{align*}$ ist...

06.04.2016, 22:59

tatmas

Auf diesen Beitrag antworten »

Eine grobe Idee meines Vorgehens.
Gibt es ein gesuchtes x, so muss es eine Lösung mod m geben, daher muss 21 ein Quadrat mod m sein (siehe Hal9000-Post).
Die Bedingung dafür kann man mittels quadr. Reziprozität relativ einfach hinschreiben.
Hat man die max. 2 Lösungen mod m, nennen wir so a und b so muss x=a+m*l oder =b+m*K gelten wobei k,l<m natürliche Zahlen sind.

07.04.2016, 22:00

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Auf jeden Fall vielen Dank bisher! Könntet ihr eure Vorgehensweise evtl an dem Beispiel m = 11 zeigen?

07.04.2016, 23:14

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von tatmas
Gibt es ein gesuchtes x, so muss es eine Lösung mod m geben, daher muss 21 ein Quadrat mod m sein (siehe Hal9000-Post).
Die Bedingung dafür kann man mittels quadr. Reziprozität relativ einfach hinschreiben.

Wenn du den Weg befolgst, dann kommt am Ende raus, dass es für $\begin{align*} m=11 \end{align*}$ keine Lösung geben kann - allgemeiner sogar für alle Primzahlen $\begin{align*} m\equiv 11\bmod 42 \end{align*}$ nicht.

Schritt für Schritt:

1) Ist dir das mit der 21 oben jetzt klar?

2) Wende das quadratische Reziprozitätsgesetz an, mit dem kannst du $\begin{align*} \left( \frac{21}{m} \right) = \left( \frac{3}{m} \right)\cdot \left( \frac{7}{m} \right) \end{align*}$ mit Hilfe von $\begin{align*} \left( \frac{m}{3} \right) \end{align*}$ und $\begin{align*} \left( \frac{m}{7} \right) \end{align*}$ schreiben.

P.S.: Natürlich geht es nur für $\begin{align*} m=11 \end{align*}$ leichter, man sieht etwa einfach durch Betrachtung aller Reste $\begin{align*} x\equiv -5,-4,\ldots,4,5\bmod 11 \end{align*}$ , dass es keine Lösung gibt. Allerdings bringt dich das nicht gerade entscheidend weiter, was die Gesamtlösung der Aufgabe betrifft.

08.04.2016, 20:29

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Irgendwie klemmt's unglücklich

Ich nehme an die 21 bezieht sich auf m = 11? Wie sieht es dann z.B. für m = 41 aus?

08.04.2016, 20:33

tatmas

Auf diesen Beitrag antworten »

Zitat:

Ich nehme an die 21 bezieht sich auf m = 11?

Nein. Die 21 ist komplett unabhängig von m.

09.04.2016, 08:46

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

@HAL9000: Vielleicht ist es noch zu früh am Morgen, aber die 21 entzieht sich mir noch verwirrt

09.04.2016, 10:25

HAL 9000

Auf diesen Beitrag antworten »

Hast du über meinen Beitrag 06.04.2016 22:54 irgendwie mal nachgedacht, also das mit der quadratischen Ergänzung?

11.04.2016, 18:06

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Zum Beitrag und zur 21 hab ich mir überlegt:
x^2 - 5x +1
--> 4(x^2 - 5x + 1)
--> 4x^2 - 20x + 4
--> (2x - 5)^2 = 4x^2 - 20x + 25

Um dann von 25 wieder zur 4 zu kommen, muss ich 21 subtrahieren. Sollte da diese 21 herkommen? Falls ja, müsste dann für den anderen Fall von z.B f(x) = x^2 - 3x - 1 mit der Vorgehensweise 13 erhalten. Oder?

(Meine Erklärung ist für Mathematiker sicherlich unzureichend und viel zu sehr vereinfacht...)

11.04.2016, 18:40

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Nicht_Adam_Ries
Zum Beitrag und zur 21 hab ich mir überlegt:
x^2 - 5x +1
--> 4(x^2 - 5x + 1)
--> 4x^2 - 20x + 4
--> (2x - 5)^2 = 4x^2 - 20x + 25

Um dann von 25 wieder zur 4 zu kommen, muss ich 21 subtrahieren. Sollte da diese 21 herkommen?

Ja. Wie ich oben geschrieben hatte: $\begin{align*} x^2-5x+1\equiv 0\bmod m^2 \end{align*}$ ist für ungerade m äquivalent zu $\begin{align*} 4(x^2-5x+1) = 4x^2-20x+4 = (2x-5)^2-21\equiv 0\bmod m^2 \end{align*}$ , d.h. $\begin{align*} (2x-5)^2\equiv 21\bmod m^2 \end{align*}$ . Damit eine Lösung überhaupt existieren kann, muss also 21 quadratischer Rest modulo $\begin{align*} m^2 \end{align*}$ sein, und dafür ist wiederum notwendig, dass 21 quadratischer Rest modulo $\begin{align*} m \end{align*}$ ist. Bei ungeraden Primzahlen $\begin{align*} m\neq 3,7 \end{align*}$ ist letzteres aber auch hinreichend für ersteres (wenn ich mich richtig erinnere).

11.04.2016, 20:38

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Deine Aussage von weiter oben: (21/m) = (3/m) * (7/m)... Wenn ich viele m habe, könnte ich dann über das Legendre Symbol die (Nicht-)Teilbarkeit schnell bestimmen? Ich erinnere mich, so was bei Wiki beim Quadratischen Reziprozitätsgesetz gelesen zu haben. Zumindest entspricht dir o.g. Darstellung der von Wikipedia.

11.04.2016, 20:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Nicht_Adam_Ries
Deine Aussage von weiter oben: (21/m) = (3/m) * (7/m)... Wenn ich viele m habe, könnte ich dann über das Legendre Symbol die (Nicht-)Teilbarkeit schnell bestimmen?

Ja, das war der Gedanke dahinter. Augenzwinkern

m=3 und m=7 musst du extra betrachten, aber für alle anderen greift das quadratische Reziprozitätsgesetz.

11.04.2016, 21:06

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Einen Versuch ist es wert Freude

Ich bin noch unschlüssig, wie bei (21/m) dann das Legendre Symbol für alle möglichen primen m aussieht. Aber durch Trial und Error finde ich das sicher raus.

12.04.2016, 13:11

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Ich bin jetzt soweit, dass ich vermute, dass L(a/m) = 1, wenn m ein Teiler von f(x) ist. a ist hier der Subtrahend aus der quadratischen Gleichung. L(a/m) berechne ich durch a^((m-1)/2) mod m.
Sollte das alles stimmen? verwirrt

12.04.2016, 14:17

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Nicht_Adam_Ries
dass L(a/m) = 1, wenn m ein Teiler von f(x) ist. a ist hier der Subtrahend aus der quadratischen Gleichung.

Vielleicht meinst du ja das Richtige, aber so verklausuliert formuliert bleibt fast nix mehr davon übrig.

L(a/m) soll wohl das Legendre-Symbol $\begin{align*} \left( \frac{a}{m} \right) \end{align*}$ darstellen, Ok. Und du redest von a=21, oder? In dem Sinne gilt für alle ungeraden $\begin{align*} m \end{align*}$ :

Es existieren $\begin{align*} x \end{align*}$ mit $\begin{align*} m \mid f(x) \end{align*}$ genau dann wenn $\begin{align*} \left( \frac{21}{m} \right) = 1 \end{align*}$ .

Darüber hatte ich ja zuletzt gesprochen.

Zitat:

Original von Nicht_Adam_Ries
L(a/m) berechne ich durch a^((m-1)/2) mod m.

Obgleich richtig, ist diese Formel für die konkrete Rechnung eher etwas sperrig. Wir haben jetzt wiederholt das quadratische Reziprozitätsgesetz erwähnt - warum setzt du nicht dort mal ein? Damit nimmt die Charakterisierung passender $\begin{align*} m \end{align*}$ deutlich konkretere Züge an.

-------------------------------------------------------------

EDIT: OK, mal etwas schneller vorangeschritten. Gemäß Reziprozitätsgesetz gilt

$\begin{align*} \left( \frac{3}{m} \right) = \left( \frac{m}{3} \right)\cdot (-1)^{\frac{3-1}{2}\cdot \frac{m-1}{2}} = \left( \frac{m}{3} \right)\cdot (-1)^{\frac{m-1}{2}} \end{align*}$

$\begin{align*} \left( \frac{7}{m} \right) = \left( \frac{m}{7} \right)\cdot (-1)^{\frac{7-1}{2}\cdot \frac{m-1}{2}} = \left( \frac{m}{7} \right)\cdot (-1)^{3\frac{m-1}{2}} \end{align*}$

Und dann das Produkt der beiden:

$\begin{align*} \left( \frac{21}{m} \right) = \left( \frac{m}{3} \right) \cdot \left( \frac{m}{7} \right) \cdot (-1)^{4\frac{m-1}{2}} = \left( \frac{m}{3} \right) \cdot \left( \frac{m}{7} \right) \end{align*}$ .

$\begin{align*} \left( \frac{21}{m} \right) =1 \end{align*}$ ergibt sich somit, wenn die Legendre-Symbole rechts beide 1 oder beide -1 sind, in Worten: 21 ist genau dann quadratischer Rest modulo $\begin{align*} m \end{align*}$ , wenn entweder

(a) $\begin{align*} m \end{align*}$ quadratischer Rest sowohl modulo 3 als auch modulo 7 ist, oder

(b) $\begin{align*} m \end{align*}$ quadratischer Nichtrest sowohl modulo 3 als auch modulo 7 ist.

Die 0 außen vor lassend gibt es modulo 3 den quadratischen Rest 1 und den Nichtrest 2, entsprechend modulo 7 die quadratischen Reste 1,2,4 und die Nichtreste 3,5,6. Die entsprechenden Kombinationen

(a) $\begin{align*} m\equiv 1\bmod 3 \end{align*}$ mit $\begin{align*} m\equiv 1,2,4\bmod 7 \end{align*}$ ,

(b) $\begin{align*} m\equiv 2\bmod 3 \end{align*}$ mit $\begin{align*} m\equiv 3,5,6\bmod 7 \end{align*}$

ergeben dann alle möglichen Werte $\begin{align*} m \bmod 21 \end{align*}$ , bzw. da $\begin{align*} m \end{align*}$ eine ungerade Primzahl ist, kann man das dann auch als entsprechende $\begin{align*} m\bmod 42 \end{align*}$ formulieren.

13.04.2016, 08:38

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Das werd ich mal probieren. Für den Fall einer Primzahl anstelle der 21 vereinfacht sich der Vorgang m.E. dann. Weiterführend bleibt für mich dann die Frage, wie ich bei gegebenem m oder vielmehr m^2 dann das/die x berechne. Ich kann mich täuschen, aber wäre Tonelli Shanks dann der Weg?

13.04.2016, 09:23

HAL 9000

Auf diesen Beitrag antworten »

Halten wir fest: Die Frage, für welche Primzahlen $\begin{align*} m \end{align*}$ es Lösungen $\begin{align*} x \end{align*}$ vom $\begin{align*} m^2 \mid f(x) \end{align*}$ gibt, ist mit den obigen Betrachtungen weitgehend gelöst (Ok, die Fälle m=2, m=3 und m=7 müssen noch gesondert geprüft werden, was aber schnell geht), es ergeben sich letztlich sechs Restklassen modulo 42, in denen derartige Primzahlen liegen müssen.

Offen ist die andere Frage, wie die Lösungen $\begin{align*} x \end{align*}$ für solche $\begin{align*} m \end{align*}$ ermittelt werden. Und da muss dir wohl ein anderer (tatmas?) weiterhelfen, ich bin mit meinen Amateurkenntnissen zur Zahlentheorie weitgehend am Ende - Tonelli Shanks sagt mir z.B. gar nichts. Augenzwinkern

13.04.2016, 11:11

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Amateurkenntnisse?

13.04.2016, 11:42

tatmas

Auf diesen Beitrag antworten »

Ja mnateurkenntnisse.
Meine sind auch maximal bessere Amateurkenntnisse.
Das ist das Problem mit dem Einsortieren von seinem Wissen: woran man es misst. Daher fand ich deine Antwort auf meine diesbzgl. Fragen deiner Vorkenntnissse betreffend sehr dürftig (und wie gesagt: wenn ich wüßte worauf aufzubauen ist, ist es einfacher eine nachvollziehbare Antwort zu geben und/oder auf sinnvolle Lektüre zu verweisen. Rein ins blaue zu schreiben hab ich als Amateur, d.h. ich werde dafür nicht bezahlt, keine Lust)

Tonelli-Shanks kann man modulo m verwenden, nicht aber modulo m².
Für Lösungen modulo m² hatte ich bereits einen elementaren Ansatz geschrieben.
Die sinnvollste Lösung ist hier aber wohl ein Hensel-Lift.

13.04.2016, 13:13

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Meine Aussage zum TS Algorithmus muss ich zurücknehmen, da hat tatmas recht. Ich habe eben bei Wiki zum Henselschen Lemma nachgelesen. Es scheint das zu sein was ich suche. Da hilft nur reinfuchsen.

15.04.2016, 17:32

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

Eine kleine Ergänzung... aus den Weblinks zu Wiki "Henselsches Lemma" kommt man zu einem Skript der Uni Stuttgart. Hier verwendet man den Begriff ***modulare Nullstelle***. Ich glaube dieser Begriff beschreibt die Problemstellung ganz gut. Falls jemand weitere Anregungen zur Lösbarkeit im sinne von "Ein-X-Finden hat, sodass f(x) = 0 (mod p)", dann einfach melden.

10.05.2016, 16:37

Nicht_Adam_Ries

Auf diesen Beitrag antworten »

So weit, so gut. Mit dem Hensel Lifting bin ich ein Stück vorangekommen. Ich hab es auch mit verschiedenen anderen Gleichungen und Werten probiert und bin hierbei auf ein weiteres Problem gestoßen: Legen wir in diesem Fall das Polynom f(x) = x^2 - 3x - 1 zugrunde, Primzahl p = 17. Nach dem Verfahren bzgl Hensel Lifting erhalte ich als eine Lösung x = 261, so dass f(x) = 0 (mod p^2). Eine andere, kleinere Lösung ist x = 31.
Ist es nun möglich bei Vorliegen einer Lösung durch diese auf andere Lösungen zu schließen? In diesem Fall: kann ich aus der Lösung 261 auch die Lösung 31 ableiten?

10.05.2016, 17:32

HAL 9000

Auf diesen Beitrag antworten »

Mit $\begin{align*} x \end{align*}$ sind offenbar auch alle $\begin{align*} x+kp^2 \end{align*}$ sowie $\begin{align*} -x+3+kp^2 \end{align*}$ Lösung der Kongruenz $\begin{align*} x(x-3)-1\equiv 0\bmod p^2 \end{align*}$ .

Bezogen auf $\begin{align*} x=261 \end{align*}$ erhält man mit $\begin{align*} p=17,k=-1 \end{align*}$ dann $\begin{align*} -x+3+kp^2 = -261+3+289 = 31 \end{align*}$ .

12 nächste Seite »

Neue Frage »

Antworten »

Teilbarkeit einer Funktion

Verwandte Themen