Alle Lösungen einer Gleichung (Modulo)

22.02.2017, 16:37

MathRules

Alle Lösungen einer Gleichung (Modulo)

Hallo Leute,

ich hänge an einer Aufgabe bei der ich einfach keinen Lösungsweg finde:

Berechne alle Lösungen der Gleichung: $\begin{eqnarray*} x^{2} \equiv 1 \mod 15 \end{eqnarray*}$

Wenn die Unbekannte in der Potenz steht, weiß ich wie ich vorgehen muss. Aber bei unbekannter Basis stehe ich momentan auf dem Schlauch. Es muss ja irgendwas mit der Wurzel zu tun haben.
Meine Überlegungen bisher sind: Anwenden des Chinesischen Restsatzes, aber da bin ich leider auch nicht weit gekommen...

Also falls jemand eine Eingebung für mich hätte wäre ich sehr dankbar.

22.02.2017, 16:41

IfindU

Auf diesen Beitrag antworten »

RE: Alle Lösungen einer Gleichung (Modulo)
Offenbar ist mit $\begin{eqnarray*} x \end{eqnarray*}$ auch $\begin{eqnarray*} 15 - x \end{eqnarray*}$ eine Lösung. Das heißt du musst nur gucken welche Zahlen $\begin{eqnarray*} 0, 1, .., 7 \end{eqnarray*}$ die Gleichung erfüllen. Wenn es Theorie gibt (ich weiß dass es welche für Primzahlpotenzen gibt), dann wird sie auch nicht schneller sein.

Edit: Man kann $\begin{eqnarray*} x^2 - 1 = (x-1)(x+1) \end{eqnarray*}$ faktorisieren und dann über Nullteiler von $\begin{eqnarray*} \mathbb Z/ 15\mathbb Z \end{eqnarray*}$ nachdenken. Aber viel schneller wird das auch nicht sein.

22.02.2017, 16:47

MathRules

Auf diesen Beitrag antworten »

Danke schon mal für die Antwort.

Zitat:

Offenbar ist mit $\begin{eqnarray*} x \end{eqnarray*}$ auch $\begin{eqnarray*} 15 - x \end{eqnarray*}$ eine Lösung. Das heißt du musst nur gucken welche Zahlen $\begin{eqnarray*} 0, 1, .., 7 \end{eqnarray*}$ die Gleichung erfüllen

Warum die Werte 0 - 7 ? Und wie wäre es bei einem anderen Exponenten als 2? Mir gehts hier mehr um das allgemeine Verständnis dieser Aufgabentypen. Wie geht man vor wenn man so eine Aufgabe sieht. Falls du da Referenz bzgl Literatur oder Links hast wäre ich sehr dankbar

22.02.2017, 16:54

IfindU

Auf diesen Beitrag antworten »

Die erste Beobachtung ist, dass es ausreicht die Zahlen $\begin{eqnarray*} k = 0, 1,2, \ldots, 14 \end{eqnarray*}$ zu betrachten. Jede Zahl lässt sich nämlich darstellen als Summe von einer dieser Zahlen, und einem Vielfachen von 15. D.h. für jedes $\begin{eqnarray*} n \in \mathbb N \end{eqnarray*}$ gibt es ein $\begin{eqnarray*} l \in \mathbb Z \end{eqnarray*}$ mit $\begin{eqnarray*} n = k + 15\cdot l \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ wie oben. Es folgt aus dem binomischen Lehrsatz, dass $\begin{eqnarray*} n^m = k^m \pmod {15} \end{eqnarray*}$ ist für alle $\begin{eqnarray*} m \in \mathbb N \end{eqnarray*}$ , hier $\begin{eqnarray*} m = 2 \end{eqnarray*}$ . D.h. wenn man die Zahlen aus 0 bis 14 kennt, kann man leicht durch addieren und subtrahieren vom Vielfachen von 15 alle Zahlen bekommen.

Für gerade Exponenten gilt ferner $\begin{eqnarray*} x^m = (15 - x)^m \pmod {15} \end{eqnarray*}$ . Folgt wieder aus dem binomischen Lehrsatz. D.h. statt die Zahlen von 0 bis 14 zu probieren, reicht es sich eine Hälfte davon auszusuchen. So erfüllt 1 offenbar die Gleichung, dann auch $\begin{eqnarray*} 15 - 1 = 14 \end{eqnarray*}$ . Letzteres ist nur aufwendiger auszurechnen, da man dafür $\begin{eqnarray*} 14^2 = 196 \end{eqnarray*}$ ausrechnen muss statt $\begin{eqnarray*} 1^2 = 1 \end{eqnarray*}$ .

Der Trick mit der binomischen Formel ist das einzige halbsystematische was ich kenne, aber ich denke es ist schwer die Gleichung `algebraisch' zu loesen. Aber HAL war wenigstens eben noch online, wenn etwas geht, meldet er sich bestimmt gleich Big Laugh

22.02.2017, 17:16

HAL 9000

Auf diesen Beitrag antworten »

Ich wollte nur was sagen zur Anzahl der Lösungen, gewissermaßen als Kontrollmöglichkeit:

$\begin{align*} x^2\equiv 1\bmod p \end{align*}$ hat genau zwei Lösungen modulo $\begin{align*} p \end{align*}$ , wenn $\begin{align*} p \end{align*}$ ungerade Primzahl ist.

Bei $\begin{align*} x^2\equiv 1\bmod n \end{align*}$ mit quadratfreiem $\begin{align*} n \end{align*}$ hat man dann durch entsprechende Kombination der Primzahlmodulo-Lösungen (chinesischer Restsatz) genau $\begin{align*} 2^r \end{align*}$ Lösungen modulo $\begin{align*} n \end{align*}$ , wobei $\begin{align*} r \end{align*}$ die Anzahl der verschiedenen ungeraden Primfaktoren von $\begin{align*} n \end{align*}$ ist.

Im vorliegenden Fall $\begin{align*} 15=3\cdot 5 \end{align*}$ mit $\begin{align*} r=2 \end{align*}$ sind das demnach genau $\begin{align*} 2^2=4 \end{align*}$ Lösungen.

Ist $\begin{align*} n \end{align*}$ nicht quadratfrei, wird es etwas komplizierter - das wollte ich hier (weil für n=15 irrelevant) nicht auswalzen. Augenzwinkern

EDIT: Ok, hab gerade nochmal rekapituliert, wie das bei beliebigen Primzahlpotenzen ist:

Auch modulo $\begin{align*} p^k \end{align*}$ gibt es bei ungeradem $\begin{align*} p \end{align*}$ nur genau die zwei Lösungen $\begin{align*} x\equiv \pm 1 \mod p^k \end{align*}$ .

Bei $\begin{align*} p=2 \end{align*}$ wird es komplizierter: Im Fall $\begin{align*} k=1 \end{align*}$ gibt's nur die eine Lösung $\begin{align*} x\equiv 1\bmod 2 \end{align*}$ , bei $\begin{align*} k=2 \end{align*}$ genau zwei Lösungen $\begin{align*} x\equiv \pm 1\bmod 4 \end{align*}$ , und für $\begin{align*} k\geq 3 \end{align*}$ gibt es genau vier Lösungen $\begin{align*} x\equiv \pm 1\bmod 2^k \end{align*}$ sowie $\begin{align*} x\equiv \pm \left(2^{k-1}-1\right)\bmod 2^k \end{align*}$ . Augenzwinkern

Neue Frage »

Antworten »

Alle Lösungen einer Gleichung (Modulo)

Verwandte Themen