ggT < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie für b,m,n [mm] \in \mathbb{N}:
[/mm]
[mm] ggT(b^{m}-1,b^{n}-1)=b^{ggT(m,n)}-1 [/mm] |
Hallo!
Ich hab hier ein Problem bei der einen Richtung. Während die eine, nämlich [mm] \ge [/mm] klar ist, weil [mm] b^{d}-1 b^{n}-1 [/mm] teilt, wann immer d n teilt, sehe ich einfach nicht, wie ich die andere Richtung zeigen soll.
Sei D ein Teiler von [mm] b^{m}-1 [/mm] und [mm] b^{n}-1. [/mm] Zu zeigen: Dann teilt D auch [mm] b^{ggT(m,n)}-1. [/mm] Sei g=ggT(m,n)
Es gibt x und y mit
$ D x = [mm] b^{m}-1 [/mm] = ( [mm] b^{g} [/mm] - 1 ) [mm] \sum_{i=1}^{\frac{m}{g}} b^{m-i*g}$
[/mm]
$ D y = [mm] b^{n} [/mm] -1 = ( [mm] b^{g} [/mm] -1 ) [mm] \sum_{i=1}^{\frac{n}{g}} b^{n-i*g} [/mm] $
Ich sehe aber nicht, wie ich damit dann weiterkomme :(
Es wäre natürlich ausreichend, zu zeigen, dass [mm] \sum_{i=1}^{\frac{m}{g}} b^{m-i*g} [/mm] und [mm] \sum_{i=1}^{\frac{n}{g}} b^{n-i*g} [/mm] relativ prim sind. Aber das seh ich irgendwie auch nicht. Kann man irgendwie einen Widerspruch konstruieren, indem man annimmt sie hätten einen gemeinsamen Primteiler?
|
|
| |
|
Hallo Salamence,
"Richtung" ist auch gut bei einer Gleichung. 
> Zeigen Sie für b,m,n [mm]\in \mathbb{N}:[/mm]
>
> [mm]ggT(b^{m}-1,b^{n}-1)=b^{ggT(m,n)}-1[/mm]
> Hallo!
> Ich hab hier ein Problem bei der einen Richtung. Während
> die eine, nämlich [mm]\ge[/mm] klar ist,
[mm] \ge [/mm] ![[haee]](/images/smileys/haee.gif "[haee]")
> weil [mm]b^{d}-1 b^{n}-1[/mm]
> teilt, wann immer d n teilt, sehe ich einfach nicht, wie
> ich die andere Richtung zeigen soll.
> Sei D ein Teiler von [mm]b^{m}-1[/mm] und [mm]b^{n}-1.[/mm] Zu zeigen: Dann
> teilt D auch [mm]b^{ggT(m,n)}-1.[/mm]
Gute Idee, aber m.E. schwierig zu zeigen. Ich sehe jedenfalls auch gerade nicht, wie das gehen soll.
> Sei g=ggT(m,n)
> Es gibt x und y mit
> [mm]D x = b^{m}-1 = ( b^{g} - 1 ) \sum_{i=1}^{\frac{m}{g}} b^{m-i*g}[/mm]
>
> [mm]D y = b^{n} -1 = ( b^{g} -1 ) \sum_{i=1}^{\frac{n}{g}} b^{n-i*g}[/mm]
>
> Ich sehe aber nicht, wie ich damit dann weiterkomme :(
>
> Es wäre natürlich ausreichend, zu zeigen, dass
> [mm]\sum_{i=1}^{\frac{m}{g}} b^{m-i*g}[/mm] und
> [mm]\sum_{i=1}^{\frac{n}{g}} b^{n-i*g}[/mm] relativ prim sind. Aber
> das seh ich irgendwie auch nicht. Kann man irgendwie einen
> Widerspruch konstruieren, indem man annimmt sie hätten
> einen gemeinsamen Primteiler?
Na, Du kannst auch einen anderen Weg versuchen.
1) Zeige [mm] b^g-1|b^m-1 [/mm] und [mm] b^g-1|b^n-1.
[/mm]
2) Zeige [mm] \ggT{\left(\bruch{b^m-1}{b^g-1},\ \bruch{b^n-1}{b^g-1}\right)}=1.
[/mm]
Dann wärst Du ja auch fertig.
Grüße
reverend
|
|
|
| |
|
> Hallo Salamence,
>
> "Richtung" ist auch gut bei einer Gleichung.
>
> > Zeigen Sie für b,m,n [mm]\in \mathbb{N}:[/mm]
> >
> > [mm]ggT(b^{m}-1,b^{n}-1)=b^{ggT(m,n)}-1[/mm]
> > Hallo!
> > Ich hab hier ein Problem bei der einen Richtung.
> Während
> > die eine, nämlich [mm]\ge[/mm] klar ist,
>
> [mm]\ge[/mm]
>
> > weil [mm]b^{d}-1 b^{n}-1[/mm]
> > teilt, wann immer d n teilt, sehe ich einfach nicht, wie
> > ich die andere Richtung zeigen soll.
> > Sei D ein Teiler von [mm]b^{m}-1[/mm] und [mm]b^{n}-1.[/mm] Zu zeigen: Dann
> > teilt D auch [mm]b^{ggT(m,n)}-1.[/mm]
>
> Gute Idee, aber m.E. schwierig zu zeigen. Ich sehe
> jedenfalls auch gerade nicht, wie das gehen soll.
>
> > Sei g=ggT(m,n)
> > Es gibt x und y mit
> > [mm]D x = b^{m}-1 = ( b^{g} - 1 ) \sum_{i=1}^{\frac{m}{g}} b^{m-i*g}[/mm]
>
> >
> > [mm]D y = b^{n} -1 = ( b^{g} -1 ) \sum_{i=1}^{\frac{n}{g}} b^{n-i*g}[/mm]
>
> >
> > Ich sehe aber nicht, wie ich damit dann weiterkomme :(
> >
> > Es wäre natürlich ausreichend, zu zeigen, dass
> > [mm]\sum_{i=1}^{\frac{m}{g}} b^{m-i*g}[/mm] und
> > [mm]\sum_{i=1}^{\frac{n}{g}} b^{n-i*g}[/mm] relativ prim sind.
> Aber
> > das seh ich irgendwie auch nicht. Kann man irgendwie einen
> > Widerspruch konstruieren, indem man annimmt sie hätten
> > einen gemeinsamen Primteiler?
>
> Na, Du kannst auch einen anderen Weg versuchen.
> 1) Zeige [mm]b^g-1|b^m-1[/mm] und [mm]b^g-1|b^n-1.[/mm]
> 2) Zeige [mm]\ggT{\left(\bruch{b^m-1}{b^g-1},\ \bruch{b^n-1}{b^g-1}\right)}=1.[/mm]
>
> Dann wärst Du ja auch fertig.
>
Das 1. hab ich ja schon gezeigt und das 2. ist ja gerade, dass die beiden relativ prim sind. Wie stellt man das denn an?
Das sind ja beides Summen von Potenzen von [mm] b^{g}
[/mm]
x:=1+ [mm] b^{g} [/mm] + [mm] b^{2*g} [/mm] + ... + [mm] b^{l*g}
[/mm]
y:=1+ [mm] b^{g} [/mm] + ... + [mm] b^{k*g} [/mm]
wobei OE k<l
Wie zeig ich denn jetzt hier ggT(x,y)=1 ?
> Grüße
> reverend
>
|
|
|
| |
|
Hallo nochmal,
> > Na, Du kannst auch einen anderen Weg versuchen.
> > 1) Zeige [mm]b^g-1|b^m-1[/mm] und [mm]b^g-1|b^n-1.[/mm]
> > 2) Zeige [mm]\ggT{\left(\bruch{b^m-1}{b^g-1},\ \bruch{b^n-1}{b^g-1}\right)}=1.[/mm]
> >
> > Dann wärst Du ja auch fertig.
> >
> Das 1. hab ich ja schon gezeigt
So hatte ich das auch verstanden.
> und das 2. ist ja gerade,
> dass die beiden relativ prim sind. Wie stellt man das denn
> an?
> Das sind ja beides Summen von Potenzen von [mm]b^{g}[/mm]
> x:=1+ [mm]b^{g}[/mm] + [mm]b^{2*g}[/mm] + ... + [mm]b^{l*g}[/mm]
> y:=1+ [mm]b^{g}[/mm] + ... + [mm]b^{k*g}[/mm]
> wobei OE k<l
> Wie zeig ich denn jetzt hier ggT(x,y)=1 ?
Wie wärs mit dem euklidischen Algorithmus?
Alternativ kannst du auch zeigen, dass es [mm] s,t\in\IZ [/mm] gibt, so dass $sx+ty=1$ ist. Dazu brauchst Du aber entweder einen Geniestreich oder den erweiterten euklidischen Algorithmus, was es ja nicht gerade vereinfacht.
Dritte Variante: du führst einen Widerspruchsbeweis. Nimm an es gebe ein a mit a|x und a|y. Setze [mm] a=b\pm{i} [/mm] und führe eine Polynomdivision durch. Mühsam, aber möglich.
Grüße
reverend
</l
|
|
|
| |
|
> Hallo nochmal,
>
> > > Na, Du kannst auch einen anderen Weg versuchen.
> > > 1) Zeige [mm]b^g-1|b^m-1[/mm] und [mm]b^g-1|b^n-1.[/mm]
> > > 2) Zeige [mm]\ggT{\left(\bruch{b^m-1}{b^g-1},\ \bruch{b^n-1}{b^g-1}\right)}=1.[/mm]
>
> > >
> > > Dann wärst Du ja auch fertig.
> > >
> > Das 1. hab ich ja schon gezeigt
>
> So hatte ich das auch verstanden.
>
> > und das 2. ist ja gerade,
> > dass die beiden relativ prim sind. Wie stellt man das denn
> > an?
> > Das sind ja beides Summen von Potenzen von [mm]b^{g}[/mm]
> > x:=1+ [mm]b^{g}[/mm] + [mm]b^{2*g}[/mm] + ... + [mm]b^{l*g}[/mm]
> > y:=1+ [mm]b^{g}[/mm] + ... + [mm]b^{k*g}[/mm]
> > wobei OE k<l
> > Wie zeig ich denn jetzt hier ggT(x,y)=1 ?
>
> Wie wärs mit dem euklidischen Algorithmus?
>
> Alternativ kannst du auch zeigen, dass es [mm]s,t\in\IZ[/mm] gibt,
> so dass [mm]sx+ty=1[/mm] ist. Dazu brauchst Du aber entweder einen
> Geniestreich oder den erweiterten euklidischen Algorithmus,
> was es ja nicht gerade vereinfacht.
>
> Dritte Variante: du führst einen Widerspruchsbeweis. Nimm
> an es gebe ein a mit a|x und a|y. Setze [mm]a=b\pm{i}[/mm] und
> führe eine Polynomdivision durch. Mühsam, aber möglich.
>
> Grüße
> reverend
> </l
>
Ich weiß nicht, wie der euklidische Algorithmus hier helfen soll...
[mm] \sum_{i=0}^{l} (b^{g})^{i} [/mm] = [mm] (b^{g})^{l-k} \sum_{i=0}^{k}(b^{g})^{i} [/mm] + [mm] \sum_{i=0}^{l-k-1}(b^{g})^{i}
[/mm]
[mm] \sum_{i=0}^{k} (b^{g})^{i} [/mm] = [mm] (b^{g})^{2*k-l+1} \sum_{i=0}^{l-k-1}(b^{g})^{i} [/mm] + [mm] \sum_{i=0}^{2*k-l} (b^{g})^{i}
[/mm]
[mm] \sum_{i=0}^{l-k-1} (b^{g})^{i} [/mm] = [mm] (b^{g})^{2*l-3*k-1} \sum_{i=0}^{2*k-l} (b^{g})^{i} [/mm] + [mm] \sum_{i=0}^{2*l-3*k-2} (b^{g})^{i}
[/mm]
[mm] \sum_{i=0}^{2*k-l} (b^{g})^{i} [/mm] = [mm] (b^{g})^{5*k-3*l+2} \sum_{i=0}^{2*l-3*k-2} (b^{g})^{i} [/mm] + [mm] \sum_{i=0}^{5*k-3*l+1} (b^{g})^{i}
[/mm]
...
Da kommt man doch zu keinem Ergebnis.
|
|
|
| |
|
Hallo Salamence,
> Ich weiß nicht, wie der euklidische Algorithmus hier
> helfen soll...
>
> [mm]\sum_{i=0}^{l} (b^{g})^{i}[/mm] = [mm](b^{g})^{l-k} \sum_{i=0}^{k}(b^{g})^{i}[/mm]
> + [mm]\sum_{i=0}^{l-k-1}(b^{g})^{i}[/mm]
>
> [mm]\sum_{i=0}^{k} (b^{g})^{i}[/mm] = [mm](b^{g})^{2*k-l+1} \sum_{i=0}^{l-k-1}(b^{g})^{i}[/mm]
> + [mm]\sum_{i=0}^{2*k-l} (b^{g})^{i}[/mm]
>
> [mm]\sum_{i=0}^{l-k-1} (b^{g})^{i}[/mm] = [mm](b^{g})^{2*l-3*k-1} \sum_{i=0}^{2*k-l} (b^{g})^{i}[/mm]
> + [mm]\sum_{i=0}^{2*l-3*k-2} (b^{g})^{i}[/mm]
>
> [mm]\sum_{i=0}^{2*k-l} (b^{g})^{i}[/mm] = [mm](b^{g})^{5*k-3*l+2} \sum_{i=0}^{2*l-3*k-2} (b^{g})^{i}[/mm]
> + [mm]\sum_{i=0}^{5*k-3*l+1} (b^{g})^{i}[/mm]
> ...
> Da kommt man doch zu keinem Ergebnis.
Oh, doch...
Das ist am einfachsten zu sehen in einem b-adischen System.
Schaus Dir mal exemplarisch dezimal an, es funktioniert zu jeder anderen Basis aber genauso.
Sowohl [mm] (b^m-1)/(b^g-1) [/mm] als auch [mm] (b^n-1)/(b^g-1) [/mm] sind so gebaut (wie Du ja sichtlich längst erkannt hast):
1000...1000...1
wobei die Zahl der Nullen jeder Gruppe eben g-1 ist und es insgesamt m/g bzw. n/g Einsen gibt.
Nehmen wir mal m=12, n=15, g=ggT(12,15)=3.
Dann ist [mm] (b^m-1)/(b^g-1)=1001001001 [/mm] im b-adischen System.
Und [mm] (b^n-1)/(b^g-1)=1001001001001.
[/mm]
So ist doch anschaulich, was bei Euklid passiert.
Und dann auch, warum es keinen weiteren Teiler geben kann...
m/g und n/g sind ja relativ prim zueinander.
Grüße
reverend
|
|
|
| |
|
z.z. [mm]\operatorname{ggT}(b^n-1,b^m-1)=b^{\operatorname{ggT}(n,m)}-1[/mm]
Du hattest schon geschrieben [mm]d:=\operatorname{ggT}(m,n)[/mm] und gezeigt, dass [mm]b^d-1 \mid b^n-1[/mm] und [mm]b^d-1 \mid b^m-1[/mm] gilt.
Mit der Idee von reverend die Aufgabe mit Bezout zu schlachten kann man so beginnen:
Nach Bezout gibt es x,y mit xm+yn=d.
Es muss gelten [mm]x*y\leq 0[/mm]! Warum?
O.B.d.A sei nun x>0 und y<=0.
Setze [mm]e:=\operatorname{ggT}(b^n-1,b^m-1)[/mm]. Dann teilt e sowohl [mm]b^{mx}-1[/mm] als auch [mm]b^{-ny}-1[/mm]
Jetzt du.
Alternative (ohne Gewähr):
Man zeigt, dass alle Teiler der linken Seite [mm]\operatorname{ggT}(b^n-1,b^m-1)[/mm] auch Teiler der rechten Seite sind:
[mm]b^m\equiv 1 \mod d \wedge b^m\equiv 1 \mod d \gdw ord_d(b)\mid m \wedge ord_d(b)\mid m \gdw ord_d(b)\mid \operatorname{ggT}(m,n) \gdw b^{\operatorname{ggT}}=1[/mm]
|
|
|
|
