Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Zahlentheoretische Frage

Zahlentheoretische Frage

Universität / Fachhochschule

Tags: Zahlentheorie

Sukomaki aktiv_icon

15:07 Uhr, 18.09.2023

Hallo,

ich habe eine arithmetische Funktion

f (A, B) := \frac{2^{A B} - 1}{(2^{A} - 1) (2^{B} - 1)} - 1

Zeigen möchte ich, dass

g g T (A, B) = 1 \Leftrightarrow ((2^{A} - 1) ∣ (2^{A B} - 1)) \land ((2^{B} - 1) ∣ (2^{A B} - 1))

Ob beide Richtungen gelten, bin ich etwas unsicher.

Gruß
Sukomaki

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

HAL9000

17:49 Uhr, 18.09.2023

(2^{A} - 1) ∣ (2^{A B} - 1)

sowie

(2^{B} - 1) ∣ (2^{A B} - 1)

gelten beide IMMER, auch bei

A, B

mit

ggT (A, B) > 1

. Insofern ist diese deine Äquivalenzaussage sicher falsch.

Meinst du rechts womöglich stattdessen

(2^{A} - 1) (2^{B} - 1) ∣ (2^{A B} - 1)

? Dann gilt zumindest

\Rightarrow

, basierend auf

ggT (2^{A} - 1, 2^{B} - 1) = 2^{ggT (A, B)} - 1

Sukomaki aktiv_icon

08:28 Uhr, 19.09.2023

(2^{A} - 1) ∣ (2^{A B} - 1)

sowie

(2^{B} - 1) ∣ (2^{A B} - 1)

gelten beide IMMER

Wie lässt sich das beweisen : direkt, Induktion oder durch Widerspruch?

Oder vielleicht mittels geometrischer Reihe?

\sum_{j = 0}^{B - 1} (2^{A})^{j} = \frac{2^{A B} - 1}{2^{A} - 1}

Ja, ich meine natürlich rechts

((2^{A} - 1) \cdot (2^{B} - 1) ∣ (2^{A B} - 1)

Ich dachte das wäre dasselbe wie

((2^{A} - 1) ∣ (2^{A B} - 1)) \land ((2^{B} - 1) ∣ (2^{A B} - 1))

Ist aber wohl nicht so.

Gegenbeispiel :

A = B = 3 \Rightarrow (7 ∣ 511)

, aber nicht

49 ∣ 511

> Dann gilt zumindest

\Rightarrow

Gilt denn auch

\Leftarrow

?

Kannst Du

g g T (2^{A} - 1, 2^{B} - 1) = 2^{g g T (A, B)} - 1

bitte ein wenig detaillierter ausführen?

HAL9000

09:30 Uhr, 19.09.2023

Ja, Partialsummenformel der geometrischen Reihe ist das richtige Stichwort.

Die ggT-Aussage ist einigermaßen raffiniert und geht gewissermaßen auf den euklidischen Algorithmus zurück: O.B.d.A. sei

A \geq B

, dann gilt

f (A, B) := ggT (2^{A} - 1, 2^{B} - 1) = ggT (2^{A} - 1 - 2^{A - B} \cdot (2^{B} - 1), 2^{B} - 1) = ggT (2^{A - B} - 1, 2^{B} - 1) \overset{!}{=} f (A - B, B)

.

Zusammen mit Symmetrie

f (A, B) = f (B, A)

folgt dann in Analogie zum euklidischen Algorithmus nach endlich vielen Schritten

f (A, B) = f (ggT (A, B), 0) = ggT (2^{ggT (A, B)} - 1, 2^{0} - 1) = 2^{ggT (A, B)} - 1

.

Der Beweis ist übrigens nicht an Basis 2 gebunden, man kann auch jede andere positive ganze Zahl dort nehmen.

> Gilt denn auch

\Leftarrow

?

Wenn ich das wüsste, hätte ich es gesagt. Hab zumindest auf die Schnelle kein Gegenbeispiel gefunden, aber das muss nichts heißen.

Sukomaki aktiv_icon

12:27 Uhr, 20.09.2023

Das mit der Teilbarkeit ist im Prinzip recht einfach :

Es sind

(2^{A} - 1) ∣ (2^{A B} - 1)

und

(2^{B} - 1) ∣ (2^{A B} - 1)

Wenn jetzt

g g T (A, B) = 1

dann ist auch

(2^{A} - 1) (2^{B} - 1) ∣ (2^{A B} - 1)

Begründung : Es ist denkbar, dass in

2^{A} - 1

und

2^{B} - 1

jeweils

p

vorkommt (Vielfachheit

v

).

Dann muss der Primfaktor

p

2^{A B} - 1

mindestens

2 v

mal vorkommen.

Das ist nicht selbstverständlich.

Kommen alle

p

nur in

2^{A} - 1

oder

2^{B} - 1

vor, so entspricht die Primfaktorzerlegung von

2^{A B} - 1

dem Produkt der Primfaktorzerlegung von

2^{A} - 1

multipliziert mit der Primfaktorzerlegung von

2^{B} - 1

multipliziert mit einem Restfaktor.

Es gilt also :

g g T (A, B) = 1 \Rightarrow (2^{A} - 1) (2^{B} - 1) ∣ (2^{A B} - 1)

Den an Euklid angelehnten "Algorithmus" verstehe ich.

Der Schritt mit

g g T (2^{A} - 1, 2^{B} - 1) = g g T (2^{A} - 1 - 2^{A - B} \cdot (2^{B} - 1), 2^{B} - 1)

ist clever.

(Hier kommt

A \geq B

ins Spiel)

Er basiert auf

g g T (A, B) = g g T (A - λ B, B)

Nun gut : Jetzt haben wir

g g T (2^{A} - 1, 2^{B} - 1) = 2^{g g T (a, b)} - 1

Sollte recht einfach sein, daraus

g g T (A, B) = 1 \Rightarrow (2^{A} - 1) (2^{B} - 1) ∣ (2^{A B} - 1)

zu folgern, aber irgendwie habe ich einen Knoten im Hirn :-D)

HAL9000

12:51 Uhr, 20.09.2023

Für teilerfremde

a, b

folgt aus

a ∣ c

und

b ∣ c

sofort

a b ∣ c

, das ist eine recht elementare Teilbarkeitsaussage.

Allgemein gilt lediglich

a b ∣ (c \cdot ggT (a, b))

Sukomaki aktiv_icon

13:31 Uhr, 20.09.2023

a ∣ c \land b ∣ c \Rightarrow a b ∣ (c \cdot g g T (a, b))

Danke, diese Umformung hatte mir zum Verständnis gefehlt.

Habe ich denn richtig verstanden, dass

g g T (a, b) = 1 \Leftrightarrow g g T (2^{a} - 1, 2^{b} - 1) = 1

wobei die Basis 2 unabdingbar ist oder habe ich da etwas übersehen?

HAL9000

14:43 Uhr, 20.09.2023

Naja, für jede Basis

c \geq 2

gilt gemäß obiger Aussage

ggT (a, b) = 1 \Leftrightarrow ggT (c^{a} - 1, c^{b} - 1) = c - 1

,

im besonderen eben auch für

c = 2

Sukomaki aktiv_icon

15:08 Uhr, 20.09.2023

Danke sehr,

dann passt das ja.

Wieder etwas dazugelernt.

Aber auf welche obige Aussage beziehst Du Dich?

HAL9000

15:10 Uhr, 20.09.2023

> Der Beweis ist übrigens nicht an Basis 2 gebunden, man kann auch jede andere positive ganze Zahl dort nehmen.

Übersetzt:

ggT (c^{A} - 1, c^{B} - 1) = c^{ggT (A, B)} - 1

Sukomaki aktiv_icon

15:23 Uhr, 20.09.2023

Ich danke Dir.

Das ist schon komisch mit mir, oder?

Ich meine, einerseits fällt mir mancher Uni-Stoff relativ leicht und andererseits sehe ich von Zeit zu Zeit die einfachsten Zusammenhänge nicht.

Ich hoffe, ich nerve Dich nicht mit meinen einfachen Fragen :-D)

HAL9000

08:41 Uhr, 21.09.2023

Genervt bin ich allenfalls, wenn ich Dinge mehrfach wiederholen muss, bis sie überhaupt registriert werden. Das ist bisher hier noch nicht vorgekommen, daher alles gut.

Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.

1575967

1575821

	Status: nicht eingeloggt	Noch nicht registriert?