"Zerlegung" von Potenzresten < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 23:04 Mo 27.09.2010 | | Autor: | para1991 |
| Aufgabe | Zeige: x ist ein quadratischer und kubischer Rest modulo m genau dann,
wenn x ein sechster Potenzrest modulo m ist.
Ist dies verallgemeinerbar? |
Wenn wir den sechsten Potenzrest gegeben haben, ist der Schluss trivial.
Ich habe meine Probleme, den sechsten Potenzrest aus dem quadr./kub. herzustellen.
Ich habe bereits versucht, etwas dazu zu googlen, finde aber neben reichlich abgehobenem Zeugs nur noch das quadr. Reziprozitätsgesetz, das mir hier nicht weiterhilft (oder doch?).
Ansonsten habe ich hier keine Idee, wie man hier rangehen könnte.
Um die evtl. Verallgemeinerung habe ich mir noch keine Gedanken gemacht, da ich nicht mal mit diesem Spezialfall klarkomme.
Über Hilfe wäre ich sehr dankbar (und bin natürlich bereit an der Lösung mitzuarbeiten,...ihr wisst schon...)
Grüße,
para1991
(Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.)
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:47 Mo 27.09.2010 | | Autor: | felixf |
Moin!
> Zeige: x ist ein quadratischer und kubischer Rest modulo m
> genau dann,
> wenn x ein sechster Potenzrest modulo m ist.
>
> Ist dies verallgemeinerbar?
> Wenn wir den sechsten Potenzrest gegeben haben, ist der
> Schluss trivial.
Ja. Dieser Schluss ist aber der Ausgangspunkt, mit dem du anfangen musst!
Wenn du ein $a$ hast mit [mm] $a^6 [/mm] = b$, dann gilt mit $c := [mm] a^2$ [/mm] und $d := [mm] a^3$, [/mm] dass [mm] $c^3 [/mm] = b = [mm] a^2$ [/mm] ist.
Jedoch kannst du jetzt auch $a = [mm] \frac{a^3}{a^2} [/mm] = [mm] \frac{d}{c}$ [/mm] schreiben.
Das ist die grundlegende Idee. Jetzt kann es natuerlich sein, dass $c$ nicht invertierbar ist.
Schreibe $m$ als Produkt von Primzahlpotenzen und benutze den chin. Restsatz. Es reicht das ganze also fuer $m = [mm] p^e$ [/mm] zu zeigen.
Modulo [mm] $p^e$ [/mm] hast du zwei Faelle: $c$ ist invertierbar (nicht durch $p$ teilbar) oder nicht (durch $p$ teilbar). Untersuche beide Faelle getrennt!
> Um die evtl. Verallgemeinerung habe ich mir noch keine
> Gedanken gemacht, da ich nicht mal mit diesem Spezialfall
> klarkomme.
Wichtig ist, dass 2 und 3 teilerfremd sind. Damit kannst du $1 = a [mm] \cdot [/mm] 2 + b [mm] \cdot [/mm] 3$ schreiben mit $a, b [mm] \in \IZ$; [/mm] hier: $a = -1$ und $b = 1$.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:04 Di 28.09.2010 | | Autor: | para1991 |
Tach,
> Moin!
>
> > Zeige: x ist ein quadratischer und kubischer Rest modulo m
> > genau dann,
> > wenn x ein sechster Potenzrest modulo m ist.
> >
> > Ist dies verallgemeinerbar?
> > Wenn wir den sechsten Potenzrest gegeben haben, ist der
> > Schluss trivial.
>
> Ja. Dieser Schluss ist aber der Ausgangspunkt, mit dem du
> anfangen musst!
>
> Wenn du ein [mm]a[/mm] hast mit [mm]a^6 = b[/mm], dann gilt mit [mm]c := a^2[/mm] und
> [mm]d := a^3[/mm], dass [mm]c^3 = b = a^2[/mm] ist.
>
Soweit ich die Frage verstanden habe, ist x ein quadratischer und kubischer Rest modulo m.
Das heißt doch nicht, dass dieselbe Zahl potenziert diese Reste ergibt, oder?
Falls ich da irgendwas falsch verstanden habe, klärt mich bitte auf.
Ansonsten versteh ich den Rest, vorausgesetzt du meintest [mm] d^2 [/mm] und nicht [mm] a^2 [/mm] in der Gleichung.
> Jedoch kannst du jetzt auch [mm]a = \frac{a^3}{a^2} = \frac{d}{c}[/mm]
> schreiben.
>
> Das ist die grundlegende Idee. Jetzt kann es natuerlich
> sein, dass [mm]c[/mm] nicht invertierbar ist.
>
>
> Schreibe [mm]m[/mm] als Produkt von Primzahlpotenzen und benutze den
> chin. Restsatz. Es reicht das ganze also fuer [mm]m = p^e[/mm] zu
> zeigen.
>
> Modulo [mm]p^e[/mm] hast du zwei Faelle: [mm]c[/mm] ist invertierbar (nicht
> durch [mm]p[/mm] teilbar) oder nicht (durch [mm]p[/mm] teilbar). Untersuche
> beide Faelle getrennt!
>
> > Um die evtl. Verallgemeinerung habe ich mir noch keine
> > Gedanken gemacht, da ich nicht mal mit diesem Spezialfall
> > klarkomme.
>
> Wichtig ist, dass 2 und 3 teilerfremd sind. Damit kannst du
> [mm]1 = a \cdot 2 + b \cdot 3[/mm] schreiben mit [mm]a, b \in \IZ[/mm]; hier:
> [mm]a = -1[/mm] und [mm]b = 1[/mm].
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 22:50 Di 28.09.2010 | | Autor: | felixf |
Moin!
> > > Zeige: x ist ein quadratischer und kubischer Rest modulo m
> > > genau dann,
> > > wenn x ein sechster Potenzrest modulo m ist.
> > >
> > > Ist dies verallgemeinerbar?
> > > Wenn wir den sechsten Potenzrest gegeben haben, ist
> der
> > > Schluss trivial.
> >
> > Ja. Dieser Schluss ist aber der Ausgangspunkt, mit dem du
> > anfangen musst!
> >
> > Wenn du ein [mm]a[/mm] hast mit [mm]a^6 = b[/mm], dann gilt mit [mm]c := a^2[/mm] und
> > [mm]d := a^3[/mm], dass [mm]c^3 = b = a^2[/mm] ist.
> >
>
> Soweit ich die Frage verstanden habe, ist x ein
> quadratischer und kubischer Rest modulo m.
> Das heißt doch nicht, dass dieselbe Zahl potenziert diese
> Reste ergibt, oder?
Nein. Eine dritte Wurzel ist normalerweise nicht gleich einer zweiten Wurzel.
> Falls ich da irgendwas falsch verstanden habe, klärt mich
> bitte auf.
Mach das ganze doch erstmal in [mm] $\IR$. [/mm] Wenn du [mm] $\sqrt[3]{124513}$ [/mm] und [mm] $\sqrt[2]{124513}$ [/mm] gegeben hast, wie kommst du auf [mm] $\sqrt[6]{124513}$?
[/mm]
> Ansonsten versteh ich den Rest, vorausgesetzt du meintest
> [mm]d^2[/mm] und nicht [mm]a^2[/mm] in der Gleichung.
Ja, ich meinte [mm] $d^2$.
[/mm]
> > Jedoch kannst du jetzt auch [mm]a = \frac{a^3}{a^2} = \frac{d}{c}[/mm]
> > schreiben.
> >
> > Das ist die grundlegende Idee. Jetzt kann es natuerlich
> > sein, dass [mm]c[/mm] nicht invertierbar ist.
> >
> >
> > Schreibe [mm]m[/mm] als Produkt von Primzahlpotenzen und benutze den
> > chin. Restsatz. Es reicht das ganze also fuer [mm]m = p^e[/mm] zu
> > zeigen.
> >
> > Modulo [mm]p^e[/mm] hast du zwei Faelle: [mm]c[/mm] ist invertierbar (nicht
> > durch [mm]p[/mm] teilbar) oder nicht (durch [mm]p[/mm] teilbar). Untersuche
> > beide Faelle getrennt!
> >
> > > Um die evtl. Verallgemeinerung habe ich mir noch keine
> > > Gedanken gemacht, da ich nicht mal mit diesem Spezialfall
> > > klarkomme.
> >
> > Wichtig ist, dass 2 und 3 teilerfremd sind. Damit kannst du
> > [mm]1 = a \cdot 2 + b \cdot 3[/mm] schreiben mit [mm]a, b \in \IZ[/mm]; hier:
> > [mm]a = -1[/mm] und [mm]b = 1[/mm].
> >
> > LG Felix
> >
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 17:43 Sa 02.10.2010 | | Autor: | para1991 |
Danke für deine Antwort,
Ich versuchs mal in |R: [mm] \bruch{\wurzel[2]{3}}{\wurzel[3]{3}} [/mm] = [mm] \wurzel[6]{3}.
[/mm]
Also versuche ich [mm] \bruch{d}{c} [/mm] auszurechnen.
Es stellt sich die Frage, ob [mm] \bruch{1}{c} [/mm] überhaupt existiert.
Du möchtest nun mit dem chin. Restsatz c auseinanderziehen.
Aber ich dachte immer der chin. Restsatz sagt etwas über die Lösung von simultanen Kongruenzen, nicht über die Invertierbarkeit, aus?
Oder ist dies irgendeine verallgemeinerte Form des chin. Restsatzes?
|
|
|
| |
|
Hallo,
> Danke für deine Antwort,
>
> Ich versuchs mal in [mm] \IR: [/mm]
> [mm]\bruch{\wurzel[2]{3}}{\wurzel[3]{3}}=\wurzel[6]{3}.[/mm]
Sehr hübsch. Wenn nach Lösung des ersten Teils die Frage nach der Verallgemeinerbarkeit kommt, solltest Du aber über diese Darstellung noch einmal gründlich nachdenken.
Ansonsten geht natürlich auch (bleiben wir zur Demonstration in [mm] \IR [/mm] ) [mm] \wurzel[6]{3}=\wurzel[2]{\wurzel[3]{2}}=\wurzel[3]{\wurzel[2]{2}}
[/mm]
> Also versuche ich [mm]\bruch{d}{c}[/mm] auszurechnen.
>
> Es stellt sich die Frage, ob [mm]\bruch{1}{c}[/mm] überhaupt
> existiert.
Die Frage stellt sich auch bei meinem Vorschlag. In beiden Fällen kannst Du aber beweisen, dass die sechste Wurzel existiert. Tipp: Fundamentalsatz.
> Du möchtest nun mit dem chin. Restsatz c
> auseinanderziehen.
> Aber ich dachte immer der chin. Restsatz sagt etwas über
> die Lösung von simultanen Kongruenzen, nicht über die
> Invertierbarkeit, aus?
> Oder ist dies irgendeine verallgemeinerte Form des chin.
> Restsatzes?
Wenn Du die Kongruenz hinsichtlich eines zusammengesetzten Moduls hast, weißt Du doch auch etwas über ein bedeutungsgleiches System simultaner Kongruenzen (bzw. sogar ggf. mehrere mögliche). Das ist hier gemeint. Du kannst leicht zeigen, dass es ebenso eindeutig ist wie die Gegenrichtung, die der chin. Restsatz meint.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 18:40 Mo 04.10.2010 | | Autor: | para1991 |
Hallo
und Danke für die Mühe. Ich habe den oberen Post nun nachvollziehen können, nur an der Stelle, wo du etwas vom chin. Restesatz erzählst benutze ich die Aussage, dass eine Zahl genau dann modulo m invertierbar ist, wenn sie teilerfremd sind, was ja auf dasselbe hinausläuft.
Wenn Teilerfremdheit vorliegt, sind wir fertig.
Ich gehe also nun von ggT(c,m)>1 aus. Aus dem, was ich beweisen muss, weiß ich, dass dieses gleich ggT(d,m) sein müsste.
Wenn dies gilt, könnte ich in [mm] \bruch{d}{c} [/mm] kürzen und hätte nun teilerfremde zu m. Wir hätten dies also auf den vorherigen Fall zurückgeführt.
Ich glaube, dass dies sich durch die Eigenschaft, dass sie ja gemeinsame Potenzen haben ableiten lässt, ich habe allerdings noch nicht gesehen, ob dies tatsächlich funktioniert.
Oder ist mein Ansatz, den ich eben erläutert habe, falsch?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:43 Mo 04.10.2010 | | Autor: | felixf |
Moin!
> und Danke für die Mühe. Ich habe den oberen Post nun
> nachvollziehen können, nur an der Stelle, wo du etwas vom
> chin. Restesatz erzählst benutze ich die Aussage, dass
> eine Zahl genau dann modulo m invertierbar ist, wenn sie
> teilerfremd sind, was ja auf dasselbe hinausläuft.
>
> Wenn Teilerfremdheit vorliegt, sind wir fertig.
Sozusagen.
> Ich gehe also nun von ggT(c,m)>1 aus. Aus dem, was ich
> beweisen muss, weiß ich, dass dieses gleich ggT(d,m) sein
> müsste.
Woher weisst du das? Ich bezweifle das mal ganz stark!
> Wenn dies gilt, könnte ich in [mm]\bruch{d}{c}[/mm] kürzen und
> hätte nun teilerfremde zu m. Wir hätten dies also auf den
> vorherigen Fall zurückgeführt.
Vorsicht! Du rechnest hier in [mm] $\IQ$, [/mm] du sollst aber in [mm] $\IZ/m\IZ$ [/mm] rechnen! Dort ist [mm] $\frac{d}{c}$ [/mm] eine Abkuerzung fuer $d [mm] \cdot c^{-1}$ [/mm] -- was nur geht, wenn $c$ invertierbar ist.
> Ich glaube, dass dies sich durch die Eigenschaft, dass sie
> ja gemeinsame Potenzen haben ableiten lässt, ich habe
> allerdings noch nicht gesehen, ob dies tatsächlich
> funktioniert.
>
> Oder ist mein Ansatz, den ich eben erläutert habe, falsch?
Am besten benutzt du erstmal den chinesischen Restsatz, um alles auf den Fall $m = [mm] p^e$ [/mm] zu reduzieren mit $p$ prim. Beachte, dass du jedes Element in [mm] $\IZ/p^e\IZ$ [/mm] darstellen kannst als [mm] $p^i \cdot [/mm] e$, wobei $e [mm] \in (\IZ/p^{e-i}\IZ)^\ast$ [/mm] ist und $0 [mm] \le [/mm] i [mm] \le [/mm] e$.
Wenn $i = 0$ ist, dann ist [mm] $p^i \cdot [/mm] e$ eine Einheit in [mm] $\IZ/p^e\IZ$ [/mm] und du kannst wie oben vorgehen.
Wenn $i > 0$ ist, musst du etwas geschickter vorgehen! Beachte, dass [mm] $c^3 [/mm] = a = [mm] d^2$ [/mm] ist und ueberleg dir, was das genau bedeutet bzgl. dieser Darstellung.
LG Felix
|
|
|
|
