Beweis für Gleichung mit ggT < Sonstiges < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Zeige: Für alle natürlichen Zahlen m und n ist [mm] ggT(2^{m} [/mm] - [mm] 1,2^{n} [/mm] - 1) = [mm] 2^{ggT(m,n)} [/mm] - 1 |
Hallo,
ich hab da zu der Aufgabe eine Frage. Ich soll ja diese Gleichung beweisen. Anscheinend gilt sie ja für alle natürlichen Zahlen m und 2. Wenn ich jetzt z.B. für m=4 und für n=2 einsetze, erhalte ich ggT(13,56) = 3, da
[mm] ggT(2^{m} [/mm] - [mm] 1,2^{n} [/mm] - 1) = [mm] ggT(2^{4} [/mm] - [mm] 1,2^{2} [/mm] - 1) = ggT(16 - 1,44 - 1) = ggT(13,56)
und [mm] 2^{ggT(m,n)} [/mm] - 1 = [mm] 2^{ggT(4,2)} [/mm] - 1 = [mm] 2^{2} [/mm] - 1 = 4 - 1 = 3.
Was denke ich falsch? Wieso kommt bei mir raus, dass es nicht gilt?
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:35 Sa 07.12.2013 | | Autor: | abakus |
> Zeige: Für alle natürlichen Zahlen m und n ist [mm]ggT(2^{m}[/mm]
> - [mm]1,2^{n}[/mm] - 1) = [mm]2^{ggT(m,n)}[/mm] - 1
> Hallo,
> ich hab da zu der Aufgabe eine Frage. Ich soll ja diese
> Gleichung beweisen. Anscheinend gilt sie ja für alle
> natürlichen Zahlen m und 2. Wenn ich jetzt z.B. für m=4
> und für n=2 einsetze, erhalte ich ggT(13,56) = 3, da
> [mm]ggT(2^{m}[/mm] - [mm]1,2^{n}[/mm] - 1) = [mm]ggT(2^{4}[/mm] - [mm]1,2^{2}[/mm] - 1) =
> ggT(16 - 1,44 - 1) = ggT(13,56)
> und [mm]2^{ggT(m,n)}[/mm] - 1 = [mm]2^{ggT(4,2)}[/mm] - 1 = [mm]2^{2}[/mm] - 1 = 4 -
> 1 = 3.
>
> Was denke ich falsch? Wieso kommt bei mir raus, dass es
> nicht gilt?
Hallo,
[mm] $2^4-1$ [/mm] und [mm] $2^2-1$ [/mm] sind weder 13 noch 56.
Gruß Abakus
>
>
> Ich habe diese Frage in keinem Forum auf anderen
> Internetseiten gestellt.
|
|
|
| |
|
Versteh ich nicht.
[mm] 2^{4} [/mm] - 1 = 16 - 1 = 15... Oder was denke ich falsch?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:33 Sa 07.12.2013 | | Autor: | abakus |
> Versteh ich nicht.
>
> [mm]2^{4}[/mm] - 1 = 16 - 1 = 15... Oder was denke ich falsch?
Na sicher ist das 15.
Aber lies mal deinen ersten eigenen Post.
Du schreibst da etwas von ggT(13,56).
Diese Schreibweise bedeutet "größter gemeinsamer Teiler von 13 und 56". Das Komma ist ein Trennzeichen zwischen zwei Zahlen 13 und 56 und bedeutet nicht etwa die Dezimalzahl DreizehnKommaFünfSechs.
Ich habe mich schon gewundert, warum bei dir die völlig sinnlose Zahl 1,44 auftauchte.
Es geht in der Aufgabe um den größten gemeinsamen Teiler von [mm]2^m-1[/mm] und [mm]2^n-1[/mm]!
Gruß Abakus
|
|
|
| |
|
Vielen Dank, jetzt verstehe ich erstmal die Aufgabe, dann macht alles plötzlich auch Sinn.
Nun komme ich aber bei der Lösung nicht weiter.
Aber ich hab schon einen Ansatz:
[mm] 2^{m}-1 [/mm] = 1 + 2 + 4 + ... + [mm] 2^{m-1}
[/mm]
[mm] 2^{n}-1 [/mm] = 1 + 2 + 4 + ... + [mm] 2^{n-1}
[/mm]
Nun kann man annehmen, dass m<n gilt, also gilt :
[mm] 2^{m}-1 [/mm] = 1 + 2 + 4 + ... + [mm] 2^{m-1}
[/mm]
[mm] 2^{n}-1 [/mm] = [mm] 2^{m} [/mm] - 1 + ... + [mm] 2^{n-1}
[/mm]
Stimmt das bis hierhin? Und hilft es mir auch irgendwie zum beweisen der Behauptung? Weil ab hier komme ich nicht weiter
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:05 So 08.12.2013 | | Autor: | abakus |
> Vielen Dank, jetzt verstehe ich erstmal die Aufgabe, dann
> macht alles plötzlich auch Sinn.
>
> Nun komme ich aber bei der Lösung nicht weiter.
>
> Aber ich hab schon einen Ansatz:
>
> [mm]2^{m}-1[/mm] = 1 + 2 + 4 + ... + [mm]2^{m-1}[/mm]
> [mm]2^{n}-1[/mm] = 1 + 2 + 4 + ... + [mm]2^{n-1}[/mm]
>
> Nun kann man annehmen, dass m<n gilt, also gilt :
>
> [mm]2^{m}-1[/mm] = 1 + 2 + 4 + ... + [mm]2^{m-1}[/mm]
> [mm]2^{n}-1[/mm] = [mm]2^{m}[/mm] - 1 + ... + [mm]2^{n-1}[/mm]
>
> Stimmt das bis hierhin? Und hilft es mir auch irgendwie zum
> beweisen der Behauptung? Weil ab hier komme ich nicht
> weiter
Hallo,
der ggT von [mm]2^{m}-1[/mm] und [mm]2^{n}-1[/mm] teilt auch die Differenz [mm](2^{n}-1)-(2^{m}-1)[/mm].
Gruß Abakus
|
|
|
|
