Nullstellen im Restklassenring bestimmen

27.12.2011, 19:42

_Kevin_

Nullstellen im Restklassenring bestimmen

Hallo,

ich möchte gerne die Anzahl der Nullstellen von x²-1 im Restklassenring $\begin{eqnarray*} \mathbb{Z}/2006\mathbb{Z} \end{eqnarray*}$ bestimmen.
1 und 2005 sind mir klar. Aber wie bestimme ich die anderen Nullstellen? Könnt ihr mir helfen?

Gruß und Danke im Voraus

27.12.2011, 21:01

wdposchmann

Auf diesen Beitrag antworten »

RE: Nullstellen im Restklassenring bestimmen
Hi,

Zitat:

1 und 2005 sind mir klar.

die 1 ist klar. Die 2005 solltest du dir nochmal überlegen. Die Nullstellen des Polynoms über den ganzen Zahlen sind ja 1 und -1. Da du nun modulo 2006 rechnest, brauchst du also (um erst mal das positive zu betrachten) alle Zahlen, die bei Division durch 2006 den Rest 1 ergeben. Die erste wäre da 2007. Wie geht's dann weiter? Und wie sieht es im Negativen aus?

Gruß

27.12.2011, 21:15

parkerstone

Auf diesen Beitrag antworten »

@wdposchmann:
Die 2005 solltest du dir nochmal überlegen. Erstens sieht man durch nachrechnen dass sie Nullstelle ist, zweitens ist $\begin{eqnarray*} 2005 \equiv -1 \mod 2006 \end{eqnarray*}$ . Auch deine weiteren Anmerkungen zeugen von fröhlicher Unkenntnis der Ringe $\begin{eqnarray*} \mathbb{Z} / n \mathbb{Z} \end{eqnarray*}$ .

@_Kevin_:
Der Trick ist hier chinesischen Restsatz anzuwenden. Und auszunutzen, dass es in Körpern nur maximal zwei Lösungen von X²-1 gibt.

27.12.2011, 21:18

_Kevin_

Auf diesen Beitrag antworten »

Hallo,

danke für Deine Antwort.

Alle Zahlen der Form k*2006 + 1 haben diese Eigenschaft, k eine ganze Zahl ohne die Null. Aber ich sehe noch nicht, worauf du hinaus möchtest. Wenn ich dann ja mod 2006 rechne, habe ich ja im Endeffekt wieder Eins als die Nullstelle, oder etwa nicht?

Ich habe mir zur Hilfe mal ein Programm geschrieben, das mir ausgibt, dass unter anderem eine weitere Nullstelle 1769 ist. Und 2006 - 1769 = 237. Aber diese haben ja nicht die Form k*2006 + 1. Also frage ich mich, wie ich darauf komme ... Vermutlich habe ich aber nur ein riesen Brett vorm Kopf.

Danke nochmals für Deine Bemühungen.

27.12.2011, 21:21

_Kevin_

Auf diesen Beitrag antworten »

@parkerstone:

Das dachte ich eigentlich auch. War mir nur nicht sicher ob ich richtig liege, weil ich ja derjenige bin, der wenig Ahnung von dem Gebiet hat.

Ich überleg mir das mal mit dem chinesischen Restsatz, danke für deine Antwort!

28.12.2011, 16:56

Leopold

Auf diesen Beitrag antworten »

Man könnte auch folgendermaßen vorgehen.

Faßt man die Aufgabe als Problem über $\begin{eqnarray*} \mathbb{Z} \end{eqnarray*}$ auf, dann schreibt sie sich als Kongruenz:

$\begin{eqnarray*} x^2 \equiv 1 \pmod{2006} \ \ \Leftrightarrow \ \ (x-1)(x+1) \equiv 0 \pmod{2006} \end{eqnarray*}$

Zwei Lösungen sind klar: $\begin{eqnarray*} x \equiv \pm 1 \pmod{2006} \end{eqnarray*}$ . Es genügt, Lösungen im Vertreterbereich

$\begin{eqnarray*} V = \{ 0,1,2,\ldots,2005 \} \end{eqnarray*}$

zu bestimmen, da die Lösungen nur modulo $\begin{eqnarray*} 2006 \end{eqnarray*}$ eindeutig sind. In der zweiten Fassung oben unterscheiden sich die Faktoren $\begin{eqnarray*} x-1 \end{eqnarray*}$ und $\begin{eqnarray*} x+1 \end{eqnarray*}$ modulo $\begin{eqnarray*} 2006 \end{eqnarray*}$ um $\begin{eqnarray*} 2 \end{eqnarray*}$ . Zu den bereits gefundenen Lösungen gehören die Faktorenpaare $\begin{eqnarray*} 0,2 \end{eqnarray*}$ (bei $\begin{eqnarray*} x=1 \end{eqnarray*}$ ) und $\begin{eqnarray*} 2004,0 \end{eqnarray*}$ (bei $\begin{eqnarray*} x=2005 \end{eqnarray*}$ ). Für weitere Lösungen sind also ganze Zahlen $\begin{eqnarray*} m,n \in V \setminus \{ 0 \} \end{eqnarray*}$ zu bestimmen mit $\begin{eqnarray*} |m-n| = 2 \end{eqnarray*}$ und

$\begin{eqnarray*} mn \equiv 0 \pmod{2006} \ \ \Leftrightarrow \ \ 2006 \, | \, mn \end{eqnarray*}$

Der Mittelwert von $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ ist dann ein gesuchtes $\begin{eqnarray*} x \end{eqnarray*}$ . (Man kann das auch als die Suche nach Nullteilern im Ring $\begin{eqnarray*} \mathbb{Z} / 2006 \mathbb{Z} \end{eqnarray*}$ auffassen.) Beginnen wir mit der Primfaktorzerlegung

$\begin{eqnarray*} 2006 = 2 \cdot 17 \cdot 59 \end{eqnarray*}$

Das Produkt $\begin{eqnarray*} mn \end{eqnarray*}$ muß nun diese Primteiler enthalten. Daß einer der beiden Faktoren alle drei Primfaktoren enthält, ist wegen $\begin{eqnarray*} m,n \in V \end{eqnarray*}$ nicht möglich. Einer der Faktoren muß daher zwei der Primfaktoren enthalten, nehmen wir dafür $\begin{eqnarray*} m \end{eqnarray*}$ , der andere den dritten.

1. Fall: $\begin{eqnarray*} m \end{eqnarray*}$ enthält die Primfaktoren $\begin{eqnarray*} 2 \end{eqnarray*}$ und $\begin{eqnarray*} 17 \end{eqnarray*}$

Wir suchen also ganze Zahlen $\begin{eqnarray*} r,s \end{eqnarray*}$ mit

$\begin{eqnarray*} \text{(1)} \ \ m = 34r , \ n = 59s \end{eqnarray*}$

$\begin{eqnarray*} \text{(2)} \ \ 1 \leq r \leq 58 , \ 1 \leq s \leq 33 \end{eqnarray*}$

$\begin{eqnarray*} \text{(3)} \ \ 34r - 59s = \pm 2 \end{eqnarray*}$

Die Bedingung $\begin{eqnarray*} \text{(2)} \end{eqnarray*}$ garantiert, daß $\begin{eqnarray*} m,n \in V \setminus \{ 0 \} \end{eqnarray*}$ sind, die Bedingung $\begin{eqnarray*} \text{(3)} \end{eqnarray*}$ , daß $\begin{eqnarray*} |m-n| = 2 \end{eqnarray*}$ ist.

Aus $\begin{eqnarray*} \text{(3)} \end{eqnarray*}$ folgert man, wenn man zu einer Kongruenz modulo $\begin{eqnarray*} 34 \end{eqnarray*}$ übergeht:

$\begin{eqnarray*} 9s \equiv \pm 2 \pmod{34} \end{eqnarray*}$

Modulo $\begin{eqnarray*} 34 \end{eqnarray*}$ ist $\begin{eqnarray*} 19 \end{eqnarray*}$ das multiplikative Inverse von $\begin{eqnarray*} 9 \end{eqnarray*}$ . Das kann man durch Probieren oder mit dem erweiterten euklidischen Algorithmus herausfinden. Multipliziert man die letzte Kongruenz mit $\begin{eqnarray*} 19 \end{eqnarray*}$ , so erhält man

$\begin{eqnarray*} s \equiv \pm 38 \pmod{34} \end{eqnarray*}$

Nehmen wir hier zunächst das Pluszeichen, also $\begin{eqnarray*} s \equiv 4 \pmod{34} \end{eqnarray*}$ . Die einzige Zahl $\begin{eqnarray*} s \end{eqnarray*}$ , die auch noch $\begin{eqnarray*} \text{(2)} \end{eqnarray*}$ erfüllt, ist $\begin{eqnarray*} s=4 \end{eqnarray*}$ . Aus $\begin{eqnarray*} \text{(3)} \end{eqnarray*}$ (mit dem Pluszeichen) kann man jetzt $\begin{eqnarray*} r \end{eqnarray*}$ berechnen, dann mittels $\begin{eqnarray*} \text{(1)} \end{eqnarray*}$ die Zahlen $\begin{eqnarray*} m \end{eqnarray*}$ und $\begin{eqnarray*} n \end{eqnarray*}$ . Ihr Mittelwert ist dann eine Lösung $\begin{eqnarray*} x \end{eqnarray*}$ .

Du kannst das jetzt alleine zu Ende rechnen. Dann mußt du noch den Fall mit dem Minuszeichen in $\begin{eqnarray*} \text{(3)} \end{eqnarray*}$ behandeln. Und zu guter Letzt auch die Fälle, wo $\begin{eqnarray*} m \end{eqnarray*}$ andere Primfaktorenpaare enthält.

Übrigens: Ist $\begin{eqnarray*} x \equiv a \pmod{2006} \end{eqnarray*}$ eine Lösung, so auch $\begin{eqnarray*} x \equiv -a \pmod{2006} \end{eqnarray*}$ . Darüber wäre ein weiterer Zugang zu Lösungen möglich. Mit deinen Lösungen $\begin{eqnarray*} 237 \end{eqnarray*}$ und $\begin{eqnarray*} 1769 \end{eqnarray*}$ hast du das ja bereits vorgeführt.

30.12.2011, 17:33

_Kevin_

Auf diesen Beitrag antworten »

Wow!!! Extrem gute Antwort, dankeschön!

Neue Frage »

Antworten »

Nullstellen im Restklassenring bestimmen

Verwandte Themen