ggT(10^m+1,10^n+1) < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | i) Zeige, dass für [mm] m\equiv [/mm] 0 (mod n) und m>0 gilt
[mm] ggT(10^m+1,10^n+1)=1 [/mm] oder [mm] 10^n+1
[/mm]
ii) Zeige auch, dass für [mm] m\equiv [/mm] 1 (mod n) und m>0 gilt
[mm] ggT(10^m+1,10^n+1)=1 [/mm] oder 11. |
Hi,
versuchen wir vielleicht erstmal mal die i).
Ich verstehe gerade nicht genau, wie man diese Kongruenzen benutzen soll, könnt ihr mir das vielleicht sagen?
Ansonsten habe ich so angefangen:
[mm] ggT(10^m+1,10^n+1) [/mm] mit dem E.A. erhält man:
[mm] 10^m+1=(10^n+1)(10^m+1)-10^{2n+m}
[/mm]
[mm] 10^n+1=(-10^{2n+m})(-10^{3n-m}+1
[/mm]
[mm] -10^{2n+m}=1(-10^{2n+m})+0
[/mm]
Damit wäre [mm] ggT(10^m+1,10^n+1)=1, [/mm] aber wie kommt man auf [mm] ggT(10^m+1,10^n+1)=10^n+1???
[/mm]
Ist meine Rechnung so oben überhaupt richtig?? war mir nicht sicher, ob man das so machen kann, weil ich ja den Rest negativ gewähl habe.
Grüße
|
|
| |
|
Hallo jaruleking,
> i) Zeige, dass für [mm]m\equiv[/mm] 0 (mod n) und m>0 gilt
>
> [mm]ggT(10^m+1,10^n+1)=1[/mm] oder [mm]10^n+1[/mm]
>
>
> ii) Zeige auch, dass für [mm]m\equiv[/mm] 1 (mod n) und m>0 gilt
>
> [mm]ggT(10^m+1,10^n+1)=1[/mm] oder 11.
> Hi,
>
> versuchen wir vielleicht erstmal mal die i).
>
> Ich verstehe gerade nicht genau, wie man diese Kongruenzen
> benutzen soll, könnt ihr mir das vielleicht sagen?
Du kannst hier ersetzen m=a*n mit [mm] a\in\IN.
[/mm]
> Ansonsten habe ich so angefangen:
>
> [mm]ggT(10^m+1,10^n+1)[/mm] mit dem E.A. erhält man:
>
> [mm]10^m+1=(10^n+1)(10^m+1)-10^{2n+m}[/mm]
Das stimmt doch schon nicht.
> [mm]10^n+1=(-10^{2n+m})(-10^{3n-m}+1[/mm]
>
> [mm]-10^{2n+m}=1(-10^{2n+m})+0[/mm]
>
> Damit wäre [mm]ggT(10^m+1,10^n+1)=1,[/mm] aber wie kommt man auf
> [mm]ggT(10^m+1,10^n+1)=10^n+1???[/mm]
Beispiele:
[mm] 10^6+1=(10^2+1)*9901,\quad 10^9+1=(10^3+1)*19*52579,\quad 10^{25}+1=(10^5+1)*251*5051*78.875.943.472.201
[/mm]
> Ist meine Rechnung so oben überhaupt richtig?? war mir
> nicht sicher, ob man das so machen kann, weil ich ja den
> Rest negativ gewähl habe.
Letzteres ist kein Problem, aber die Rechnung ist falsch.
Überleg doch mal, in welchen Fällen [mm] (10^m+1) [/mm] ein Vielfaches von [mm] (10^n+1) [/mm] ist.
Grüße
reverend
|
|
|
| |
|
Hi
ich bin hier gerade am probieren, aber irgendwie komme ich nicht weiter.
> Du kannst hier ersetzen m=a*n mit $ [mm] a\in\IN. [/mm] $
> Ansonsten habe ich so angefangen:
>
> $ [mm] ggT(10^m+1,10^n+1) [/mm] $ mit dem E.A. erhält man:
D.h. ich kann auch so anfangen:
[mm] ggT(10^{an}+1,10^n+1) [/mm] , oder??
[mm] 10^{an}+1 [/mm] = [mm] (10^n+1) [/mm] ....
komm da nicht weiter
|
|
|
| |
|
Moin jaruleking,
> > Du kannst hier ersetzen m=a*n mit [mm]a\in\IN.[/mm]
>
> > Ansonsten habe ich so angefangen:
> >
> > [mm]ggT(10^m+1,10^n+1)[/mm] mit dem E.A. erhält man:
>
>
> D.h. ich kann auch so anfangen:
>
> [mm]ggT(10^{an}+1,10^n+1)[/mm] , oder??
>
> [mm]10^{an}+1[/mm] = [mm](10^n+1)[/mm] ....
Für a ungerade gilt mit [mm] z:=10^n [/mm] (Teleskopsumme):
[mm] 10^{an}+1=z^a+1=(z+1)(z^{a-1}-z^{a-2}+z^{a-3}-\ldots+1)
[/mm]
LG
|
|
|
| |
|
Hi,
> $ [mm] ggT(10^{an}+1,10^n+1) [/mm] $ , oder??
>
> $ [mm] 10^{an}+1 [/mm] $ = $ [mm] (10^n+1) [/mm] $ ....
> Für a ungerade gilt mit $ [mm] z:=10^n [/mm] $ (Teleskopsumme):
$ [mm] 10^{an}+1=z^a+1=(z+1)(z^{a-1}-z^{a-2}+z^{a-3}-\ldots+1) [/mm] $
Aber dadurch wird es doch nur noch komplizierter, oder?? Denn so wüsste ich jetzt auch nicht, wie ich den E.A. anwenden soll :-//
|
|
|
| |
|
Hallo nochmal,
> > [mm]ggT(10^{an}+1,10^n+1)[/mm] , oder??
> >
> > [mm]10^{an}+1[/mm] = [mm](10^n+1)[/mm] ....
>
> > Für a ungerade gilt mit [mm]z:=10^n[/mm] (Teleskopsumme):
>
> [mm]10^{an}+1=z^a+1=(z+1)(z^{a-1}-z^{a-2}+z^{a-3}-\ldots+1)[/mm]
>
>
> Aber dadurch wird es doch nur noch komplizierter, oder??
> Denn so wüsste ich jetzt auch nicht, wie ich den E.A.
> anwenden soll :-//
Nein, dadurch wird dieser Fall so einfach, dass du den E.A. überhaupt nicht mehr anzuwenden brauchst. Es steht doch alles schon da!
Grüße
reverend
|
|
|
| |
|
hi,
ich sehe irgendwie immer noch nicht, wieso von
[mm] 10^{an}+1=z^a+1=(z+1)(z^{a-1}-z^{a-2}+z^{a-3}-\ldots+1) [/mm]
und
[mm] 10^{n}+1
[/mm]
der ggT jetzt 1 oder [mm] 10^{n}+1 [/mm] sein soll. Kannst du mir das vielleicht nochma erklären?
und das gilt ja jetzt nur für a ungerade. Was ist mit dem Fall a gerade??
|
|
|
| |
|
Hallo,
[mm] 10^{an}+1=10^m+1 [/mm] und [mm] z=10^n
[/mm]
Also ist gezeigt, dass [mm] 10^n+1 [/mm] ein Teiler von [mm] 10^m+1 [/mm] ist, wenn a ungerade ist, und damit ist der ggT doch auch klar.
Für gerade a tritt der andere Fall ein, die beiden Zahlen sind dann teilerfremd.
Das kannst Du mit dem E.A. zeigen, oder vielleicht einfacher mit dem ![[]](/images/popup.gif) Lemma von Bézout.
Grüße
reverend
|
|
|
| |
|
Hi,
ok vielen Dank.
Und wie könnte man ii), also
> ii) Zeige auch, dass für $ [mm] m\equiv [/mm] $ 1 (mod n) und m>0 gilt
> $ [mm] ggT(10^m+1,10^n+1)=1 [/mm] $ oder 11.
lösen, wenn m=a*n+1 ist??
|
|
|
| |
|
Hallo nochmal,
> Und wie könnte man ii), also
>
> > ii) Zeige auch, dass für [mm]m\equiv[/mm] 1 (mod n) und m>0 gilt
>
> > [mm]ggT(10^m+1,10^n+1)=1[/mm] oder 11.
>
> lösen, wenn m=a*n+1 ist??
Zeig doch erstmal, dass [mm] 11|10^k+1 [/mm] genau dann wahr ist, wenn k ungerade ist. Der Rest findet sich dann leichter...
Grüße
revernd
|
|
|
| |
|
Hi,
> ii) Zeige auch, dass für $ [mm] m\equiv [/mm] $ 1 (mod n) und m>0 gilt
>
> $ [mm] ggT(10^m+1,10^n+1)=1 [/mm] $ oder 11.
>
> lösen, wenn m=a*n+1 ist??
> Zeig doch erstmal, dass $ [mm] 11|10^k+1 [/mm] $ genau dann wahr ist, wenn k ungerade ist. Der Rest findet sich dann leichter...
steht dieses k bei dir für m und für n?? Oder kannste mir vielleicht nochmal erklären, wie du das ersetzt hast?
Und für die Div habe ich das dann wie folgt gemacht:
[mm] 10^k+1=\{10+1, 1000+1, 100000+1, 10000000+1,.....\} [/mm]
So und diese Zahlen sind immer durch 11 teilbar. Oder aber auch so:
[mm] 10^0 \equiv [/mm] 1 (mod 11)
[mm] 10^1 \equiv [/mm] -1 (mod 11)
[mm] 10^2 \equiv [/mm] 1 (mod 11)
[mm] 10^3 [/mm] = [mm] (-1)*10^2 \equiv [/mm] -1 (mod 11)
[mm] 10^4 =(-1)*10^3 \equiv [/mm] 1 (mod 11)
=> 10k [mm] \equiv (-1)^k [/mm] (mod 11)
=> für ungerade k teilt 11 [mm] 10^k [/mm] +1 mit Rest 0
=> für gerade k teilt 11 [mm] 10^k [/mm] +1 mit Rest 2
Jetzt weiß ich gerade nicht, wie ich diese Ergebnisse auf [mm] ggT(10^m+1,10^n+1) [/mm] übertragen kann?
Könnt ihr mir vielleicht dabei nochmal helfen??
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:24 Mo 06.06.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
