Aussage über ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 18:10 Sa 20.04.2013 | | Autor: | Rubix |
| Aufgabe | Zeigen Sie, dass gilt:
[mm] ggT(a^m-1,a^n -1)=a^{ggT(m,n)}-1
[/mm]
Hinweis: [mm] ggT(a^m-1, a^n-1)=ggT(a^{m-n}-1,a^n-1) [/mm] |
Hallo,
stecke bei obiger Aufgabe fest. Habe den Hinweis bereits gezeigt und versucht ggT(m,n)= [mm] k_{1}*m+k_{2}*n [/mm] für [mm] k_{1}, k_{2}\in \IN [/mm] zusetzen um so eventuell weiterzukommen und erhalte damit:
[mm] ggT(a^m-1,a^n -1)=ggT(a^{m+k_{2}*n}-1,a^n [/mm] -1)
und wollte das dann mit dem Hinweis zu [mm] ggT(a^m-1,a^n -1)=ggT(a^{k_{1}*m+k_{2}*n}-1, a^{k_{1}*m+k_{2}*n}-1) [/mm] umformen womit die Aussage gezeigt wäre.
Das schein allerdings nicht aufzugehen und ich bräuchte nun einen Hinweis. Ich bedanke mich für Antworten.
Gruß Rubix
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:15 Sa 20.04.2013 | | Autor: | valoo |
Tipp: Induktion nach der Summe von n+m. Für n=m oder eine von beiden 0 ist die Aussage klar. Dann benutzt du den Hinweis und die Induktionsvoraussetzung und bist fertig.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:35 Sa 20.04.2013 | | Autor: | Rubix |
Hallo,
du meinst einen Induktionsschritt der etwa so aussieht?
[mm] ggT(a^{m+n+1}-1, a^n-1)=ggT(a^{m+1}-1, a^n-1)=a^{ggT(m+1,n)}=a^{ggT(m+n+1,n)}
[/mm]
Das sieht gut aus. Danke.
Gruß
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 18:45 Sa 20.04.2013 | | Autor: | valoo |
Erstmal fehlt da die -1 und zweitens ist da die Summe links [mm] m+2 n+1 [/mm] und rechts [mm] m+n+1 [/mm]. Du solltest da nicht einfach plötzlich nen n in den Exponenten zum m schreiben...
Angenommen, die Aussage gilt für alle [mm] n'+m'< n + m [/mm] Und sei ohne Einschränkung n > m. Dann gilt:
[mm] ggT(b^{n}-1, b^{m}-1)=ggT(b^{n-m}-1, b^{m}-1) \stackrel{IV}{=}b^{ggT(n-m,m)}-1= b^{ggT(n,m)}-1
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:07 Sa 20.04.2013 | | Autor: | Rubix |
OK, super verstanden. Danke.
Gruß
|
|
|
|
