Elementare Zahlentheorie

Aufrufe: 73     Aktiv: 18.03.2021 um 01:13

0

Hey ich soll folgende Aufgabe lösen, weiß allerdings nicht wie:
Seien m und n positive ganze Zahlen. Dann soll man zeigen dass der ggT((2^n)-1,(2^m)-1) = 1genau dann gilt wenn ggT(n,m)=1.

Seit gestern überlege und probiere ich da herum aber ich komme nicht drauf:(
Ich bedanke mich bereits jetzt für die Antwort:D

Diese Frage melden
gefragt

Punkte: 12

 

ich hab mir gerade ehrlich gesagt nicht total lang gedanken gemacht (deswegen keine antwort sondern nur ein kommentar). hast du vielleicht schon mal was mit binärdarstellung oder steinscher algorithmus probiert? sieht finde ich nämlich relativ viel versprechend aus.   ─   b_schaub 18.03.2021 um 01:05

Kommentar schreiben

2 Antworten
0
Hi,
Wenn bei zwei Zahlen m und n der ggT 1 sein soll, bedeutet dies, dass hier Primzahlen vorliegen müssen. Bzw mindestens eine davon ist eine Primzahl, aber dann darf die andere kein Vielfaches von ihr sein. So gilt: ggT(n,m)=1.
Dass der ggT((2^n)-1,(2^m)-1) = 1 ist passt dementsprechend auch, da es sich bei der Form 2^n-1 um eine sog. Mersenne-Zahl handelt, diese kann nur eine Primzahl sein, wenn n selbst eine ist. Da der ggT 1 sein soll, ist dies der Fall.
Hoffe ich konnte helfen!
LG
Diese Antwort melden
geantwortet

Punkte: 10
 

So wie ich das sehe, ist diese Antwort leider völlig fehlerhaft.
Wenn zwei Zahlen den ggT \(1\) haben, dann bedeutet das im Allgemeinen nicht, dass mindestens eine davon eine Primzahl sein muss. Beispielsweise ist \( ggT(4,15)=1 \) und weder \( 4 \) noch \( 15 \) ist eine Primzahl.
Auch bei der Mersenne-Zahl liegt ein Denkfehler vor. Es stimmt, dass eine Mersenne-Zahl \( 2^n - 1 \) nur dann eine Primzahl sein kann, wenn \( n \) selbst eine Primzahl ist, allerdings gilt das umgekehrt nicht. \( 11 \) ist eine Primzahl, aber die Mersenne-Zahl \( 2^{11}-1 \) ist keine Primzahl.
Außerdem ist auch die Struktur der Antwort ziemlich verwirrend. Hier soll ja eine Äquivalenz gezeigt werden, aber (zumindest für mich) sind die beiden Implikationen nicht klar zu erkennen.
  ─   anonym 17.03.2021 um 23:43

Kommentar schreiben

0
Für die Hinrichtung zeigen wir die Kontraposition:
Angenommen, es gilt \( g := ggT(n,m) \neq 1 \). Dann ist \( 2^g-1 \) offensichtlich größer als \( 1 \) und außerdem ein Teiler von \( 2^n-1 \) und \( 2^m-1 \), denn man kann schreiben \( n=gu \) und \( m=gv \) für positive ganze Zahlen \( u \) und \( v \) und erhält dann durch die Formel für die geometrische Summe, dass die Ausdrücke \( \frac{2^n-1}{2^g-1} = \frac{(2^g)^u-1}{2^g-1} \) und \( \frac{2^m-1}{2^g-1} = \frac{(2^g)^v-1}{2^g-1} \) ganze Zahlen sind. Damit folgt dann aber sofort \( ggT(2^n-1,2^m-1) \neq 1 \).

Nun zeigen wir die Rückrichtung:
Angenommen, es gilt \( ggT(n,m)=1 \). Dann findet man mit dem erweiterten euklidischen Algorithmus zwei (oBdA) positive ganze Zahlen \( a \) und \( b \), sodass \( an-bm=1 \) ist.
Per Definition teilt nun \( ggT(2^n-1,2^m-1) \) die beiden Zahlen \( 2^n-1 \) und \(2^m-1\) und somit auch die folgende Linearkombination dieser Zahlen:
\( \frac{(2^n)^a-1}{2^n-1}(2^n-1) - \frac{(2^m)^b-1}{2^{m}-1} (2^m-1) = 2^{an} - 2^{bm} = 2^{bm} ( 2^{an-bm}-1) = 2^{bm} ( 2^1 - 1) = 2^{bm} \)
(Beachte hierbei, dass \( \frac{(2^n)^a-1}{2^n-1} \) und \( \frac{(2^m)^b-1}{2^{m}-1} \) ganze Zahlen sind. Vergleiche hierzu die Formel für die geometrische Summe.)
Da \( ggT(2^n-1,2^m-1) \) aber keine gerade Zahl sein kann (denn er teilt die ungerade Zahl \( 2^n-1 \)), folgt somit \( ggT(2^n-1,2^m-1)=1 \).
Diese Antwort melden
geantwortet

Student, Punkte: 5.54K
 

Kommentar schreiben