ggT = 1, Unklarheit in einem Beweis

19.01.2023, 16:09

Malcang

ggT = 1, Unklarheit in einem Beweis

Hallo mal wieder smile

Ich schaue mir aktuell in diesem Paper das Korollar 6.6 an. Hier als Ausschnitt:
[attach]56705[/attach]

Mir ist der Abschnitt nach "Hence" unklar.
Ich sehe natürlich ein, warum $\begin{eqnarray*} q=2 \end{eqnarray*}$ der einzige Primfaktor von $\begin{eqnarray*} F \end{eqnarray*}$ ist. Aber warum ist $\begin{eqnarray*} ggT(a^{\frac{n-1}{2}}, n) = 1 \end{eqnarray*}$ ? verwirrt

19.01.2023, 16:16

IfindU

Auf diesen Beitrag antworten »

RE: ggT = 1, Unklarheit in einem Beweis
Wir haben $\begin{eqnarray*} a^{\frac 1 2 (n-1)} \equiv -1 \bmod n \end{eqnarray*}$ , d.h. $\begin{eqnarray*} n | a^{\frac 1 2 (n-1)} +1 \end{eqnarray*}$ . Jede Zahl, die sowohl $\begin{eqnarray*} n \end{eqnarray*}$ als auch $\begin{eqnarray*} a^{\frac 1 2 (n-1)} \end{eqnarray*}$ teilt, muss auch die 1 teilen.

19.01.2023, 16:28

Malcang

Auf diesen Beitrag antworten »

So oft wie ich mir heute den Hammer schon auf den Kopf hauen musste, sollte ich mich liber hinlegen.

IfindU, ich danke dir! smile

19.01.2023, 16:36

Malcang

Auf diesen Beitrag antworten »

Sorry, ich muss doch noch einmal einhaken.
Der Autor sagt ja jetzt, dass die Vorraussetzungen für den Satz von Pocklington erfüllt sind. Dieser ist direkt davor, sagt aber doch
[attach]56706[/attach]
Es wird hier doch $\begin{eqnarray*} ggT(a^{\frac{n-1}{q}}-1, n) = 1 \end{eqnarray*}$ gefordert und nicht $\begin{eqnarray*} [latex]ggT(a^{\frac{n-1}{q}}, n) = 1 \end{eqnarray*}$ verwirrt

19.01.2023, 16:45

IfindU

Auf diesen Beitrag antworten »

Sei $\begin{eqnarray*} l \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} n \end{eqnarray*}$ . Aus $\begin{eqnarray*} n | a^{\frac 1 2 (n-1)} +1 \end{eqnarray*}$ folgt $\begin{eqnarray*} l | a^{\frac 1 2 (n-1)} +1 \end{eqnarray*}$ . Was folgt, wenn ebenfalls $\begin{eqnarray*} l | a^{\frac 1 2 (n-1)} -1 \end{eqnarray*}$ ?

19.01.2023, 16:53

Malcang

Auf diesen Beitrag antworten »

Ah, ich habe gerade folgendes erkannt:
Aus $\begin{eqnarray*} a^{\frac{n-1}{2}}\equiv -1 \pmod n \end{eqnarray*}$ folgt $\begin{eqnarray*} a^{\frac{n-1}{2}} -1 \equiv -2 \pmod n \end{eqnarray*}$ und damit $\begin{eqnarray*} n|(a^{\frac{n-1}{2}} - 1) + 2 \end{eqnarray*}$ .
Es kann also $\begin{eqnarray*} ggT(a^{\frac{n-1}{2}-1, n} = 1 \end{eqnarray*}$ oder $\begin{eqnarray*} ggT(a^{\frac{n-1}{2}-1, n} = 2 \end{eqnarray*}$ sein.
Im letzteren Falle müsste $\begin{eqnarray*} n \end{eqnarray*}$ gerade sein, was aber nicht stimmt, da $\begin{eqnarray*} n = h\cdot 2^k + 1 \end{eqnarray*}$ ist.

Edit: IfindU, du hast geantwortet, das hat sich gerade überschnitten. Ich muss jetzt hier im Unibistro das Feld räumen, melde mich aber gleich zuhause wieder Big Laugh

19.01.2023, 19:34

Malcangunterwegs

Auf diesen Beitrag antworten »

Hallo,

ich schaffe es wegen Bahn und Bus heute doch leider nicht mehr. Werde mich aber natürlich morgen wieder melden.

Vielen Dank und schönen Abend!

20.01.2023, 08:41

Malcang

Auf diesen Beitrag antworten »

Guten Morgen,

Zitat:

Original von IfindU
Sei $\begin{eqnarray*} l \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} n \end{eqnarray*}$ . Aus $\begin{eqnarray*} n | a^{\frac 1 2 (n-1)} +1 \end{eqnarray*}$ folgt $\begin{eqnarray*} l | a^{\frac 1 2 (n-1)} +1 \end{eqnarray*}$ . Was folgt, wenn ebenfalls $\begin{eqnarray*} l | a^{\frac 1 2 (n-1)} -1 \end{eqnarray*}$ ?

Hm...
Also, es folgt erstmal $\begin{eqnarray*} l|(a^{\frac{n-1}{2}} - 2) + (a^{\frac{n-1}{2}} + 1) = 2a^{\frac{n-1}{2}} \end{eqnarray*}$ und damit $\begin{eqnarray*} l|2 \text{ oder } l|a^{\frac{n-1}{2}}\Rightarrow l|a \end{eqnarray*}$ .
Ersteren Fall kann ich ja mit n ungerade direkt ausschließen, also ist l = 1.
Aber für den zweiten Fall? Bin ich denn noch zu müde? verwirrt

20.01.2023, 08:46

IfindU

Auf diesen Beitrag antworten »

Ich habe nichts mehr geschrieben, weil du auf gleiche selbst gekommen bist.

Zitat:

Aus $\begin{eqnarray*} l | a^{\frac 1 2 (n-1)} +1 \end{eqnarray*}$ und $\begin{eqnarray*} l | a^{\frac 1 2 (n-1)} -1 \end{eqnarray*}$ folgt $\begin{eqnarray*} l | \Big( a^{\frac 1 2 (n-1)} +1 \Big) - \Big( a^{\frac 1 2 (n-1)} -1\Big) = 2 \end{eqnarray*}$ . D.h. $\begin{eqnarray*} l | 2 \end{eqnarray*}$ und damit entweder $\begin{eqnarray*} l = 1 \end{eqnarray*}$ oder $\begin{eqnarray*} l =2 \end{eqnarray*}$ . Ersteres ist das was wir wollen, letzteres impliziert, dass $\begin{eqnarray*} n \end{eqnarray*}$ gerade ist.

Wie gesagt, nichts neues zu dem was du schon hattest Augenzwinkern

20.01.2023, 09:20

Malcang

Auf diesen Beitrag antworten »

Ifindu, vielen dank für diese wieder sehr aufschlussreiche Antwort smile

Neue Frage »

Antworten »

ggT = 1, Unklarheit in einem Beweis

Verwandte Themen