Anzahl Primteiler

02.06.2012, 21:33

carm561

Auf diesen Beitrag antworten »

Anzahl Primteiler

Meine Frage:
Hallo zusammen,
ich hätte da gern mal ein Problem. Es stammt aus Buchmann, Einführung in die Kryptographie, 2. Auflage, und gehört in den Dunstkreis Miller-Rabin-Test.

In einem Beweis wählt Buchmann ein gewisses $\begin{eqnarray*} m\in\mathbb{N} \end{eqnarray*}$ und definiert damit für

$\begin{eqnarray*} n=\prod_{i=1}^N p_i^{v_i} \end{eqnarray*}$ (das ist die Primfaktorzerlegung von $\begin{eqnarray*} n \end{eqnarray*}$ )

folgende Untergruppen von $\begin{eqnarray*} (\mathbb{Z}/n\mathbb{Z})^* \end{eqnarray*}$

$\begin{eqnarray*} <br /> K= \{ a+n\mathbb{Z}: \gcd(a,n)=1, a^m\equiv \pm 1 \bmod p_i^{v_i} \mbox{\,für alle\,} i \} \\<br /> L= \{ a+n\mathbb{Z}: \gcd(a,n)=1, a^m \equiv \pm 1 \bmod n \}<br /> \end{eqnarray*}$

Dann behauptet er:
Ist der Index von L in K gleich 2, dann hat n genau zwei Primteiler.
Ist der Index von L in K gleich 1, dann ist n Primzahlpotenz.

Meine Ideen:
Definiere $\begin{eqnarray*} \varphi\colon K \to H: = \{1\}\times\{-1,1\}^{N-1} \end{eqnarray*}$
durch $\begin{eqnarray*} \varphi(a) = sign(a^m \bmod p_1^{v_1})(a^m \bmod p_1^{v_1}, \dots , a^m \bmod p_N^{v_N}) \end{eqnarray*}$

$\begin{eqnarray*} sign \end{eqnarray*}$ ist die Vorzeichenfunktion und sorgt dafür, dass die erste Komponenten immer gleich 1 ist.
Mit komponentenweiser Multiplikation ist H eine Gruppe.
Der Kern von $\begin{eqnarray*} \varphi \end{eqnarray*}$ ist $\begin{eqnarray*} L \end{eqnarray*}$ und somit $\begin{eqnarray*} |K/L| = |Bild(\varphi)| \end{eqnarray*}$

Bei surjektivem $\begin{eqnarray*} \varphi \end{eqnarray*}$ ist man fertig, aber eben die Surjektivität kann ich nicht zeigen.

Der Chinesische Restsatz liefert zu beliebigem $\begin{eqnarray*} h\in H \end{eqnarray*}$ ein $\begin{eqnarray*} b \end{eqnarray*}$ mit
$\begin{eqnarray*} b\equiv h_i \bmod p_i^{v_i} \end{eqnarray*}$ für jedes $\begin{eqnarray*} i \end{eqnarray*}$ .

Aber warum gibt es $\begin{eqnarray*} a \end{eqnarray*}$ mit $\begin{eqnarray*} b=a^m \end{eqnarray*}$ ?

03.06.2012, 16:17

Reksilat

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Hi carm561,

Ich finde die Aussage merkwürdig. Setze zum Beispiel m=2. Dann gibt es genügend Primzahlen $\begin{eqnarray*} p_i \end{eqnarray*}$ , für die -1 kein Quadrat ist, d.h. $\begin{eqnarray*} a^m\equiv \pm 1\pmod{p_i}\Leftrightarrow a^m\equiv 1\pmod{p_i} \end{eqnarray*}$ .

Damit sollte sich ein Gegenbeispiel konstruieren lassen.

Gruß,
Reksilat.

03.06.2012, 20:38

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Hi Reksilat.
Danke für deine Antwort, dachte schon, mit mir möchte keiner über meine Probleme reden Augenzwinkern

Augenzwinkern

Ich teile deine Skepsis, aber wenn $\begin{eqnarray*} \varphi \end{eqnarray*}$ nicht surjektiv ist, habe ich keine Ahnung, wie ich Buchmanns Behauptung zeigen soll.
Das $\begin{eqnarray*} m \end{eqnarray*}$ ist wie schon angedeutet allerdings nicht beliebig, sondern wird während des Beweises konstruiert: Setze $\begin{eqnarray*} n-1=2^sd \end{eqnarray*}$ mit ungeradem $\begin{eqnarray*} d \end{eqnarray*}$ . Sei $\begin{eqnarray*} k \end{eqnarray*}$ die größte Zahl in $\begin{eqnarray*} \{0,1,\ldots, s-1\} \end{eqnarray*}$ , für die es ein $\begin{eqnarray*} a \end{eqnarray*}$ mit $\begin{eqnarray*} \gcd (a,n)=1 \end{eqnarray*}$ und $\begin{eqnarray*} a^{2^kd}\equiv -1 \bmod n \end{eqnarray*}$ gibt.

Ich werde es trotzdem mal für den Fall $\begin{eqnarray*} n=65 \end{eqnarray*}$ , also insbesondere $\begin{eqnarray*} d=1 \end{eqnarray*}$ durchrechnen.
Grüße
carm561

aha, warum auch immer funktioniert die Darstellung nicht. Bin aber in Eile, muss ich mir später anschauen.
Gruß

Edit: LaTeX-Tags mit [/latex] statt mit [\latex] schließen. Gruß, Reksilat.

04.06.2012, 09:33

Reksilat

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Jetzt sind noch $\begin{eqnarray*} d \end{eqnarray*}$ , $\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} s \end{eqnarray*}$ hinzugekommen, aber was $\begin{eqnarray*} m \end{eqnarray*}$ sein soll, hast Du noch nicht gesagt. Augenzwinkern

Augenzwinkern

Gruß,
Reksilat.

04.06.2012, 11:05

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler

Zitat:

Original von Reksilat
Jetzt sind noch $\begin{eqnarray*} d \end{eqnarray*}$ , $\begin{eqnarray*} k \end{eqnarray*}$ und $\begin{eqnarray*} s \end{eqnarray*}$ hinzugekommen, aber was $\begin{eqnarray*} m \end{eqnarray*}$ sein soll, hast Du noch nicht gesagt. Augenzwinkern

Augenzwinkern

Ja lustig, das Wichtigste hat er weggelassen, nämlich $\begin{eqnarray*} m=2^kd \end{eqnarray*}$ ... geschockt

geschockt

04.06.2012, 17:53

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Ihr sollt euch nicht über mich lustig machen sondern mein Problem lösen. Grummel Augenzwinkern

Augenzwinkern

Ah, XML-End-Tags statt Latex-Befehl, danke Reksilat. Der Editor hat sogar eine passende Schaltfläche, die ich in der Eile gestern glatt übersehen habe.
Mystic hat mit seiner Definition von $\begin{eqnarray*} m \end{eqnarray*}$ ins Schwarze getroffen.

Anzeige

04.06.2012, 20:12

Reksilat

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Ich bin in der Thematik nicht ganz so bewandert und habe leider gerade auch nicht die Zeit, länger drüber nachzudenken. Ich hoffe also, dass Mystic ein paar Tipps für Dich hat.

Gruß,
Reksilat.

04.06.2012, 21:36

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
@carm561

Mit deinem $\begin{eqnarray*} \varphi \end{eqnarray*}$ kann ich irgendwie nichts anfangen... Warum definierst es nicht so:

$\begin{eqnarray*} \varphi : K \to H: = \{-1,1\}^N \end{eqnarray*}$
$\begin{eqnarray*} a \mapsto sign(a^m \mod n) (a^m \bmod p_1^{v_1},\ldots,a^m \bmod p_N^{v_N}) \end{eqnarray*}$

Damit gilt dann offensichtlich

$\begin{eqnarray*} Kern(\varphi) =L \end{eqnarray*}$

Was ferner deine Frage bez. der Lösbarkeit von

$\begin{eqnarray*} a^m \equiv 1 \mod n \end{eqnarray*}$ bzw. $\begin{eqnarray*} a^m \equiv -1 \mod n \end{eqnarray*}$

betrifft, so brauchst du natürlich die Definition von m dazu, du kannst da nicht einfach irgendein m nehmen, das war wohl ein bißchen sehr naiv von dir gedacht... geschockt

geschockt

Probiers mal selbst mit der nachgereichten Definition von m, bei Unklarheiten helfe ich dir gern weiter... Augenzwinkern

Augenzwinkern

04.06.2012, 22:02

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
So kann man $\begin{eqnarray*} \varphi \end{eqnarray*}$ natürlich auch definieren. Aber das kann dann nicht surjektiv sein, wenn Buchmann recht hat. Es erschien mir günstiger, die Funktion so zu definieren, dass ich nur Surjektivität zeigen muss.
Kannst du bei deiner Definition $\begin{eqnarray*} Bild\, \varphi \end{eqnarray*}$ angeben?

So sehr naiv war das von mir nicht gedacht: Ich kann nicht einmal zeigen, dass es zu $\begin{eqnarray*} h\in H \end{eqnarray*}$ irgendein $\begin{eqnarray*} r \end{eqnarray*}$ gibt, mit $\begin{eqnarray*} b \equiv h_i \bmod p_i^{v_i} \end{eqnarray*}$ und $\begin{eqnarray*} b = a ^r$ \end{eqnarray*}$ .
Ganz zu schweigen davon, dass $\begin{eqnarray*} r=m \end{eqnarray*}$ gilt.

Edit: Hm, dein $\begin{eqnarray*} \varphi \end{eqnarray*}$ könnte doch surjektiv sein. Die erste Komponente von $\begin{eqnarray*} \varphi (a) \end{eqnarray*}$ ist ja auch immer gleich 1.

04.06.2012, 22:31

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Edit2: Vergiss was ich schrieb, bei deiner Defintion von $\begin{eqnarray*} \varphi \end{eqnarray*}$ muss die erste Komponente nicht 1 sein. Für $\begin{eqnarray*} a^m=7, n=12 \end{eqnarray*}$ ist $\begin{eqnarray*} a^m\equiv -1 \bmod 4, a^m\equiv 1 \bmod 3 \end{eqnarray*}$ und $\begin{eqnarray*} sign\, a^m \bmod 12 =1 \end{eqnarray*}$ .

04.06.2012, 22:38

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Ja, ich versteh auch nicht, warum du so "auf die erste Komponente" fixiert bist... Was ist so besonders an ihr? Wir wissen ja rein gar nichts über die Primzahl $\begin{eqnarray*} p_1 \end{eqnarray*}$ , außer dass sie ungerade ist... verwirrt

verwirrt

Edit: Hm, du verwendest n=12 in deinem Beispiel? Du weisst aber schon, dass n für diesen Beweis ungerade sein muss?

04.06.2012, 23:02

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Ah, jetzt verstehe ich, was dich stört.
Ich will mit dem Vorzeichenfaktor nur irgend eine Komponente auf den Wert 1 fixieren. Welche ist mir egal. Die Idee dabei ist, dass meine Zielmenge $\begin{eqnarray*} H \end{eqnarray*}$ genau $\begin{eqnarray*} 2^{N-1} \end{eqnarray*}$ Elemente hat. Bei surjektivem $\begin{eqnarray*} \varphi \end{eqnarray*}$ kann ich dann direkt die Behauptungen von Buchmann ablesen.

Ja, mir ist klar, dass n ungerade sein muss. Nimm stattdessen $\begin{eqnarray*} a^m 11, n=15 \end{eqnarray*}$

05.06.2012, 07:01

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Ich denke, dass durch diesen ganzen Formalismus die doch sehr einfache Grundidee "zugedeckt" wird... Diese besteht einfach darin, dass in den definierenden Eigenschaften der Elemente von K bzw. L, nämlich

$\begin{eqnarray*} K= \{ a+n\mathbb{Z}: \gcd(a,n)=1, a^m\equiv \pm 1 \bmod p_i^{v_i} \mbox{\,für alle\,} i \} \end{eqnarray*}$
$\begin{eqnarray*} L= \{ a+n\mathbb{Z}: \gcd(a,n)=1, a^m \equiv \pm 1 \bmod n \} \end{eqnarray*}$

die Vorzeichenwahl für K bei $\begin{eqnarray*} \pm 1 \end{eqnarray*}$ auf alle $\begin{eqnarray*} 2^N \end{eqnarray*}$ Arten erfolgen kann, während für L nur zwei Fälle zugelassen sind, nämlich alle Werte sind +1 oder alle Werte sind -1... Du siehst nun hoffentlich auch. warum ich $\begin{eqnarray*} \varphi \end{eqnarray*}$ gerade so gewählt habe..

Für die Frage, warum es in K wirklich für jede der möglichen $\begin{eqnarray*} 2^N \end{eqnarray*}$ Vorzeichenwahlen ein a dazu gibt muss man natürlich die speziellen Eigenschaften von m heranziehen: Wir wissen ja, dass es ein a gibt, sodass

$\begin{eqnarray*} a^m \equiv -1 \mod n \end{eqnarray*}$

ist und daher wissen wir auch, dass speziell die Kongruenzen

$\begin{eqnarray*} x^m \equiv -1 \mod p_i^{v_i} \end{eqnarray*}$

für alle i lösbar sind, denn $\begin{eqnarray*} x=a \end{eqnarray*}$ für dieses a ist ja Lösung für alle diese..

08.06.2012, 17:27

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
@Mystic: Also ich komme weder mit deiner noch mit meiner Definition von $\begin{eqnarray*} \varphi \end{eqnarray*}$ weiter. Kannst du bei deiner Definition $\begin{eqnarray*} Bild \varphi \end{eqnarray*}$ angeben?

08.06.2012, 19:50

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler

Zitat:

Original von carm561
@Mystic: Also ich komme weder mit deiner noch mit meiner Definition von $\begin{eqnarray*} \varphi \end{eqnarray*}$ weiter. Kannst du bei deiner Definition $\begin{eqnarray*} Bild \varphi \end{eqnarray*}$ angeben?

Ja, ich fürchte, ich hab mich da auch geirrt... Wo immer du deine Definition von $\begin{eqnarray*} \varphi \end{eqnarray*}$ her hast, aber sie macht jetzt - wo ich mir die Sache doch etwas genauer angesehen habe - durchaus Sinn und ich bin zu ihr (reumütig!) zurückgekehrt... unglücklich

unglücklich

Ich habe nachfolgend den Fall $\begin{eqnarray*} n=65=5\cdot 13 \end{eqnarray*}$ mal im Detail durchgerechnet und das sollte dann auch alle Fragen bisher dann beantworten... Falls noch welche übrig bleiben, dann melde dich einfach wieder...

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:

n:=65: ifactor(n);
                             (5) (13)
J:=select(proc(a) evalb(a&^(n-1) mod n=1) end,[$1..n]);
                           [1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64] 
select(proc(a) evalb(mods(a^((n-1)/2),n)=-1) end, J);
                                [] 
select(proc(a) evalb(mods(a^((n-1)/2^2),n)=-1) end, J);
                                [] 
select(proc(a) evalb(mods(a^((n-1)/2^3),n)=-1) end, J);
                                [] 
select(proc(a) evalb(mods(a^((n-1)/2^4),n)=-1) end, J);
                                []
select(proc(a) evalb(mods(a^((n-1)/2^5),n)=-1) end, J);
                         [8, 18, 47, 57]
m:=(n-1)/2^5;
                                2
K:=select(proc(a) evalb(mods(a^m,5) in [1,-1] and mods(a^m,13) in [1,-1]) end,J);
                           [1, 8, 12, 14, 18, 21, 27, 31, 34, 38, 44, 47, 51, 53, 57, 64] 
L:=select(proc(a) evalb(mods(a^m,5) in [1,-1] and mods(a^m,5)=mods(a^m,13)) end,J);
                           [1, 8, 14, 18, 47, 51, 57, 64] 
f:=a->mods(a^m,5)*[mods(a^m,5),mods(a^m,13)];         
f~(K); 
[[1, 1], [1, 1], [1, -1], [1, 1], [1, 1], [1, -1], [1, -1], [1, -1], [1, -1], [1, -1], [1, -1], [1, 1], [1, 1], [1, -1],  [1, 1], [1,1]

09.06.2012, 00:01

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Allem Anschein nach bin ich zu dusselig. Mir ist nicht einmal klar, was du in Zeile 3 als J berechnest.
Die volle $\begin{eqnarray*} (\mathbb{Z}/65\mathbb{Z})^* \end{eqnarray*}$ ist es jedenfalls nicht, denn die hat bekanntlich 48 Elemente.
Ist das eine schlaue Repräsentierung davon bzw. warum kann man die fehlenden Elemente für die weitere Betrachtung einfach weglassen?

09.06.2012, 07:50

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler

Zitat:

Original von carm561
Die volle $\begin{eqnarray*} (\mathbb{Z}/65\mathbb{Z})^* \end{eqnarray*}$ ist es jedenfalls nicht, denn die hat bekanntlich 48 Elemente.

Hm, warum hast du nicht einfach für ein einziges "fehlendes" Element a, z.B. a=2 nachgerechnet, dass wirklich

$\begin{eqnarray*} a^{64} \not \equiv 1 \mod 65 \end{eqnarray*}$

gilt? verwirrt

verwirrt

Offenbar hast du irgendwo im Hinterkopf die Beziehung

$\begin{eqnarray*} \varphi(n)=n-1 \end{eqnarray*}$

die aber bekanntlich nur für primes n gilt... geschockt

geschockt

09.06.2012, 12:02

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Dann andersherum gefragt, warum kannst du dich auf Elemente beschränken, für die $\begin{eqnarray*} a^{64} \equiv 1 \bmod 65 \end{eqnarray*}$ gilt? In der Definition von $\begin{eqnarray*} K, L \end{eqnarray*}$ steht $\begin{eqnarray*} \gcd(a,n)=1 \end{eqnarray*}$ und das ist etwas anderes.

09.06.2012, 13:53

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler

Zitat:

Original von carm561
Dann andersherum gefragt, warum kannst du dich auf Elemente beschränken, für die $\begin{eqnarray*} a^{64} \equiv 1 \bmod 65 \end{eqnarray*}$ gilt? In der Definition von $\begin{eqnarray*} K, L \end{eqnarray*}$ steht $\begin{eqnarray*} \gcd(a,n)=1 \end{eqnarray*}$ und das ist etwas anderes.

Naja, unser Ziel ist ja für eine ungerade zusammengesetzte Zahl n>1 den Anteil der falschen Zeugen in {1,2,...,n-1} nach oben hin abzuschätzen... Und jeder falsche Zeuge a erfüllt nun einmal die Kongruenz

$\begin{eqnarray*} x^{n-1} \equiv 1 \mod n \quad (*) \end{eqnarray*}$

denn der Miller-Rabin-Test ist ja bekanntlich nur eine Verschärfung des Fermattests, der auf dem "Kleinen Fermat" angewandt auf n für die Basis a beruht... D.h. also, die falschen Zeugen bilden jedenfalls eine Teilmenge von dem J, das aus allen a besteht, welche (*) erfüllen...Und ich hoffe, du siehst auch sofort, dass die Bedingung (*) für ein a automatisch auch ggT(a,n)=1 zur Folge hat, d.j., J ist seinerseits Teilmenge von $\begin{eqnarray*} \mathbb{Z}^* \end{eqnarray*}$ ...

Und ja, es gibt da noch ein weiteres Problem, das dich seit Beginn dieses Threads verfolgt, und das besteht darin, dass du einfach die wichtige Rolle von m aufgrund seiner überaus speziellen Gestalt konsequent unterschätzt...Diese spezielle Gestalt ist

$\begin{eqnarray*} m= \frac{n-1}{2^j} \end{eqnarray*}$

wobei $\begin{eqnarray*} j \in \mathbb N \end{eqnarray*}$ kleinstmöglich gewählt ist, sodass die Kongruenz

$\begin{eqnarray*} x^m \equiv -1 \mod n \quad (**) \end{eqnarray*}$

eine Lösung hat...Aufgrund dieser Wahl von m liegt dann jedes Element von K auch automatisch in J, denn man muss, um das zu sehen, ja nur die definierenden Kongruenzen von K j-mal quadrieren (beachte dabei auch, dass j>0 ist!)...

Kannst du mal checken, ob dir das soweit klar ist?

09.06.2012, 14:25

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Du hast einfach die Definition von $\begin{eqnarray*} J \end{eqnarray*}$ von Buchmann abgeschrieben.
Bei Buchmann steht ausführlich $\begin{eqnarray*} M\subset L \subset K \subset J \subset (\mathbb{Z}/n\mathbb{Z})^* \end{eqnarray*}$ und ja, das ist mir alles klar.
Einem Beweis der ursprünglichen Aussage bin ich aber noch keinen Schritt näher.
Also mal Klartext: Hast du eine Beweis oder nicht?

09.06.2012, 16:16

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler

Zitat:

Original von carm561
Du hast einfach die Definition von $\begin{eqnarray*} J \end{eqnarray*}$ von Buchmann abgeschrieben.

Merk dir bitte eines: Ich habe es nicht notwendig, von Buchmann oder irgendjemanden sonst etwas abzuschreiben... Aber es ist richtig, dass ich mich an den Bezeichnungen in seinem Beweis orientiert habe, um es dir leichter zu machen... Das hat man nun davon... unglücklich

unglücklich

Zitat:

Original von carm561
Bei Buchmann steht ausführlich $\begin{eqnarray*} M\subset L \subset K \subset J \subset (\mathbb{Z}/n\mathbb{Z})^* \end{eqnarray*}$ und ja,
das ist mir alles klar.

Hm, eben noch klang es anders, nämlich so:

Zitat:

Original von carm561
Allem Anschein nach bin ich zu dusselig. Mir ist nicht einmal klar, was du in Zeile 3 als J berechnest. Die volle $\begin{eqnarray*} (\mathbb{Z}/65\mathbb{Z})^* \end{eqnarray*}$ ist es jedenfalls nicht, denn die hat bekanntlich 48 Elemente.

Woher diese plötzliche "Erleuchtung"? verwirrt

verwirrt

Zitat:

Original von carm561
Einem Beweis der ursprünglichen Aussage bin ich aber noch keinen Schritt näher.

Mag sein, ist aber jetzt nicht unbedingt meine Schuld... geschockt

geschockt

Zitat:

Original von carm561
Also mal Klartext: Hast du eine Beweis oder nicht?

Ok, dann auch von meiner Seite Klartext: Natürlich habe ich den Beweis, inzwischen ja sogar mit deinem Homomorphismus $\begin{eqnarray*} \varphi \end{eqnarray*}$ , obwohl ich das vorher noch nicht so kannte... Die Frage sollte also eher lauten, ob ich ihn dir unter diesen Umständen noch mitteilen will... Ich denke, die Antwort darauf sollte dir aber jetzt nicht ganz so schwer fallen, wie manches andere hier... unglücklich

unglücklich

10.06.2012, 11:56

carm561

Auf diesen Beitrag antworten »

Ich hatte schlicht übersehen, dass dein $\begin{eqnarray*} J \end{eqnarray*}$ sein $\begin{eqnarray*} J \end{eqnarray*}$ ist und ja, es war eine gute Idee von dir, für das Beispiel $\begin{eqnarray*} J \end{eqnarray*}$ statt der vollen Restklassengruppe zu nehmen.
Mir war und ist aber noch immer nicht klar, was das zum Beweis der ursprünglichen Aussage beiträgt. Die Erleuchtung, von der du sprachst, fehlt so gesehen noch immer.

Merk du dir bitte, dass auch ich nicht nötig habe, einen Homomorphismus abzuschreiben.
Wenn du deinen Beweis behalten willst, bitte.
Mag sein, dass du was von Mathe verstehst, aber du bist sicher nicht halb so gut wie du arrogant bist.

10.06.2012, 17:28

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von carm561
Merk du dir bitte, dass auch ich nicht nötig habe, einen Homomorphismus abzuschreiben.

Naja, im Unterschied zu dir hab ich das auch nicht dezidiert behauptet... geschockt

geschockt

Angesichts der einfachen Frage, um die es hier geht, nämlich

Zitat:

Original von carm561
Bei surjektivem $\begin{eqnarray*} \varphi \end{eqnarray*}$ ist man fertig, aber eben die Surjektivität kann
ich nicht zeigen.

Der Chinesische Restsatz liefert zu beliebigem $\begin{eqnarray*} h\in H \end{eqnarray*}$ ein $\begin{eqnarray*} b \end{eqnarray*}$ mit
$\begin{eqnarray*} b\equiv h_i \bmod p_i^{v_i} \end{eqnarray*}$ für jedes $\begin{eqnarray*} i \end{eqnarray*}$ .

Aber warum gibt es $\begin{eqnarray*} a \end{eqnarray*}$ mit $\begin{eqnarray*} b=a^m \end{eqnarray*}$ ?

waren meine Zweifel aber mehr als nur berechtigt...Immerhin ist die Antwort ja für beide Fälle b=-1 und b=1 vollkommen trivial...Im Fall b=-1 wissen wir ja, dass nach Wahl von m die Kongruenz

$\begin{eqnarray*} x^m \equiv -1 \mod n \end{eqnarray*}$

lösbar ist... Ist a eine Lösung davon, so ist dieses a dann auch Lösung von

$\begin{eqnarray*} x^m \equiv -1 \mod p_i^{v_i} \end{eqnarray*}$

Der Fall b=1 ist aber wegen der Lösung x=1 ohnehin klar...

Zitat:

Original von carm561
Mag sein, dass du was von Mathe verstehst, aber du bist sicher nicht halb so gut wie du arrogant bist.

Wie sagt man doch (was du aber vielleicht auch noch lernen musst!): Man soll nicht die Hand beissen, die einen füttert... unglücklich

unglücklich

10.06.2012, 17:59

sulo

Auf diesen Beitrag antworten »

Zitat:

Original von carm561
Mag sein, dass du was von Mathe verstehst, aber du bist sicher nicht halb so gut wie du arrogant bist.

@carm561
Du ahnst vermutlich nicht einmal, wie sehr du dich irrst.

Deine mehrfach gezeigte arrogante Haltung widerspricht der Netiquette hier im Board.

11.06.2012, 19:09

carm561

Auf diesen Beitrag antworten »

@sulo: Mir gefällt der Umgangston auch nicht. Ich will auch gar nicht bestreiten, dass ich Anteil an dieser Entgleisung habe. Aber wenn mich die Hand nicht füttert sondern schlägt – und der Vorwurf der Naivität ist eine Ohrfeige – dann beiße ich eben irgendwann. Ist das nachvollziehbar?

Aus meiner Sicht haben Mystic und ich uns gegenseitig unterstellt, abgeschrieben zu haben, er nennt mich naiv, ich ihn arrogant. Eine gute Stelle, das Kriegsbeil reumütig zu begraben, wie ich finde.

@Mystic: Aus deiner Sicht akzeptabel?

11.06.2012, 23:06

carm561

Auf diesen Beitrag antworten »

also ich verstehe, dass du b=-1 und b=1 in der Form $\begin{eqnarray*} a^m \end{eqnarray*}$ schreiben kannst.
und wenn ich es weiter richtig verstehe, gehört b=-1 zu $\begin{eqnarray*} h=(-1,-1,\ldots , -1) \end{eqnarray*}$ , das wegen der negativen ersten Komponente gar nicht in $\begin{eqnarray*} H \end{eqnarray*}$ ist. Soweit richtig?
Entsprechend gehört b=1 zu $\begin{eqnarray*} h=(1,1,\ldots , 1) \end{eqnarray*}$ .
Was ich nicht verstehe ist, wie du mit diesen beiden Fällen z.B das Element $\begin{eqnarray*} (1,-1,1,-1,\ldots)\in H \end{eqnarray*}$ erledigst. verwirrt

verwirrt

12.06.2012, 00:36

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von carm561
Was ich nicht verstehe ist, wie du mit diesen beiden Fällen z.B das Element $\begin{eqnarray*} (1,-1,1,-1,\ldots)\in H \end{eqnarray*}$ erledigst. verwirrt

verwirrt

ok, ich rechne dazu ein etwas größeres Beispiel, nämlich n=561, wo man das besser sieht:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:

n:=561:ifactor(n);
                          (3) (11) (17)  
# Suchen zuerst passendes m der Form m=(n-1)/2^j, j in {1,2,3,4}
# mit kleinstmöglichem j
                          
m:=(n-1)/2:select(proc(x) mods(x^m,n)=-1 end,[$1..n]); 
                             [] 
m:=(n-1)/2^2:select(proc(x) mods(x^m,n)=-1 end,[$1..n]);
                                [] 
m:=(n-1)/2^3:select(proc(x) mods(x^m,n)=-1 end,[$1..n]);
                                [] 
m:=(n-1)/2^4:select(proc(x) mods(x^m,n)=-1 end,[$1..n]);
                     [50, 101, 305, 458, 560] 
a:=50: # Eine der Lösungen von x^m=-1 mod n
 
f:=x->mods(x^m,3)*[mods(x^m,3),mods(x^m,11),mods(x^m,17)]:  # Dein phi  :)  
  
g:=v -> chrem([v[1],v[2],v[3]],[3,11,17]): #Hilfsfunktion
#Bildet Tripel v=(v_1,v_2,v_3) auf  die Lösung von 
#x=v_1 mod 3, x=v_2 mod 11, x=v_3 mod 17 ab 
#chrem(v,[3,11,17])=Maple-Routine für chin. Restsatz mit Moduln 3,11,17 

#Zeige nun, dass f surjektiv ist, indem ich die Komposition (fog)(A)  
#für die nachfolgende Liste A bilde 

A:=[[1,1,1],[1,1,a],[1,a,1],[1,a,a],[a,1,1],[a,1,a],[a,a,1],[a,a,a]]:  
(f@g)~(A);  
[[1, 1, 1], [1, 1, -1], [1, -1, 1], [1, -1, -1], [1, -1, -1],[1, -1, 1], [1, 1, -1], [1, 1, 1]]

Hab den Maple-Code ein bißchen kommentiert... Daraus sollte eigentlich die Anwort auf deine Frage ablesbar sein... Findest du dich damit zurecht?

P.S.: Zu dem, was du oben geschrieben hast, möchte ich nur sagen, dass dies deine Sicht der Dinge ist und ich um des lieben Friedens willen nicht im Detail darauf eingehen werde (jeder der den Thread mitliest kann sich ohnehin sein eigenes Urteil bilden)...

Eine einzige Anmerkung dazu aber dennoch: "Naiv" hat für mich - und ich habe mich da extra im Internet versichert, dass dies auch stimmt- die Hauptbedeutung von "blauäugig" bzw. "gutgläubig"...Wenn ich sage, es ist naiv anzunehmen, dass man für diesen Beweis ohne die speziellen Eigenschaften von m auskommt, so ist dies keine Aussage über dich als Person allgemein, sondern heißt, dass du in diesem speziellen Fall eine "zu einfache Sicht" der Dinge hast... Was ist daran so fürchterlich? verwirrt

verwirrt

12.06.2012, 10:44

carm561

Auf diesen Beitrag antworten »

Ich habe es eben als Aussage über meine Person aufgefasst und dabei den Duden im Kopf gehabt, der naiv mit kindlich und einfältig gleichsetzt. Das kam dann nicht gut an.
Das Beispiel schaue ich mir später an. Danke einstweilen.

12.06.2012, 11:08

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Übrigens haben ich inzwischen eingesehen, dass mein Mißtrauen bezüglich deiner Autorschaft von $\begin{eqnarray*} \varphi \end{eqnarray*}$ , wie hier definiert

Zitat:

Original von carm561
Definiere $\begin{eqnarray*} \varphi\colon K \to H: = \{1\}\times\{-1,1\}^{N-1} \end{eqnarray*}$
durch $\begin{eqnarray*} \varphi(a) = sign(a^m \bmod p_1^{v_1})(a^m \bmod p_1^{v_1}, \dots , a^m \bmod p_N^{v_N}) \end{eqnarray*}$

$\begin{eqnarray*} sign \end{eqnarray*}$ ist die Vorzeichenfunktion und sorgt dafür, dass die erste Komponenten immer gleich 1 ist.

sehr wahrscheinlich unberechtigt war... Ein "Profi" hätte nämlich sofort gesehen, dass man die signum-Funktion hier gar nicht braucht, da der kleinste Absolutrest der ersten Komponente ohnehin nur $\begin{eqnarray*} \pm 1 \end{eqnarray*}$ sein kann... Augenzwinkern

Augenzwinkern

12.06.2012, 11:12

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Da hat meine Ungenauigkeit doch noch etwas gutes smile

smile

Im maple code hast du es ja schon weggelassen.
Habs verstanden, Zeile 26 fehlte mir. Danke

12.06.2012, 11:33

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Eines würde mich aber doch noch interessieren, da ich den Beweis des Satzes von Rabin-Monier wie meine Westentasche kenne (oder soll ich jetzt sagen, zu kennen glaubte Big Laugh

Big Laugh

) und ich selber schon unzählige Male darüber vorgetragen habe: Wozu in aller Welt brauchst du dein $\begin{eqnarray*} \varphi \end{eqnarray*}$ überhaupt?...

Das übliche Argument ist doch (und so macht's ja, glaube ich, auch der Buchmann), dass die Quadrate von K in

$\begin{eqnarray*} M= \{ a+n\mathbb{Z}: \gcd(a,n)=1, a^m \equiv 1 \bmod n \} \end{eqnarray*}$

liegen müssen, d.h., K/M ist eine abelsche Gruppe mit Exponenten 2 und die Ordnung von K/M daher eine Potenz von 2...Wegen dem 2. Isomorphiesatz für Gruppen, d.h.,

$\begin{eqnarray*} K/L =(K/M)/(L/M) \end{eqnarray*}$

gilt das dann auch für K/L selbst... Dabei tritt der Fall K=L genau dann ein, wenn n eine Primzahlpotenz ist...

Was genau gefällt dir an diesem Argument nicht bzw. ist dir unklar? verwirrt

verwirrt

Edit: Übrigens würde ich in den Definitionen von J,K,L und M die Bedingung ggT(a,n)=1 überall weglassen, da ja die jeweils zweite Bedingung viel stärker ist... Allerdings steht das auch bei Buchmann so ...Warum, das weiß vermutlich nicht einmal er selber... Big Laugh

Big Laugh

12.06.2012, 12:01

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
Ich wollte das ganze mit den Mitteln machen, die Buchmann vorher bereitgestellt hat. Der 2. Isomorphiesatz gehört nicht dazu. Dass die Ordnung von K/M eine Potenz von 2 ist habe ich dann aber auch nur hinbekommen, indem ich mich letztlich auf den 1. Sylowschen Satz berufe - der natürlich auch nicht da war.
Hat man die Ordnung von K/M, dann ergibt sich aus |K/M|=|K/L| |L/M| - was eine Verallgemeinerung von Lagrange ist und ich mir deshalb erlaubt habe Augenzwinkern

Augenzwinkern

- auch die Ordnung von K/L als Potenz von 2.
Von da aus kam ich eben nicht anders an N als mit dem $\begin{eqnarray*} \varphi \end{eqnarray*}$ .

Edit: Vielleicht ein Zugeständnis von Buchmann an die naiven Augenzwinkern

Augenzwinkern

12.06.2012, 12:06

Mystic

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler

Zitat:

Original von carm561
Dass die Ordnung von K/M eine Potenz von 2 ist habe ich dann aber auch nur hinbekommen, indem ich mich letztlich auf den 1. Sylowschen Satz berufe - der natürlich auch nicht da war.
[/latex].

Endliche Gruppen mit Exponent 2 sind

1. abelsch (das weiß man hier aber ohnehin)
2. endlichdimensionale Vektorräume über $\begin{eqnarray*} \mathbb{Z}_2 \end{eqnarray*}$ ...

Speziell aus 2. folgt dann, nach Wahl einer Basis, dass die Ordnung eine Potenz von 2 ist... Augenzwinkern

Augenzwinkern

16.06.2012, 21:03

carm561

Auf diesen Beitrag antworten »

RE: Anzahl Primteiler
ah. sorry, hatte nicht damit gerechnet, dass du nochmal schreiben würdest u deswegen nicht mehr in den thread reingeschaut.

öh, ja, das mit dem VR ist sehr schick Big Laugh

Big Laugh

Danke

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »