Kongruenzen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | (i) Für ungerade v und r [mm] \ge [/mm] 3 zeige [mm] v^{2^{r-2}} \equiv [/mm] 1 mod [mm] 2^r.
[/mm]
(ii) Zeige [mm] 5^{2^{r}}-1=2^{r+2}*v, [/mm] 2 teilt nicht v.
(iii) Folgere ord [mm] \overline{5} [/mm] = [mm] 2^{r-2} [/mm] in [mm] (\IZ/ 2^r \IZ)^{\times}
[/mm]
(iv) Zeige: die Zahlen [mm] \pm 5^{i} [/mm] für [mm] i=1,...,2^{r-2} [/mm] sind paarweise inkongurent mod [mm] 2^r. [/mm] |
Hallöchen,
ich gehe gerade meine alten Übungsaufgaben durch und diese macht mir ziemliche Probleme und ich hoffe jemand kann mir helfen.
Ich habe mich erstmal mit der Teilaufgabe (i) beschäftigt. Ich weiß nur leider nicht recht wie ich anfangen soll.
Allgemein ist ja klar, dass [mm] v^{2^{r-2}} [/mm] aufjedenfall ungerade ist aber wie kann ich folgen, dass es gerade für [mm] 2^r [/mm] den Rest 1 hat?
Hat da jemand einen Hinweis für mich?
Liebe Grüße
Schmetterfee
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 15:10 Fr 06.01.2012 | | Autor: | hippias |
Ihr habt bestimmt den kleinen Satz von Fermat besprochen...
|
|
|
| |
|
Hallöchen,
ja das haben wir aber ich weiß nicht ganz wie ich das nutzen kann. Der kleine Satz von Fermat besagt, ja:
[mm] a^{\phi(m)} \equiv [/mm] 1 mod m wenn (a,m)=1
so ich weiß, dass [mm] (v,2^r)=1
[/mm]
Muss ich denn nun zeigen, dass [mm] \phi(2^r)= 2^{r-2} [/mm] ist? Oder bin ich jetzt auf einem ganz falschen weg?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:50 Sa 07.01.2012 | | Autor: | hippias |
Aber ja, berechne [mm] $\phi(2^{r})$. [/mm] Wenn Du die Zahl bestimmt hast, sehen wir weiter.
|
|
|
| |
|
Hallöchen
> Aber ja, berechne [mm]\phi(2^{r})[/mm]. Wenn Du die Zahl bestimmt
> hast, sehen wir weiter.
wenn ich das aber berechne erhalte ich:
[mm] \phi (2^r)=2^r [/mm] - [mm] 2^{r-1}=2^{r-1} [/mm] (2-1)= [mm] 2^{r-1}
[/mm]
Wo ist denn nun mein Denkfehler, weil ich müsste doch eigentlich [mm] 2^{r-2} [/mm] raus bekommen oder?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:38 Sa 07.01.2012 | | Autor: | hippias |
> Hallöchen
>
> > Aber ja, berechne [mm]\phi(2^{r})[/mm]. Wenn Du die Zahl bestimmt
> > hast, sehen wir weiter.
>
>
> wenn ich das aber berechne erhalte ich:
> [mm]\phi (2^r)=2^r[/mm] - [mm]2^{r-1}=2^{r-1}[/mm] (2-1)= [mm]2^{r-1}[/mm]
>
> Wo ist denn nun mein Denkfehler, weil ich müsste doch
> eigentlich [mm]2^{r-2}[/mm] raus bekommen oder?
>
> Liebe Grüße
> Schmetterfee
Du hast alles richtig gemacht, jedoch genuegt wie so oft nicht nur ein einziger Gedanke. Wir haben also [mm] $v^{2^{r-1}}-1= [/mm] 0$ mod [mm] $2^{r}$. [/mm] Jetzt versuche weitere Schlussfolgerungen zu ziehen; z.B. koennte man versuchen zu faktorisieren, um irgendiwe auf einen Ausdruck mit [mm] $v^{2^{r-2}}$ [/mm] zu kommen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:13 Sa 07.01.2012 | | Autor: | hippias |
Hallo Schmetterfee: Ich glaube der Weg, auf den ich Dich gefuehrt habe, ist nicht der beste. Induktion erscheint mir einfacher, z.B. der Induktionsschritt: Sei [mm] $v^{2^{r-2}}= 2^{r}q+1$. [/mm] Dann ist [mm] $v^{2^{r-1}}= (v^{2^{r-2}})^{2}= (2^{r}q+1)^{2}= 2^{2r}q^{2}+ 2^{r+1}q+1$. [/mm] Fehlt nur noch der Induktionsanfang. Tut mir Leid, aber wenigstens konnten wir den kleinen Satz von Fermat wiederholen.
|
|
|
| |
|
Hallöchen,
okay ich habe mir nun Gedanken über den Induktionsanfang gemacht. aber ich weiß irgendwie nicht wie ich dafür zeigen soll, dass
[mm] v^2 \equiv [/mm] 1 mod 8?
Ich hab es an Beispielen ausprobiert und gesehen, dass es funktioniert. Ich weiß nur leider nicht wie ich dafür ansetzen kann. Mir macht das Rechnen mit modulo noch ziemliche Probleme:-(
Liebe Grüße Schmetterfee
|
|
|
| |
|
> Hallöchen,
>
> okay ich habe mir nun Gedanken über den Induktionsanfang
> gemacht. aber ich weiß irgendwie nicht wie ich dafür
> zeigen soll, dass
> [mm]v^2 \equiv[/mm] 1 mod 8?
Hallo,
v ist ungerade, also kannst Du v schreiben als v=2n+1.
Nun überlege Dir, warum [mm] v^2-1 [/mm] ein Vielfaches von 8 ist.
LG Angela
|
|
|
| |
|
Hallo,
ich habe mir das nun wie folgt überlegt.
zZ. [mm] v^2 \equiv [/mm] 1 mod 8 für v ungerade.
Also muss ich zeigen, dass [mm] v^2-1 [/mm] durch 8 teilbar ist. Da v ungerade ist gilt:
[mm] v^2=(2n+1)^2=4n^2+4n+1
[/mm]
Also habe ich:
[mm] 4n^2-4n+1-1 [/mm] soll durch 8 teilbar sein.
Es muss also [mm] 4(n^2+n) [/mm] durch 8 teilbar sein. Das ist nur dann der Fall wenn der Ausdruck in der Klammer eine gerade Zahl ist. Das ist aber immer der Fall, weil
(i) wenn n gerade ist [mm] n^2 [/mm] gerade und n sowieso und somit auch die Summe
und für (ii) n ungerade ist [mm] n^2 [/mm] ungerade und n auch und somit die Summe wieder gerade.
Geht dies auch irgendwie formaler oder ist diese argumentative Begründung völlig ausreichend?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
Hallo,
ich finde die Argumentation ausreichend.
Du kannst aber auch [mm] 4n^2+4n [/mm] schreiben als 4n(n+1).
Dem Argument, daß entweder n oder n+1 gerade ist, kann sich niemand verschließen.
LG Angela
|
|
|
| |
|
Danke schön für die liebe Hilfe
Liebe Grüße
Schmetterfee
|
|
|
| |
|
Hallöchen,
ich habe mich während dessen auch schon mit dem Aufgabenteil (ii) beschäftigt.
Es ist ja nun zu zeigen, dass [mm] 5^{2^{r}}-1=2^{r+2}*v [/mm] für 2 teilt nicht v
Ich weiß also wieder, dass v ungerade ist und die Form 2n+1 hat. Wenn ich das einsetze erhalte ich:
[mm] 5^{2^{r}}-1= 2^{r+2}*(2n+1)
[/mm]
= [mm] 2^{r+3}+ 2^{r+2}
[/mm]
Ich habe aber leider nicht das Gefühl, dass mich das irgendwie weiter bringt. Hat jemand nen Tipp für mich wie ich anders ansetzen kann um vielleicht doch zum gewünschten Ziel zu gelangen?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:52 Di 10.01.2012 | | Autor: | hippias |
Auch hier duerfte Induktion nach $r$ zum Erfolg fuehren. Tip: Faktorisiere im Induktionsschritt mit 3.ter bin. Formel.
Das gleiche Prinzip duerfte auch geeignet sein, um einen alterativen Beweis zur 1.sten Aufgabe zu bekommen. Ich haette gerne die erste Teilaufgabe fuer den zweiten Teil benutzt, aber das erscheint mir unnoetig kompliziert. Vielleicht taeusche ich mich.
|
|
|
| |
|
Hallöchen,
ich habe jetzt den ganzen Tag mit dieser Aufgabe rum hantiert. Ich komme aber einfach auf keinen grünen Zweig. Der Induktionsanfang war ja kein Problem. Dann habe ich im Induktionsschritt versucht deinen Tipp zu berücksichtigen. Bin aber nur bis:
[mm] 5^{2^{r+1}} -1=2^{(r+1)+2}*v
[/mm]
[mm] \Rightarrow (5^{r+1})^2-1^2=2^{r+3}*v
[/mm]
[mm] \Rightarrow (5^{r+1}+1)-(5^{r+1}-1)=2^{r+3}*v
[/mm]
aber an dieser Stelle weiß ich leider einfach nicht wie ich weiter um formen kann. Oder wie ich überhaupt weiter komme. Hat noch jemand einen Tipp für mich?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:31 Mi 11.01.2012 | | Autor: | hippias |
> Hallöchen,
>
> ich habe jetzt den ganzen Tag mit dieser Aufgabe rum
> hantiert. Ich komme aber einfach auf keinen grünen Zweig.
> Der Induktionsanfang war ja kein Problem. Dann habe ich im
> Induktionsschritt versucht deinen Tipp zu berücksichtigen.
> Bin aber nur bis:
> [mm]5^{2^{r+1}} -1=2^{(r+1)+2}*v[/mm]
> [mm]\Rightarrow (5^{r+1})^2-1^2=2^{r+3}*v[/mm]
>
> [mm]\Rightarrow (5^{r+1}+1)-(5^{r+1}-1)=2^{r+3}*v[/mm]
Das verstehe ich ueberhaupt nicht.
>
> aber an dieser Stelle weiß ich leider einfach nicht wie
> ich weiter um formen kann. Oder wie ich überhaupt weiter
> komme. Hat noch jemand einen Tipp für mich?
>
> Liebe Grüße
> Schmetterfee
Ich meinte es so: [mm] $5^{2^{r+1}} [/mm] -1= [mm] (5^{2^{r}} -1)(5^{2^{r}} [/mm] +1)$; das ist einfach 3. bin. Formel. Nach IV ist [mm] $5^{2^{r}} [/mm] -1= [mm] 2^{r+2}v$, [/mm] $v$ ungerade. Einsetzen liefert Dir die Behauptung.
|
|
|
| |
|
Hallöchen,
oh sorry da habe ich aber wirklich viel durcheinander geworfen.
Naja der Induktionsschritt klappt bei mir trotzdem nicht. Ich komme nun soweit:
[mm] 5^{2^{r+1}}-1=2^{(r+1)+2} [/mm] *v
[mm] (5^{2^{r}}-1)(5^{2^{r}}+1)=2^{r+3}*v
[/mm]
[mm] 2^{r+2}*v (5^{2^{r}}+1)=2^{r+3}*v
[/mm]
[mm] 5^{2^{r}}+1=2
[/mm]
aber das bringt mich ja kein Stück weiter. Was mache ich denn nun wieder falsch?
Liebe Grüße Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:16 Mi 11.01.2012 | | Autor: | hippias |
> Hallöchen,
>
> oh sorry da habe ich aber wirklich viel durcheinander
> geworfen.
>
> Naja der Induktionsschritt klappt bei mir trotzdem nicht.
> Ich komme nun soweit:
> [mm]5^{2^{r+1}}-1=2^{(r+1)+2}[/mm] *v
> [mm](5^{2^{r}}-1)(5^{2^{r}}+1)=2^{r+3}*v[/mm]
> [mm]2^{r+2}*v (5^{2^{r}}+1)=2^{r+3}*v[/mm]
> [mm]5^{2^{r}}+1=2[/mm]
> aber das bringt mich ja kein Stück weiter. Was mache ich
> denn nun wieder falsch?
>
> Liebe Grüße Schmetterfee
Mit Deinem Induktionsschritt kann ich auch nicht viel anfangen. Ich wuerde es so vorschlagen:
$ [mm] 5^{2^{r+1}} [/mm] -1= [mm] (5^{2^{r}} -1)(5^{2^{r}} [/mm] +1) $; das ist einfach 3. bin. Formel. Nach IV ist $ [mm] 5^{2^{r}} [/mm] -1= [mm] 2^{r+2}v [/mm] $, $ v $ ungerade. Einsetzen liefert $ [mm] 5^{2^{r+1}} [/mm] -1= [mm] 2^{r+2}v(2^{r+2}v+2)= 2^{r+3}v(2^{r+1}v+1)$. [/mm] Die $2$-Potenz hat den richtigen Exponenten: mache Dir nur noch klar, dass [mm] $v(2^{r+1}v+1)$ [/mm] ungerade ist.
|
|
|
| |
|
Hallöchen,
die Argumentation ist dann ja leicht zu führen.
Denn der Ausdruck in der Klammer ist insgesamt ungerade und das Produkt zweier ungeraden Zahlen ist auch wieder ungerade. Mein Problem beim Induktionsschritt war, dass ich fälschlicherweise immer von der Gleichung ausgegangen bin und versucht habe so umzuformen, dass eine wahre Aussage heraus kommt. Dummer Fehler.
LG Schmetterfee
|
|
|
| |
|
Hallöchen
bei dieser Aufgabe soll ich ja nun zeigen, dass
ord [mm] \overline{5} [/mm] = [mm] 2^{r-2} [/mm] in [mm] (\IZ/2^r \IZ)^{\times}
[/mm]
Ich habe dies auch per Induktion versucht bin aber nur zu eindem Induktionsanfang für r=3 gekommen.
Die Ordnung eines Elementes gibt ja an wie oft ich es mit sich selbst multiplizieren muss um die Restklasse der 1 zu erzeugen.
Ist meine Idee mit Induktion für diese Aufgabe überhaupt sinnvoll oder sollte ich es doch lieber direkt versuchen?
LG Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:48 Mi 11.01.2012 | | Autor: | hippias |
> Hallöchen
>
> bei dieser Aufgabe soll ich ja nun zeigen, dass
> ord [mm]\overline{5}[/mm] = [mm]2^{r-2}[/mm] in [mm](\IZ/2^r \IZ)^{\times}[/mm]
>
> Ich habe dies auch per Induktion versucht bin aber nur zu
> eindem Induktionsanfang für r=3 gekommen.
>
> Die Ordnung eines Elementes gibt ja an wie oft ich es mit
> sich selbst multiplizieren muss um die Restklasse der 1 zu
> erzeugen.
>
> Ist meine Idee mit Induktion für diese Aufgabe überhaupt
> sinnvoll oder sollte ich es doch lieber direkt versuchen?
>
> LG Schmetterfee
Du kannst hierfuer sehr schoen die vorherige Teilaufgabe benutzen; da ist dann vielleicht gar keine Induktion mehr notwendig
|
|
|
| |
|
Hallöchen
ich habe es nun mit Umformungen bei (ii) versucht komme aber einfach nicht zum gewünschten.
Ich weiß ja nun bereits, dass
[mm] 5^{2^{r}}-1=2^{r+2}*v
[/mm]
Also dachte ich mir könnte ich einfach Äquivalenzumformungen vornehmen, wie
[mm] 5^{2^{r}}=2^{r+2}*v+1
[/mm]
Doch hier komme ich nicht weiter. Wurzel ziehen kann ich nicht. Binomische Formel lässt sich auch nicht anwenden. Hast du noch nen Tipp wie ich weiter vorgehen muss oder ist schon die Idee über Umformungen schwachsinnig?
LG Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:00 Do 12.01.2012 | | Autor: | hippias |
> Hallöchen
>
> ich habe es nun mit Umformungen bei (ii) versucht komme
> aber einfach nicht zum gewünschten.
>
> Ich weiß ja nun bereits, dass
> [mm]5^{2^{r}}-1=2^{r+2}*v[/mm]
> Also dachte ich mir könnte ich einfach
> Äquivalenzumformungen vornehmen, wie
> [mm]5^{2^{r}}=2^{r+2}*v+1[/mm]
> Doch hier komme ich nicht weiter. Wurzel ziehen kann ich
> nicht. Binomische Formel lässt sich auch nicht anwenden.
> Hast du noch nen Tipp wie ich weiter vorgehen muss oder ist
> schon die Idee über Umformungen schwachsinnig?
>
> LG Schmetterfee
Das scheint mir alles wenig hilfreich zu sein: sage mir doch einmal wie die Ordnung eines Gruppenelementes definiert ist. Wenn Du Dir das klargemacht hast, dann wirst Du sicher auch auf einen guten Loesungsweg kommen. Es sind naemlich im Grunde zwei Bedingungen zu ueberpruefen.
|
|
|
| |
|
Hallöchen
> Das scheint mir alles wenig hilfreich zu sein: sage mir
> doch einmal wie die Ordnung eines Gruppenelementes
> definiert ist. Wenn Du Dir das klargemacht hast, dann wirst
> Du sicher auch auf einen guten Loesungsweg kommen. Es sind
> naemlich im Grunde zwei Bedingungen zu ueberpruefen.
Okay also ein neuer Versuch.
Die Ordnung eines Elementes x ist definiert als ord x= min [mm] \{n \in \IN | x^n=1 \}
[/mm]
wenn ich (ii) nutzen sollte, müsste ich also wahrscheinlich zeigen, dass
[mm] \frac{5^{2^{r}}}{2^{r+2}*v}=1
[/mm]
aber da lässt sich dann ja auch wieder nichts umformen und ich weiß hier echt nicht weiter:-(
und wenn ich wie oben umformen würde würde ich ja auch nicht auf eine Potenz von [mm] 2^{r-2} [/mm] kommen
Denn eigentlich will ich ja nachweisen, dass [mm] 5^{2^{r-2}}=1 [/mm] ist ich finde nur leider keinen Ansatzpunkt wo ich anfangen kann. Kannst du mir da vielleicht noch helfen?
LG
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:42 Do 12.01.2012 | | Autor: | hippias |
> Hallöchen
> > Das scheint mir alles wenig hilfreich zu sein: sage mir
> > doch einmal wie die Ordnung eines Gruppenelementes
> > definiert ist. Wenn Du Dir das klargemacht hast, dann wirst
> > Du sicher auch auf einen guten Loesungsweg kommen. Es sind
> > naemlich im Grunde zwei Bedingungen zu ueberpruefen.
>
> Okay also ein neuer Versuch.
> Die Ordnung eines Elementes x ist definiert als ord x= min
> [mm]\{n \in \IN | x^n=1 \}[/mm]
>
> wenn ich (ii) nutzen sollte, müsste ich also
> wahrscheinlich zeigen, dass
> [mm]\frac{5^{2^{r}}}{2^{r+2}*v}=1[/mm]
> aber da lässt sich dann ja auch wieder nichts umformen
> und ich weiß hier echt nicht weiter:-(
>
> und wenn ich wie oben umformen würde würde ich ja auch
> nicht auf eine Potenz von [mm]2^{r-2}[/mm] kommen
>
> Denn eigentlich will ich ja nachweisen, dass [mm]5^{2^{r-2}}=1[/mm]
> ist ich finde nur leider keinen Ansatzpunkt wo ich anfangen
> kann. Kannst du mir da vielleicht noch helfen?
>
> LG
> Schmetterfee
Gerne! Du hast es richtig erklaert; um nun zu zeigen, dass [mm] $o(r)_{\IZ_{2^{r}}}= 2^{r-2}$ [/mm] ist, muessen zwei Dinge ueberprueft werden:
1. [mm] $5^{2^{r-2}}= [/mm] 1$ mod [mm] $2^{r}$
[/mm]
2. [mm] $5^{m}\neq [/mm] 1$ mod [mm] $2^{r}$ [/mm] falls [mm] $m<2^{r-2}$ [/mm] gilt.
Ich behaupte, die erste Bedingung ergibt sich direkt aus der vorherigen Teilaufgabe. Fuer die zweite empfiehlt es sich haeufig so vorzugehen: Sei $m$ die Ordnung von $5$ in [mm] $\IZ_{2^{r}}$. [/mm] Nach 1. weisst Du, dass [mm] $5^{2^{r-2}}= [/mm] 1$ mod [mm] $2^{r}$ [/mm] gilt, sodass man daraus schlussfolgern kann, dass auch $m$ eine $2$-Potenz - etwa [mm] $2^{e}$ [/mm] -sein muss. Die Potenzen der Gestalt [mm] $5^{2^{e}}$ [/mm] haben wir aber gerade sehr genau studiert, woraus sich ergeben sollte, dass im Fall $e<r-2$ nicht [mm] $5^{2^{e}}= [/mm] 1$ mod [mm] $2^{r}$ [/mm] sein kann (das liegt naemlich daran, dass $v$ ungerade ist).
|
|
|
| |
|
Hallöchen,
es ist vielleicht ein zeichen dafür das ich mit der Thematik noch nicht ganz zur Rande komme aber ich schaffe es noch nicht mal zu zeigen, dass
[mm] 5^{r-2} \equiv [/mm] 1 mod [mm] 2^r
[/mm]
Also aus Teil (ii) sehe ich ja, dass
[mm] 5^{2^{r}} \equiv [/mm] 1 mod [mm] 2^{r+2}
[/mm]
aber ich sehe leider nicht wie ich die Kongruenzen so umformen kann, dass ich daraus das gewünschte erhalte. Was mache ich falsch? Gehe ich vom falschen aus oder rechne ich einfach nur falsch?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:12 Sa 14.01.2012 | | Autor: | hippias |
> Hallöchen,
>
> es ist vielleicht ein zeichen dafür das ich mit der
> Thematik noch nicht ganz zur Rande komme aber ich schaffe
> es noch nicht mal zu zeigen, dass
>
> [mm]5^{r-2} \equiv[/mm] 1 mod [mm]2^r[/mm]
>
> Also aus Teil (ii) sehe ich ja, dass
>
> [mm]5^{2^{r}} \equiv[/mm] 1 mod [mm]2^{r+2}[/mm]
Diese Beziehung haben wir ja fuer alle $r$ bewiesen. Ist nun [mm] $r'\geq [/mm] 2$ so gilt die Kongruenz ja auch speziell fuer $r:= r'-2$: [mm] $5^{2^{r}}= 5^{2^{r'-2}} \equiv [/mm] 1$ mod [mm] $2^{r+2}= 2^{r'-2+2}= 2^{r'}$, [/mm] kurz [mm] $5^{2^{r'-2}} \equiv [/mm] 1$ mod [mm] $2^{r'}$.
[/mm]
>
> aber ich sehe leider nicht wie ich die Kongruenzen so
> umformen kann, dass ich daraus das gewünschte erhalte. Was
> mache ich falsch? Gehe ich vom falschen aus oder rechne ich
> einfach nur falsch?
>
> Liebe Grüße
> Schmetterfee
Fragen ueber ueber Fragen... Aber im Ernst: Ich glaube nicht, dass Du etwas falsch machst, Du scheinst mir einfach noch nicht mit dem Thema vertraut genug: Um so besser, dass Du dieses Thema aufarbeitest! (Und fragst, wenn Dir etwas unklar ist) Vielleicht hilft es sich einen Beweis zu irgendeiner Behauptung so lange anzuschauen, bis Du das Gefuehl hast, Du haettest ihn verstanden. Dann versuche den Beweis selbst auswendig widerzugeben: Erst dann merke ich, dass ich den Beweis naemlich eigentlich nicht verstanden habe. Das machst Du solange, bis es klappt.
Ein Mathematiker, dessen Name mir entfallen ist, sagte einmal: Die Beweise sind dazu da, damit man sich die Saetze leichter merken kann.
|
|
|
| |
|
Hallöchen,
ich sitze immer noch am 2.ten Teil der Aufgabe und trotz deiner Hinweise erschließt sich mir die Argumentationsstruktur noch nicht ganz.
Also ich möchte nun ja noch zeigen: [mm] 5^m \not= [/mm] 1 mod [mm] 2^r [/mm] falls m< [mm] 2^{r-2}
[/mm]
Also sei m die Ordnung von 5 in [mm] (\IZ /{2^r \IZ}). [/mm] Wir wissen bereits, dass [mm] 5^{2^{r-2}} \equiv [/mm] 1 mod [mm] 2^r.
[/mm]
ich verstehe aber nicht wie ich hier folgern kann dass auch m eine 2-er Potenz sein muss. Kann m nicht auch 3 sein?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 11:04 So 15.01.2012 | | Autor: | hippias |
Ich habe mich mit meiner Behauptung ueber $m$ auf folgende bekannte Ueberlegung gestuetzt: Sei $G$ eine Gruppe und [mm] $m\in \IN$ [/mm] die Ordnung von [mm] $x\in [/mm] G$. Gilt fuer [mm] $k\in \IN$, [/mm] dass [mm] $x^{k}= [/mm] 1$ ist, dann gilt $m|k$: Denn schreibt man $k=qm+r$, wobei [mm] $0\leq [/mm] r<m$, dann folgt $1= [mm] x^{k}= (x^{m})^{q}x^{r}= 1x^{r}= x^{r}$. [/mm] Weil nun $m$ die kleinste natuerliche Zahl mit dieser Eigenschaft ist, folgt $r=0 $.
|
|
|
| |
|
Okay das habe ich nun auch verstanden.
nun müsste ich ja noch zeigen, dass für e<r-2 nicht [mm] 5^{2^{e}} \equiv [/mm] 1 mod [mm] 2^r [/mm] sein kann.
Du hattest ja gesagt, dass es aus der Tatsache folgt, dass v ungerade ist.
aber ich sehe leider nicht wie mich das weiter bringt. Kannst du mir noch einen Hinweis geben?
Liebe Grüße
Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 08:38 Mo 16.01.2012 | | Autor: | hippias |
> Okay das habe ich nun auch verstanden.
>
> nun müsste ich ja noch zeigen, dass für e<r-2 nicht
> [mm]5^{2^{e}} \equiv[/mm] 1 mod [mm]2^r[/mm] sein kann.
>
> Du hattest ja gesagt, dass es aus der Tatsache folgt, dass
> v ungerade ist.
> aber ich sehe leider nicht wie mich das weiter bringt.
> Kannst du mir noch einen Hinweis geben?
>
> Liebe Grüße
> Schmetterfee
Wir haben ja [mm] $5^{e}-1= 2^{e+2}v$, [/mm] wobei $v$ ungerade ist. Waere nun [mm] $5^{e}=1$ [/mm] mod [mm] $2^{r}$, [/mm] dann hiesse das ja [mm] $2^{r}|5^{e}-1= 2^{e+2}v$. [/mm] Da aber $e+2< r$ und $v$ eben nicht gerade ist, ist die hoechste $2$-Potenz, die [mm] $2^{e+2}v$ [/mm] teilt auch nur [mm] $2^{e+2}< 2^{r}$; [/mm] Widerspruch.
|
|
|
| |
|
Hallöchen,
dieser Aufgabenteil bezieht sich ja auch wieder auf die vorrige Aufgabe. Ich weiß nur leider nicht ganz wie ich argumentieren soll,
dass die Zahlen [mm] +5^{i} [/mm] für i=1,..., [mm] 2^{r-2} [/mm] inkongruent mod [mm] 2^r [/mm] sind folgt ja direkt aus dem vorrigen Aufgabenteil. Denn da haben wir ja gezeigt, dass [mm] 5^{2^{r-2}} \equiv [/mm] 1 [mm] \equiv 5^0 [/mm] mod [mm] 2^r.
[/mm]
aber mir ist nicht ganz klar wie ich die negativen Zahlen in die Argumentation mit einbinden kann. Hast du da eventuell auch noch einen Tipp für mich?
LG Schmetterfee
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 08:53 Mi 18.01.2012 | | Autor: | hippias |
Hallo Schmetterfee: Ich muss abbrechen, vielleicht stimmt es, was ich geschrieben habe, aber ganz sicher bin ich mir nicht. Vielleicht melde ich mich spaeter nocheinmal.
> Hallöchen,
>
> dieser Aufgabenteil bezieht sich ja auch wieder auf die
> vorrige Aufgabe. Ich weiß nur leider nicht ganz wie ich
> argumentieren soll,
>
> dass die Zahlen [mm]+5^{i}[/mm] für i=1,..., [mm]2^{r-2}[/mm] inkongruent
> mod [mm]2^r[/mm] sind folgt ja direkt aus dem vorrigen Aufgabenteil.
> Denn da haben wir ja gezeigt, dass [mm]5^{2^{r-2}} \equiv[/mm] 1
> [mm]\equiv 5^0[/mm] mod [mm]2^r.[/mm]
Streng genommen ist die Begruendung, dass [mm] $2^{r-2}$ [/mm] die kleinste Zahl mit [mm] $5^{m} \equiv[/mm] [/mm] 1$ mod [mm] $2^{r}$ [/mm] ist.
>
> aber mir ist nicht ganz klar wie ich die negativen Zahlen
> in die Argumentation mit einbinden kann. Hast du da
> eventuell auch noch einen Tipp für mich?
>
> LG Schmetterfee
Nehmen wir mal an es waere [mm] $5^{i}\equiv -5^{j}$ [/mm] mod [mm] $2^{r}$. [/mm] Dann ist [mm] $5^{i-j}\equiv [/mm] -1$ also [mm] $2^{r-2}\vert [/mm] 2(i-j)$.OBdA $i>j$. Nach Wahl von $i,j$ gilt [mm] $i-j<2^{r-2}$ [/mm] und damit [mm] $2^{r-2}= [/mm] 2(i-j)$, also $i= [mm] 2^{r-3}+j$ [/mm] und damit [mm] $5^{i}\equiv 2^{r-1}v5^{j}\equiv -5^{j}\iff 2^{r-1}v\equiv [/mm] -1$, $v$ ungerade. Anders gesagt [mm] $2^{r}| 2^{r-1}v+1$, [/mm] also $2|1$; Widerspruch.
|
|
|
| |
|
Hallöchen,
womit bist du dir denn ganu nicht sicher? Mit der Argumentation für die letzte Teilaufgabe oder womit direkt?
LG Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:01 Do 19.01.2012 | | Autor: | hippias |
Tut mir Leid wegen des Hin und Her:
Nehmen wir mal an es waere $ [mm] 5^{i}\equiv -5^{j} [/mm] $ mod $ [mm] 2^{r} [/mm] $. Dann ist $ [mm] 5^{i-j}\equiv [/mm] -1 $ also $ [mm] 2^{r-2}\vert [/mm] 2(i-j) $.OBdA $ i>j $. Nach Wahl von $ i,j $ gilt $ [mm] i-j<2^{r-2} [/mm] $ und damit $ [mm] 2^{r-2}= [/mm] 2(i-j) $, also $ i= [mm] 2^{r-3}+j [/mm] $ und damit $ [mm] 5^{i}\equiv (2^{r-1}v+1)5^{j} \text{Hier war ein Fehler!}\equiv -5^{j}\iff 2^{r-1}v+1\equiv [/mm] -1 $, $ v $ ungerade. Anders gesagt $ [mm] 2^{r}| 2^{r-1}v+2 [/mm] $, also $ 2|1 $ da [mm] $r\geq [/mm] 3$; Widerspruch.
Insgesamt richtig zufrieden bin ich damit noch immer nicht. Vielleicht findest Du ja eine bessere Loesung oder sogar einen Fehler!
> Hallöchen,
>
> womit bist du dir denn ganu nicht sicher? Mit der
> Argumentation für die letzte Teilaufgabe oder womit
> direkt?
>
> LG Schmetterfee
|
|
|
| |
|
Hallöchen,
ich muss gestehen ich bin mit der Aufgabe selber auf keinen grünen Zweig mehr gekommen. Verstehe nur leider deine Argumentation noch nicht so ganz
> Nehmen wir mal an es waere [mm]5^{i}\equiv -5^{j}[/mm] mod [mm]2^{r} [/mm].
> Dann ist [mm]5^{i-j}\equiv -1[/mm] also [mm]2^{r-2}\vert 2(i-j) [/mm].OBdA
> [mm]i>j [/mm]. Nach Wahl von [mm]i,j[/mm] gilt [mm]i-j<2^{r-2}[/mm] und damit [mm]2^{r-2}= 2(i-j) [/mm],
wie folgt das? Das muss doch gar nicht sein oder? Denn beispielsweise könnte doch i=2 sein und j=1 oder? Dann würde die Gleichheit ja nicht mehr gelten?
> also [mm]i= 2^{r-3}+j[/mm] und damit [mm]5^{i}\equiv (2^{r-1}v+1)5^{j} \text{Hier war ein Fehler!}\equiv -5^{j}\iff 2^{r-1}v+1\equiv -1 [/mm],
> [mm]v[/mm] ungerade. Anders gesagt [mm]2^{r}| 2^{r-1}v+2 [/mm], also [mm]2|1[/mm] da
> [mm]r\geq 3[/mm]; Widerspruch.
>
Weiter habe ich mir die Argumentation noch nicht angeguckt, weil ich Stückchenweise folgen wollte.
LG Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:47 Do 19.01.2012 | | Autor: | hippias |
> Hallöchen,
>
> ich muss gestehen ich bin mit der Aufgabe selber auf keinen
> grünen Zweig mehr gekommen. Verstehe nur leider deine
> Argumentation noch nicht so ganz
>
>
> > Nehmen wir mal an es waere [mm]5^{i}\equiv -5^{j}[/mm] mod [mm]2^{r} [/mm].
> > Dann ist [mm]5^{i-j}\equiv -1[/mm] also [mm]2^{r-2}\vert 2(i-j) [/mm].OBdA
> > [mm]i>j [/mm]. Nach Wahl von [mm]i,j[/mm] gilt [mm]i-j<2^{r-2}[/mm] und damit [mm]2^{r-2}= 2(i-j) [/mm],
> wie folgt das? Das muss doch gar nicht sein oder? Denn
> beispielsweise könnte doch i=2 sein und j=1 oder? Dann
> würde die Gleichheit ja nicht mehr gelten?
Natuerlich waere es denkbar, aber das haette Konsequenzen fuer das $r$. Jedenfalls:
1. [mm] $2^{r-2}\vert [/mm] 2(i-j)$
und
[mm] 2.$i-j<2^{r-2}$ [/mm] sind hoffentlich klar.
Aus 2. folgt durch Multiplikation mit $2$, dass [mm] $2(i-j)<2^{r-1}$ [/mm] ist. Nach 1. existiert [mm] $k\in \IN$ [/mm] mit $2(i-j)= [mm] 2^{r-2}k$. [/mm] Folglich ist [mm] $2^{r-2}k< 2^{k-1}$, [/mm] also vermittels Division mit [mm] $2^{r-2}$ [/mm] ergibt sich $k<2$.Wegen [mm] $k\geq [/mm] 1$ folgt $k= 1$ und damit die Behauptung.
> > also [mm]i= 2^{r-3}+j[/mm] und damit [mm]5^{i}\equiv (2^{r-1}v+1)5^{j} \text{Hier war ein Fehler!}\equiv -5^{j}\iff 2^{r-1}v+1\equiv -1 [/mm],
> > [mm]v[/mm] ungerade. Anders gesagt [mm]2^{r}| 2^{r-1}v+2 [/mm], also [mm]2|1[/mm] da
> > [mm]r\geq 3[/mm]; Widerspruch.
> >
> Weiter habe ich mir die Argumentation noch nicht angeguckt,
> weil ich Stückchenweise folgen wollte.
>
> LG Schmetterfee
|
|
|
| |
|
Hallöchen,
so jetzt habe ich die gesamte Argumenttion durch gearbeitet und 2 kleinere Fragen sind noch geblieben.
> Nehmen wir mal an es waere [mm]5^{i}\equiv -5^{j}[/mm] mod [mm]2^{r} [/mm].
> Dann ist [mm]5^{i-j}\equiv -1[/mm] also [mm]2^{r-2}\vert 2(i-j) [/mm].OBdA
Wieso folgt, dass [mm] 2^{r-2}\vert [/mm] 2(i-j) aus der Kongruenz? Ich habe hin und her gerechnet und probiert aber ich sehe das leider nicht.
> [mm]i>j [/mm]. Nach Wahl von [mm]i,j[/mm] gilt [mm]i-j<2^{r-2}[/mm] und damit [mm]2^{r-2}= 2(i-j) [/mm],
> also [mm]i= 2^{r-3}+j[/mm] und damit [mm]5^{i}\equiv (2^{r-1}v+1)5^{j} \text{Hier war ein Fehler!}\equiv -5^{j}\iff 2^{r-1}v+1\equiv -1 [/mm],
> [mm]v[/mm] ungerade. Anders gesagt [mm]2^{r}| 2^{r-1}v+2 [/mm], also [mm]2|1[/mm] da
> [mm]r\geq 3[/mm]; Widerspruch.
>
Wie folgt das genau das 2|1? Ich kann doch nur aus a|b und a| c folgern dass a|b+c
Danke für deine Geduld mit mir. Wenn sich die Fragen geklärt haben habe ich die Aufgabe soweit auch verstanen und werde sie versuchen aus meinem Gedächtnis noch einemal schön sauber aufzuschreiben.
LG Schmetterfee
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:52 Fr 20.01.2012 | | Autor: | hippias |
> Hallöchen,
>
> so jetzt habe ich die gesamte Argumenttion durch gearbeitet
> und 2 kleinere Fragen sind noch geblieben.
>
> > Nehmen wir mal an es waere [mm]5^{i}\equiv -5^{j}[/mm] mod [mm]2^{r} [/mm].
> > Dann ist [mm]5^{i-j}\equiv -1[/mm] also [mm]2^{r-2}\vert 2(i-j) [/mm].OBdA
> Wieso folgt, dass [mm]2^{r-2}\vert[/mm] 2(i-j) aus der Kongruenz?
> Ich habe hin und her gerechnet und probiert aber ich sehe
> das leider nicht.
Aus [mm] $5^{i-j}\equiv [/mm] -1$ folgt durch quadrieren [mm] $5^{2(i-j)}\equiv [/mm] 1$. Wie bereits erwaehnt folgt nun, dass die Ordnung von $5$ [mm] ($=2^{r-2}$) [/mm] die Zahl $2(i-j)$ teilt.
> > [mm]i>j [/mm]. Nach Wahl von [mm]i,j[/mm] gilt [mm]i-j<2^{r-2}[/mm] und damit
> [mm]2^{r-2}= 2(i-j) [/mm],
> > also [mm]i= 2^{r-3}+j[/mm] und damit [mm]5^{i}\equiv (2^{r-1}v+1)5^{j} \text{Hier war ein Fehler!}\equiv -5^{j}\iff 2^{r-1}v+1\equiv -1 [/mm],
> > [mm]v[/mm] ungerade. Anders gesagt [mm]2^{r}| 2^{r-1}v+2 [/mm], also [mm]2|1[/mm] da
> > [mm]r\geq 3[/mm]; Widerspruch.
> >
> Wie folgt das genau das 2|1? Ich kann doch nur aus a|b und
> a| c folgern dass a|b+c
Aus [mm] $2^{r}| 2^{r-1}v+2$ [/mm] folgt [mm] $2^{r}k= 2^{r-1}v+2$; [/mm] kuerzen mit $2$ liefert [mm] $2^{r-1}k= 2^{r-2}v+1$. [/mm] Links steht eine gerade Zahl, rechts eine ungerade wegen [mm] $r\geq [/mm] 3$.
>
> Danke für deine Geduld mit mir. Wenn sich die Fragen
> geklärt haben habe ich die Aufgabe soweit auch verstanen
> und werde sie versuchen aus meinem Gedächtnis noch einemal
> schön sauber aufzuschreiben.
>
> LG Schmetterfee
Geduld, Geduld, wenn mich falsche Zungen stechen... Aber im Ernst: Kein Problem.
|
|
|
| |
|
Okay, danke schön jetzt habe ich alles verstanden.
LG Schmetterfee
|
|
|
|
