Euklidischer Algorithmus < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:23 Sa 25.02.2012 | | Autor: | Pauli85 |
| Aufgabe | | Bestimme den GGT von [mm] 2^{100} [/mm] - 1 und [mm] 2^{50} [/mm] |
Hallo,
ist die folgende Rechnung so richtig? Bin mir nicht ganz sicher. Gibt es da noch eine bessere Umformungsmöglichkeit?
[mm] 2^{100} [/mm] - 1 = [mm] 2^{50}*2^{50} [/mm] - 1 = [mm] (2^{50} [/mm] - 1) * [mm] 2^{50} [/mm] + [mm] 2^{50} [/mm] - 1
[mm] 2^{50} [/mm] = 1 * [mm] (2^{50} [/mm] - 1) + 1
[mm] 2^{50} [/mm] - 1 = [mm] (2^{50} [/mm] - 1) * 1 + 0
[mm] \Rightarrow [/mm] GGT = 1
Vielen Dank
|
|
| |
|
moin Pauli,
> [mm]2^{100}[/mm] - 1 = [mm]2^{50}*2^{50}[/mm] - 1
Diese Zeile besagt, dass:
[mm] $ggT(2^{100}-1,2^{50}) [/mm] = [mm] ggT(2^{50},-1)$
[/mm]
Dass der hintere 1 ist wirst du wohl glauben.^^
Alternativ könntest du dir auch überlegen, dass der $ggT$ ja insbesondere ein gemeinsamer Teiler der beiden Zahlen sein soll.
Die Teiler von [mm] $2^{50}$ [/mm] sind aber leicht zu bestimmen, das sind die [mm] $2^k$ [/mm] für $0 [mm] \leq [/mm] k [mm] \leq [/mm] 50$; und insbesondere sind die für $k>0$ alle gerade.
Überdies dürfte auch ersichtlich sein, dass [mm] $2^{100}-1$ [/mm] ungerade ist.
Also langer Rede kurzer Sinn: Eine ungerade Zahl und eine Zweierpotenz können garkeinen gemeinsamen Teiler (außer der 1) haben.
lg
Schadow
|
|
|
|
