Primfaktoren bei Kongruenz 1 modulo 8

18.01.2023, 17:26

Malcang

Primfaktoren bei Kongruenz 1 modulo 8

Hallo zusammen,

ich habe für meine Masterarbeit einen Satz benötigt, den ich so nicht kannte und der mir auch nicht trivial erschien. Daher habe ich ihn beweisen wollen und würde ihn euch gerne zeigen.
Mir kommt der Beweis insgesamt so überladen vor, insbesondere aufgrund der Doppelindizes. Dies war mir aber lieber, als verschiedene Buchstaben $\begin{eqnarray*} p,q,r,s \end{eqnarray*}$ für die Primzahlen zu verwenden.
Außerdem bin ich normalerweise sehr pedantisch in diesen Dingen. Ich hätte normalerweise nicht geschrieben "durch Nachrechnen", sondern die einzelnen Produkte alle ausmultipliziert. Aber das erschien mir dann noch mehr überladen für eine solche Trivialität.
Was ist eure Meinung zu dem Ganzen? smile

Vielen Dank für eure Zeit!
[attach]56696[/attach]

18.01.2023, 18:00

IfindU

Auf diesen Beitrag antworten »

Etwas vereinfachen kann man den Beweis wie folgt: Sei $\begin{eqnarray*} n = \prod p_i^{\alpha_i} \end{eqnarray*}$ . Definiere $\begin{eqnarray*} \mathcal P = \{ p_i \} \end{eqnarray*}$ und $\begin{eqnarray*} \mathcal P_k = \{ p_i \in \mathcal P | \quad p_i \equiv k \mod 8 \} \end{eqnarray*}$ . Da nur $\begin{eqnarray*} k = \pm 1, \pm 3 \end{eqnarray*}$ eine nicht-leere Menge liefern und $\begin{eqnarray*} \mathcal P_1 \end{eqnarray*}$ witzlos für die weitere Berechnung ist (und man über diese Primzahlen sicherlich nichts sagen kann hier), gilt
$\begin{eqnarray*} n \equiv \prod p_i^{\alpha_i} = \prod_{p \in \mathcal P_3} p^{\alpha_p} \prod_{q \in \mathcal P_{-3}} q^{\alpha_q} \prod_{r \in \mathcal P_{-1}} r^{\alpha_r} \equiv \prod_{p \in \mathcal P_3} 3^{\alpha_p} \prod_{q \in \mathcal P_{-3}} (-3)^{\alpha_q} \prod_{r \in \mathcal P_{-1}} (-1)^{\alpha_r} \equiv 3^{ \sum_{p \in \mathcal P_3} \alpha_p} (-3)^{\sum_{q \in \mathcal P_{-3}} \alpha_q} (-1)^{ \sum_{r \in \mathcal P_{-1}} \alpha_r} \mod 8 \end{eqnarray*}$ .

Da die Elemente $\begin{eqnarray*} \pm 1, \pm 3 \end{eqnarray*}$ alle Selbstinvers sind, reicht es den Exponenten 0 oder 1 zu betrachten. Das gibt die 8 Fälle $\begin{eqnarray*} \sum_{p \in \mathcal P_3} \alpha_p \in \{0,1\} \end{eqnarray*}$ , $\begin{eqnarray*} \sum_{q \in \mathcal P_{-3}} \alpha_q \in \{0,1\} \end{eqnarray*}$ , $\begin{eqnarray*} \sum_{r \in \mathcal P_{-1}} \alpha_r \in \{0,1\} \end{eqnarray*}$ zu überprüfen.

Edit: Zu früh losgeschickt. Wollte mir noch überlegen wie man statt der 8 weniger betrachten muss.

Edit 2: $\begin{eqnarray*} 3^{ \sum_{p \in \mathcal P_3} \alpha_p} (-3)^{\sum_{q \in \mathcal P_{-3}} \alpha_q} (-1)^{ \sum_{r \in \mathcal P_{-1}} \alpha_r} \equiv 3^{ \sum_{p \in \mathcal P_3} \alpha_p + \sum_{q \in \mathcal P_{-3}} \alpha_q} \cdot (-1)^{ \sum_{r \in \mathcal P_{-1}} \alpha_r + \sum_{q \in \mathcal P_{-3}} \alpha_q} \mod 8 \end{eqnarray*}$ .

Jetzt kann man sich überlegen, warum beide Exponenten gerade sein müssen und mit den beiden Fällen $\begin{eqnarray*} \sum_{q \in \mathcal P_{-3}} \alpha_q \end{eqnarray*}$ gerade/ungerade folgt alles.

18.01.2023, 18:01

Elvis

Auf diesen Beitrag antworten »

Am Ende des Beweises von Satz 0.0.2 hast du komplizierte Produkte stehen und erwartest, dass man "durch Nachrechnen" zum Ziel kommen soll. Ich ahne zwar, worauf das hinaus läuft, aber als Beweis ist mir das zu nachlässig. Bitte rechne das "Nachrechnen" vor, damit ich es verstehen kann, ich weiß nicht, was daran trivial ist.

18.01.2023, 18:12

Malcang

Auf diesen Beitrag antworten »

Guten Abend ihr beiden,

Vielen Dank für diese wirklich aufschlussreichen Antworten. Ich nutze nun die Zeit im Zug nach Hause, um das einmal handschriftlich zu notieren. Gerne würde ich mich dann mit einer neuen PDF Datei wieder melden, das wird aber heute nichts mehr.
Freue mich aber sehr über eure weiteren Hilfestellungen!

Schönen abend smile

19.01.2023, 08:13

HAL 9000

Auf diesen Beitrag antworten »

@IfindU

M.E. kann man den Indexkrieg noch weiter eindämmen, indem man von vornherein nur mit den bloßen Anzahlen $\begin{eqnarray*} \beta_k \end{eqnarray*}$ an Primfaktoren der Restklasse $\begin{eqnarray*} k\bmod 8 \end{eqnarray*}$ (unter Berücksichtigung der Vielfachheiten) operiert, um dann unter Berücksichtigung von 0.0.1 sowie $\begin{eqnarray*} \gamma_k = \beta_k \mod 2 \end{eqnarray*}$ direkt zu rechnen

$\begin{eqnarray*} n\equiv 1^{\beta_1}\cdot 3^{\beta_3}\cdot 5^{\beta_5}\cdot 7^{\beta_7}\equiv 3^{\gamma_3}\cdot 5^{\gamma_5}\cdot 7^{\gamma_7}\bmod 8,\qquad (*) \end{eqnarray*}$

um anschließend direkt die $\begin{eqnarray*} 2^3=8 \end{eqnarray*}$ Fälle aller Kombinationen $\begin{eqnarray*} \gamma_3,\gamma_5,\gamma_7\in\{0,1\} \end{eqnarray*}$ zu diskutieren.

19.01.2023, 09:41

IfindU

Auf diesen Beitrag antworten »

@HAL Das reduziert es tatsächlich noch ein mehr Freude

Ich denke mit $\begin{eqnarray*} 3^{\gamma_3}\cdot 5^{\gamma_5}\cdot 7^{\gamma_7} \equiv 3^{\gamma_3}\cdot (-3)^{\gamma_5}\cdot (-1)^{\gamma_7} = 3^{\gamma_3 + \gamma_5 }\cdot (-1)^{\gamma_5 + \gamma_7} \bmod 8 \end{eqnarray*}$ kann man mit $\begin{eqnarray*} \gamma_3 + \gamma_5 \end{eqnarray*}$ gerade/ungerade sowie $\begin{eqnarray*} \gamma_5 + \gamma_7 \end{eqnarray*}$ gerade/ungerade betrachten nur 4 Fälle betrachten. Man bekommt schnell, dass die Summen beide gerade sein müssen, und damit, dass $\begin{eqnarray*} y_3 = y_5 = y_7 \end{eqnarray*}$ . Was zu zeigen war (wenn ich Malcang richtig verstanden hab).

19.01.2023, 11:20

HAL 9000

Auf diesen Beitrag antworten »

In der Kürze liegt die Würze...
Ok, wenn ich mal die Ideen von IfindU mit meiner Vereinfachung kombiniere, und die Bezeichnungen noch etwas straffe, so komme ich zu folgender schon ziemlich "eingedampften" Beweisvariante:

Zitat:

Sei $\begin{eqnarray*} \beta_k \end{eqnarray*}$ die Anzahl der in $\begin{eqnarray*} n \end{eqnarray*}$ enthaltenen Primfaktoren der Restklasse $\begin{eqnarray*} k\bmod 8 \end{eqnarray*}$ (mit Mehrfachzählung bei Vielfachheiten). Dann gilt unter Beücksichtigung von $\begin{eqnarray*} 5\equiv -3 \end{eqnarray*}$ sowie $\begin{eqnarray*} 7\equiv -1 \end{eqnarray*}$

$\begin{eqnarray*} n\equiv 1^{\beta_1}\cdot 3^{\beta_3}\cdot (-3)^{\beta_5}\cdot (-1)^{\beta_7} = 3^{\beta_3+\beta_5}\cdot (-1)^{\beta_5+\beta_7}\bmod 8 \end{eqnarray*}$ .

Für $\begin{eqnarray*} n\equiv 1\bmod 8 \end{eqnarray*}$ ist erforderlich, dass beide Potenzen rechts $\begin{eqnarray*} \equiv 1\bmod 8 \end{eqnarray*}$ sind, was genau dann der Fall ist, wenn beide Exponenten gerade sind. Was wiederum genau dann eintritt, wenn alle drei Werte $\begin{eqnarray*} \beta_3,\beta_5,\beta_7 \end{eqnarray*}$ dieselbe Parität aufweisen.

19.01.2023, 13:33

Malcang

Auf diesen Beitrag antworten »

Guten Tag zusammen,

ich danke euch vielmals für eure rege Teilnahme an meiner Frage! Das hat mir sehr geholfen und ich habe nun den Beweis erneut geführt. Gerne zeige ich ihn euch, diesmal aber als Screenshot smile

Ich habe eure Anmerkungen alle nachvollziehen können.
Edit: Ich sollte den Satz möglicherweise umformulieren fällt mir gerade auf. Es müssen ja nicht alle entsprechenden Primfaktoren jeweils gerade sein, sondern die Anzahl der zugehörigen Kongruenzen. Ich überlege mir beim Mittagessen eine geeignetere Formulierung.
[attach]56700[/attach]

@Elvis:
Deine Frage möchte ich natürlich trotzdem zumindest kurz skizzieren. Was ich mit "durch Nachrechnen" abgekürzt habe sind in der Tat die Fälle
$\begin{eqnarray*} 1\cdot 1\cdot 1, 1 \cdot 1\cdot 3\,\dots, 3\cdot 5\cdot 7. \end{eqnarray*}$
Ich verstehe aber deinen Einwand. Mir selber ist klar was ich mache, dem Leser ist das sicherlich nicht.
Danke für diesen Einwand!

19.01.2023, 13:51

HAL 9000

Auf diesen Beitrag antworten »

Die Äquivalenz in der viertletzten Zeile ist schlicht falsch: Repariert kann sie allenfalls

$\begin{eqnarray*} S_3+S_{-3}\equiv S_{-3}+S_{-1}\equiv 0\pmod 2 ~\Longleftrightarrow~ S_3\equiv S_{-3}\pmod 2\wedge S_{-3}\equiv S_{-1}\pmod 2 ~\Longleftrightarrow~ S_3\equiv S_{-3}\equiv S_{-1}\pmod 2 \end{eqnarray*}$

lauten.

19.01.2023, 15:31

Malcang

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Die Äquivalenz in der viertletzten Zeile ist schlicht falsch: Repariert kann sie allenfalls

$\begin{eqnarray*} S_3+S_{-3}\equiv S_{-3}+S_{-1}\equiv 0\pmod 2 ~\Longleftrightarrow~ S_3\equiv S_{-3}\pmod 2\wedge S_{-3}\equiv S_{-1}\pmod 2 ~\Longleftrightarrow~ S_3\equiv S_{-3}\equiv S_{-1}\pmod 2 \end{eqnarray*}$

lauten.

Danke HAL 9000. Ich würde das folgendermaßen niederschreiben:
$\begin{eqnarray*} S_3 + S_{-3} \equiv S_{-3} + S_{-1} \pmod 2 \Leftrightarrow S_3\equiv S_{-1}\equiv -S_{-3}\equiv S_{-3}\pmod 2 \end{eqnarray*}$

Was sagst du dazu?

Edit:
Ich habe nun übrigens den Satz umformuliert:
[attach]56703[/attach]

Edit2: Der Satz ist wieder falsch, ich bin mal wieder zu schnell.
Ich habe nun aber beides noch einmal überarbeitet und würde euch gerne meine Version nochmal zeigen. Im Anschluss an den hier besprochenen Beweis kommt übrigens der Satz, für den ich diese Behauptung benötige.

[attach]56704[/attach]

20.01.2023, 13:45

IfindU

Auf diesen Beitrag antworten »

Gar nicht gesehen, dass du hier noch was editiert hast. Sieht richtig für mich aus :thumbs: Du solltest mit den Indizes aber mehr aufpassen. Deine Produkte laufen alle über $\begin{eqnarray*} p \end{eqnarray*}$ , die Faktoren haben dann aber $\begin{eqnarray*} p,q,r \end{eqnarray*}$ im Namen.

21.01.2023, 14:55

Malcang

Auf diesen Beitrag antworten »

Oh ja, vielen Dank für diesen Hinweis!

Danke vielmals an alle Helfer! Mit Zunge

Neue Frage »

Antworten »

Primfaktoren bei Kongruenz 1 modulo 8

Verwandte Themen