Kriterium von Pocklington

25.01.2023, 12:08

Malcang

Kriterium von Pocklington

Hallo zusammen,

ich schaue mir gerade das Kriterium von Pocklington an (um genau zu sein, in diesem Paper.)
Es lautet:
[attach]56735[/attach]
und wird bewiesen wie folgt:
[attach]56736[/attach]

Ich steige leider nicht ganz durch und bin über jeden Denkanstoß dankbar smile

Im zweiten Absatz des Beweises setzt der Autor $\begin{eqnarray*} r=ord_p a \end{eqnarray*}$ . Es wurde ja nun gezeigt, $\begin{eqnarray*} a^{n-1}\equiv 1\pmod p \end{eqnarray*}$ und $\begin{eqnarray*} a^{\frac{n-1}{q}}\not\equiv 1 \pmod p \end{eqnarray*}$ .
$\begin{eqnarray*} r|n-1 \end{eqnarray*}$ folgt ja aus $\begin{eqnarray*} a^{n-1}\equiv 1\pmod p \end{eqnarray*}$ , das sehe ich ein. Aber warum kann ich auf $\begin{eqnarray*} r\not | \frac{n-1}{q} \end{eqnarray*}$ schließen?
Und wie kommt er danach auf $\begin{eqnarray*} q^{\alpha} | r \end{eqnarray*}$ ? verwirrt

Da hakt es gerade bei mir.

Edit:
Ah, das erste kann ich doch beantworten: Wenn $\begin{eqnarray*} r \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} \frac{n-1}{q} \end{eqnarray*}$ wäre, würde ja folgen:
$\begin{eqnarray*} \exists k\in\mathbb N: \frac{n-1}{q} = k\cdot r \Rightarrow a^{k\cdot r} = (a^r)^k = 1^k = 1 \end{eqnarray*}$ .

Edit2:
Ich habe nun
$\begin{eqnarray*} r|q^{\alpha}t \Rightarrow r|q^{\alpha} \text{ oder } r|t \end{eqnarray*}$
sowie
$\begin{eqnarray*} r\nmid q^{\alpha-1}t \Rightarrow r\nmid q^{\alpha-1} \text{ und } r\nmid t \end{eqnarray*}$ .
Daher folgt $\begin{eqnarray*} r|q^{\alpha} \end{eqnarray*}$ .
Aber wie komme ich auf $\begin{eqnarray*} q^{\alpha}|r? \end{eqnarray*}$ verwirrt

25.01.2023, 20:04

IfindU

Auf diesen Beitrag antworten »

RE: Kriterium von Pocklington

Zitat:

Original von Malcang
Edit2:
Ich habe nun
$\begin{eqnarray*} r|q^{\alpha}t \Rightarrow r|q^{\alpha} \text{ oder } r|t \end{eqnarray*}$

Die Folgerung im Allgemeinen gilt nur, wenn $\begin{eqnarray*} r \end{eqnarray*}$ eine Primzahl ist.

Aus $\begin{eqnarray*} r | q^\alpha t \end{eqnarray*}$ wissen wir, dass eine ganze Zahl $\begin{eqnarray*} k \end{eqnarray*}$ existiert mit $\begin{eqnarray*} r\cdot k = q^\alpha t \end{eqnarray*}$ . Teilen wir es durch $\begin{eqnarray*} q \end{eqnarray*}$ gilt $\begin{eqnarray*} r\cdot \frac k q = q^{\alpha-1} t \end{eqnarray*}$ . Wenn $\begin{eqnarray*} \frac k q \end{eqnarray*}$ eine ganze Zahl ist, dann [...], wenn nicht, dann muss [...].

Hilft das?

26.01.2023, 11:12

Malcang

Auf diesen Beitrag antworten »

Hallo IfindU,

danke für diesen Hinweis.
Ich hatte gestern abend nochmal gegrübelt und folgendes raus. Aber das sollte dann wegen deinem ersten Hinweis auf die Primalität leider doch nicht stimmen.
Bekomme ich das gerettet? Ich glaube dass der Beweis auch auf deinen zweiten Hinweis hinausläuft.
[attach]56742[/attach]

26.01.2023, 11:35

IfindU

Auf diesen Beitrag antworten »

Bei dir im Beweis sieht $\begin{eqnarray*} r| q^\alpha \end{eqnarray*}$ extrem wichtig aus. Das würde auch sofort implizieren, dass $\begin{eqnarray*} r = \pm q^\beta \end{eqnarray*}$ mit $\begin{eqnarray*} 0 \leq \beta \leq \alpha \end{eqnarray*}$ . Aus $\begin{eqnarray*} r \not \hspace{-.1cm}| \;t q^{\alpha-1} \end{eqnarray*}$ folgt (keine Äquivalenz!), dass $\begin{eqnarray*} r \not \hspace{-.1cm} |\; t \end{eqnarray*}$ UND $\begin{eqnarray*} r \not\hspace{-.1cm} |\;q^{\alpha-1} \end{eqnarray*}$ und damit sofort $\begin{eqnarray*} \beta \geq \alpha -1 \end{eqnarray*}$ und damit $\begin{eqnarray*} r = \pm q^{\alpha} \end{eqnarray*}$ .

Inwieweit man den Beweis retten kann, kann ich nicht beurteilen,

26.01.2023, 11:56

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Bei dir im Beweis $\begin{eqnarray*} r| q^\alpha \end{eqnarray*}$ sieht extrem wichtig aus. Das würde auch sofort implizieren, dass $\begin{eqnarray*} r = \pm q^\beta \end{eqnarray*}$ mit $\begin{eqnarray*} 0 \leq \beta \leq \alpha \end{eqnarray*}$ . Aus $\begin{eqnarray*} r \not \hspace{-.1cm}| \;t q^{\alpha-1} \end{eqnarray*}$ (keine Äquivalenz!), dass $\begin{eqnarray*} r \not \hspace{-.1cm} |\; t \end{eqnarray*}$ UND $\begin{eqnarray*} r \not\hspace{-.1cm} |\;q^{\alpha-1} \end{eqnarray*}$ und damit sofort $\begin{eqnarray*} \beta \geq \alpha -1 \end{eqnarray*}$ und damit $\begin{eqnarray*} r = \pm q^{\alpha} \end{eqnarray*}$ .

Inwieweit man den Beweis retten kann, kann ich nicht beurteilen,

Danke sehr. Ich gehe mal davon aus, dass ich wieder von vorne anfangen muss, um direkt deinen Hinweis umsetzen zu können. Ich verfasse das nochmal, werde das aber als Lemma auslagern. Ich würde mich dazu gerne nochmal melden, was aber jetzt etwas dauern wird. Ich hoffe es ist ok, wenn ich diesen Thread dann wieder hochhole.

Ich danke dir für die Hinweise!

26.01.2023, 12:17

IfindU

Auf diesen Beitrag antworten »

Die Idee ist ja einfach, dass $\begin{eqnarray*} r | q^{\alpha} t \end{eqnarray*}$ aber $\begin{eqnarray*} r\cdot q \not| q^{\alpha} t \end{eqnarray*}$ heißt, dass $\begin{eqnarray*} r \end{eqnarray*}$ schon selbst mindestens $\begin{eqnarray*} \alpha \end{eqnarray*}$ -mal oft den Faktor $\begin{eqnarray*} q \end{eqnarray*}$ beinhalten muss. Sonst hätte auch $\begin{eqnarray*} r\cdot q \end{eqnarray*}$ den Faktor $\begin{eqnarray*} q \end{eqnarray*}$ höchstens $\begin{eqnarray*} \alpha \end{eqnarray*}$ mal und die Teilbarkeit wäre $\begin{eqnarray*} r\cdot q | q^{\alpha} t \end{eqnarray*}$ wäre gegeben.

Edit: $\begin{eqnarray*} s | t \end{eqnarray*}$ genau dann wenn für jede Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ gilt, dass die Vielfachheit von $\begin{eqnarray*} p \end{eqnarray*}$ in $\begin{eqnarray*} s \end{eqnarray*}$ höchstens so groß wie ist wie die Vielfachheit von $\begin{eqnarray*} p \end{eqnarray*}$ in $\begin{eqnarray*} t \end{eqnarray*}$ . Damit kann man auch das oben schnell sauber (und direkt) zeigen.

23.02.2023, 11:02

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von IfindU
Die Idee ist ja einfach, dass $\begin{eqnarray*} r | q^{\alpha} t \end{eqnarray*}$ aber $\begin{eqnarray*} r\cdot q \not| q^{\alpha} t \end{eqnarray*}$ heißt, dass $\begin{eqnarray*} r \end{eqnarray*}$ schon selbst mindestens $\begin{eqnarray*} \alpha \end{eqnarray*}$ -mal oft den Faktor $\begin{eqnarray*} q \end{eqnarray*}$ beinhalten muss. Sonst hätte auch $\begin{eqnarray*} r\cdot q \end{eqnarray*}$ den Faktor $\begin{eqnarray*} q \end{eqnarray*}$ höchstens $\begin{eqnarray*} \alpha \end{eqnarray*}$ mal und die Teilbarkeit wäre $\begin{eqnarray*} r\cdot q | q^{\alpha} t \end{eqnarray*}$ wäre gegeben.

Edit: $\begin{eqnarray*} s | t \end{eqnarray*}$ genau dann wenn für jede Primzahl $\begin{eqnarray*} p \end{eqnarray*}$ gilt, dass die Vielfachheit von $\begin{eqnarray*} p \end{eqnarray*}$ in $\begin{eqnarray*} s \end{eqnarray*}$ höchstens so groß wie ist wie die Vielfachheit von $\begin{eqnarray*} p \end{eqnarray*}$ in $\begin{eqnarray*} t \end{eqnarray*}$ . Damit kann man auch das oben schnell sauber (und direkt) zeigen.

Hallo IfindU,

bitte entschuldige dass ich mich erst jetzt melde. Ich hatte den Thread aus den Augen verloren weil ich mich aktuell auf ein anderes Thema konzentriere. Jetzt wollte ich das hier nochmal anschauen und merke, dass ich leider doch noch nicht durchgestiegen bin. Kannst du mir hier nochmal zur Hand gehen?

Ich möchte also zeigen:
$\begin{eqnarray*} r\mid t\cdot q^{\alpha} \end{eqnarray*}$ und $\begin{eqnarray*} r\nmid t\cdot q^{\alpha-1} \end{eqnarray*}$ . Dann gilt: $\begin{eqnarray*} r = k\cdot q^{\alpha} \end{eqnarray*}$ wobei $\begin{eqnarray*} k \end{eqnarray*}$ ein Teiler von $\begin{eqnarray*} t \end{eqnarray*}$ ist.
Du sagst ja nun dass aus $\begin{eqnarray*} r\cdot q \nmid t\cdot q^{\alpha} \end{eqnarray*}$ folgt, dass $\begin{eqnarray*} q^{\alpha} \mid r \end{eqnarray*}$ ist. Ich kann das auch verstehen.
Sei also $\begin{eqnarray*} r = k\cdot q^{\alpha} \end{eqnarray*}$ für ein $\begin{eqnarray*} k\in\mathbb Z. \end{eqnarray*}$ Es folgt also:
$\begin{eqnarray*} k\cdot q^{\alpha} \mid t\cdot q^{\alpha} \end{eqnarray*}$ und damit $\begin{eqnarray*} k\mid t \end{eqnarray*}$ .

Ist das so ok?

23.02.2023, 12:29

HAL 9000

Auf diesen Beitrag antworten »

Ich hätte es so begründet.

$\begin{eqnarray*} r\mid t\cdot q^{\alpha} \end{eqnarray*}$ bedeutet, dass es ein $\begin{eqnarray*} s \end{eqnarray*}$ mit $\begin{eqnarray*} r\cdot s = t\cdot q^{\alpha} \end{eqnarray*}$ gibt. Dabei ist $\begin{eqnarray*} s \end{eqnarray*}$ NICHT durch $\begin{eqnarray*} q \end{eqnarray*}$ teilbar, denn andernfalls würde ja $\begin{eqnarray*} r\cdot \frac{s}{q} = t\cdot q^{\alpha-1} \end{eqnarray*}$ bedeuten dass $\begin{eqnarray*} r\mid t\cdot q^{\alpha-1} \end{eqnarray*}$ gilt, was ja ausgeschlossen ist. Somit ist zwangsläufig $\begin{eqnarray*} s\mid t \end{eqnarray*}$ und damit auch $\begin{eqnarray*} q^{\alpha}\mid r \end{eqnarray*}$ , folglich ist dann $\begin{eqnarray*} r = k\cdot q^{\alpha} \end{eqnarray*}$ mit $\begin{eqnarray*} k=\frac{t}{s} \end{eqnarray*}$ .

23.02.2023, 12:49

Malcang

Auf diesen Beitrag antworten »

Danke sehr HAL. Ich traue mich fast nicht zu fragen, aber

Zitat:

Original von HAL 9000
Somit ist zwangsläufig $\begin{eqnarray*} s\mid t \end{eqnarray*}$

sehe ich nicht sofort ein? verwirrt

23.02.2023, 12:58

HAL 9000

Auf diesen Beitrag antworten »

Hmm, also irgendwann müssen wir aber mal am Bodensatz der elementaren Teilbarkeitseigenschaften angelangt sein, über die nicht mehr ständig diskutiert werden sollte:

Zitat:

1) $\begin{eqnarray*} p\mid (rs) \end{eqnarray*}$ und $\begin{eqnarray*} p \end{eqnarray*}$ prim $\begin{eqnarray*} \Longrightarrow \left(p\mid r \,\vee\, p\mid s\right) \end{eqnarray*}$

2) $\begin{eqnarray*} a\cdot b = c\cdot d \end{eqnarray*}$ und $\begin{eqnarray*} \operatorname{ggT}(b,d)=1 \end{eqnarray*}$ $\begin{eqnarray*} \Longrightarrow b\mid c\,\wedge\,d\mid a \end{eqnarray*}$

Hier geht es um 2) mit $\begin{eqnarray*} b=s \end{eqnarray*}$ und $\begin{eqnarray*} d=q^{\alpha} \end{eqnarray*}$ .

23.02.2023, 13:33

Malcang

Auf diesen Beitrag antworten »

Damit hast du wohl recht. Ich versteife mich leider viel zu oft auf die Dinge.
Jetzt hab ich's aber verstanden.
Vielen Dank dafür! Freude

Neue Frage »

Antworten »

Kriterium von Pocklington

Verwandte Themen