Kongruenzen

11.06.2007, 23:39

Shadow86

Kongruenzen

Zeigen Sie:

(a) Seien $\begin{eqnarray*} p_1,..., p_k \end{eqnarray*}$ verschiedene Primzahlen. Ist a teilerfremd zu $\begin{eqnarray*} p_1,..., p_k \end{eqnarray*}$ , so hat die Kongruenz $\begin{eqnarray*} x^2\equiv a (mod p_1*...*p_k) \end{eqnarray*}$ entweder keine oder $\begin{eqnarray*} 2^k \end{eqnarray*}$ verschiedene Lösungen.

(b) Seien a ungerade und $\begin{eqnarray*} \alpha \geq3 \end{eqnarray*}$ . Zeigen Sie, dass $\begin{eqnarray*} x^2\equiv a (mod 2^\alpha) \end{eqnarray*}$ genau dann eine Lösung hat, wenn $\begin{eqnarray*} a\equiv 1 (mod 8) \end{eqnarray*}$ gilt.

Hat da jemand einen Vorschlag, wie ich die Sache angehen könnte?

12.06.2007, 09:00

Auf diesen Beitrag antworten »

Zu (a): Da musst du zunächst nachweisen, dass die Kongruenz $\begin{eqnarray*} x^2\equiv a\mod p \end{eqnarray*}$ mit ungerader Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ und $\begin{eqnarray*} a\neq 0 \end{eqnarray*}$ entweder keine oder genau zwei Lösungen hat. Der Rest ist dann chinesischer Restsatz!

Zu (b): Betrachte erstmal alle Reste von $\begin{eqnarray*} x^2 \mod 8 \end{eqnarray*}$ , dann stellt man fest, dass an ungeraden Resten da nur die 1 bleibt, d.h. 3,5,7 nicht möglich sind. Und durch Induktion kannst du die Existenz einer Lösung für $\begin{eqnarray*} a\equiv 1\mod 8 \end{eqnarray*}$ nachweisen, indem du ausgehend von einer Lösung $\begin{eqnarray*} x\mod 2^{\alpha} \end{eqnarray*}$ der Gleichung $\begin{eqnarray*} x^2\equiv a\mod 2^\alpha \end{eqnarray*}$ eine Lösung $\begin{eqnarray*} \tilde{x}\mod 2^{\alpha+1} \end{eqnarray*}$ mit $\begin{eqnarray*} \tilde{x}^2\equiv a\mod 2^{\alpha+1} \end{eqnarray*}$ bastelst. Dazu musst du nur die beiden Möglichkeiten $\begin{eqnarray*} \tilde{x}=x \end{eqnarray*}$ und $\begin{eqnarray*} \tilde{x}=x+2^{\alpha-1} \end{eqnarray*}$ untersuchen...

EDIT: Tipp in der letzten Zeile korrigiert. Augenzwinkern

12.06.2007, 20:46

Shadow86

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Zu (a): Da musst du zunächst nachweisen, dass die Kongruenz $\begin{eqnarray*} x^2\equiv a\mod p \end{eqnarray*}$ mit Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ und $\begin{eqnarray*} a\neq 0 \end{eqnarray*}$ entweder keine oder genau zwei Lösungen hat. Der Rest ist dann chinesischer Restsatz!

Und wie mach ich das mit zweien? Kann ich da überhaupt den chinesischen Restsatz anwenden, wenn ich doch nur eine Kongruenz habe?

zu (b) In diesem Fall muss ich aber auch die umgekehrte Richtung zeigen, wegen "genau dann, wenn..."
Hat da jemand Ahnung, wie das geht?

12.06.2007, 21:23

Auf diesen Beitrag antworten »

Eine Ergänzung zu a):

Dort fehlt als Voraussetzung bei dir noch das Wort "ungerade" für die Primzahlen $\begin{eqnarray*} p_1,\ldots,p_k \end{eqnarray*}$ . Ansonsten wäre die Aussage nämlich falsch.

Zitat:

Original von Shadow86
Und wie mach ich das mit zweien? Kann ich da überhaupt den chinesischen Restsatz anwenden, wenn ich doch nur eine Kongruenz habe?

Jede Einzelkongruenz $\begin{eqnarray*} x^2\equiv a\mod p_i \end{eqnarray*}$ für $\begin{eqnarray*} i=1,\ldots,k \end{eqnarray*}$ hat genau zwei Lösungen, nennen wir sie $\begin{eqnarray*} x_{i,0} \end{eqnarray*}$ und $\begin{eqnarray*} x_{i,1} \end{eqnarray*}$ . Nach chinesischem Restsatz hat jetzt die simultane Kongruenz

$\begin{eqnarray*} x \equiv x_{i,a_i} \mod p_i \end{eqnarray*}$ für $\begin{eqnarray*} i=1,\ldots,k\qquad (*) \end{eqnarray*}$

genau eine Lösung modulo $\begin{eqnarray*} p_1\cdot p_2\cdot \ldots \cdot p_k \end{eqnarray*}$ , dabei seien die $\begin{eqnarray*} a_i\in\{0,1\} \end{eqnarray*}$ beliebig gewählt. Für jedes solcher k-Tupel $\begin{eqnarray*} (a_1,\ldots,a_k) \end{eqnarray*}$ aus Nullen und Einsen hat also (*) genau eine Lösung, und jede dieser Lösungen erfüllt
$\begin{eqnarray*} x^2\equiv a \mod (p_1\cdot\ldots\cdot p_k) \end{eqnarray*}$ . Wieviel solche k-Tupel gibt es denn?

Zitat:

Original von Shadow86
zu (b) In diesem Fall muss ich aber auch die umgekehrte Richtung zeigen, wegen "genau dann, wenn..."
Hat da jemand Ahnung, wie das geht?

"Jemand" hat Ahnung, und hat oben geschrieben, wie's geht. Augenzwinkern

12.06.2007, 22:44

Shadow86

Auf diesen Beitrag antworten »

Zitat:

In der Vorlesung hatten wir aber:
Eine Zahl $\begin{eqnarray*} a \in \mathbb N \end{eqnarray*}$ mit ggT(a,n)=1 - und da in unserem Beispiel jedes $\begin{eqnarray*} p_i \end{eqnarray*}$ prim ist gilt das ja, wenn a ungleich n ist -
heißt quadratischer Rest modulo n, falls $\begin{eqnarray*} x^2 \equiv a (mod n) \end{eqnarray*}$ eine Lösung hat, sonst heißt a quadratischer Nichtrest.

D.h. bei $\begin{eqnarray*} x^2 \equiv a (mod n) \end{eqnarray*}$ - oder mod $\begin{eqnarray*} p_i \end{eqnarray*}$ in unserem Fall - gibt es nur EINE Lösung, keine zwei!!!

Was ist nun richtig?

Und zu (b) Ich sehe da aber nur die Richtung $\begin{eqnarray*} \Rightarrow, nicht \Leftarrow \end{eqnarray*}$ , oder hab ich was falsch verstanden?

12.06.2007, 22:46

Auf diesen Beitrag antworten »

Mit $\begin{eqnarray*} x \end{eqnarray*}$ ist auch $\begin{eqnarray*} -x \end{eqnarray*}$ Lösung, soviel solltest du wissen.

12.06.2007, 22:54

Shadow86

Auf diesen Beitrag antworten »

Also gut, ich gebe mich geschlagen ;-)

Danke, mal sehen, wie's mir weiterhilft...

12.06.2007, 22:56

Auf diesen Beitrag antworten »

Zitat:

Original von Shadow86
Und zu (b) Ich sehe da aber nur die Richtung $\begin{eqnarray*} \Rightarrow, nicht \Leftarrow \end{eqnarray*}$ , oder hab ich was falsch verstanden?

Dann schaust du nicht richtig hin: Nachzuweisen ist für ungerade $\begin{eqnarray*} a \end{eqnarray*}$ :

1.Für $\begin{eqnarray*} a\equiv 1\mod 8 \end{eqnarray*}$ gibt es eine Lösung der genannten Kongruenz.

2.Existiert eine Lösung der genannten Kongruenz, dann ist $\begin{eqnarray*} a\equiv 1\mod 8 \end{eqnarray*}$ .

Oder da $\begin{eqnarray*} (u\Rightarrow v) \end{eqnarray*}$ äquivalent ist zu $\begin{eqnarray*} (\neg v\Rightarrow \neg u) \end{eqnarray*}$ , kann man alternativ zu 2. auch

2'.Für $\begin{eqnarray*} a\neq 1\mod 8 \end{eqnarray*}$ gibt es keine Lösung der Kongruenz.

nachweisen. Logik, Logik, Logik...

Neue Frage »

Antworten »

Kongruenzen

Verwandte Themen