quadratische Reste < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Zeigen Sie, dass die folgende Gleichung in [mm] $\IZ/p\IZ$ [/mm] für jede Primzahl $p$ lösbar ist:
[mm] $(x^2-13)(x^2-17)(x^2-221)=0$ [/mm] |
Hallo zusammen,
ich hoffe, dass ich mit dem Thema "quadratische Reste" überhaupt richtig liege. Ich habe nämlich noch nicht wirklich eine Idee, wie diese Aufgabe zu lösen ist...
Mein bisheriger Ansatz:
Ich suche ja eine Zahl $a [mm] \in \IZ$, [/mm] so dass es ein $x [mm] \in \IZ$ [/mm] gibt, mit [mm] $x^2 \equiv [/mm] 13 \ mod \ p$ UND [mm] $x^2 \equiv [/mm] 17 \ mod \ p$ UND [mm] $x^2 \equiv [/mm] 221 \ mod \ p$ ist.
Existiert ein solches $a$, so ist dies doch ein quadratischer Rest modulo p.
Um ein solches $a$ zu finden,haben wir in unserer Vorlesung mit Legendre-Symbolen [mm] $\left( \bruch{a}{p} \right)$ [/mm] gerechnet. Gilt [mm] $\left( \bruch{a}{p} \right) [/mm] = 1$, so ist $a$ ein quadratischer Rest.
Nun brauche ich ja EIN [mm] $a\in \IZ$! [/mm] Daher wollte ich zunächst mit dem Chinesischen Restsatz arbeiten, da ich mit dessen Hilfe ja ein [mm] $a\in \IZ$ [/mm] finden kann, welches alle drei Bedingungen erfüllen kann.
Hier komme ich aber nun langsam ins Straucheln... Wie sehen eigentlich meine drei Bedingungen aus?!? So?
$a [mm] \equiv [/mm] 13 \ mod \ p$
$a [mm] \equiv [/mm] 17 \ mod \ p$
$a [mm] \equiv [/mm] 221 \ mod \ p$
Ich hoffe sehr, dass mir jemand weiterhelfen kann... Bin ich bisher eigentlich schon irgendwo auf dem Holzweg???
LG fagottator
|
|
| |
|
moin,
> Zeigen Sie, dass die folgende Gleichung in [mm]\IZ/p\IZ[/mm] für
> jede Primzahl [mm]p[/mm] lösbar ist:
> [mm](x^2-13)(x^2-17)(x^2-221)=0[/mm]
> Hallo zusammen,
>
> ich hoffe, dass ich mit dem Thema "quadratische Reste"
> überhaupt richtig liege. Ich habe nämlich noch nicht
> wirklich eine Idee, wie diese Aufgabe zu lösen ist...
>
> Mein bisheriger Ansatz:
>
> Ich suche ja eine Zahl [mm]a \in \IZ[/mm], so dass es ein [mm]x \in \IZ[/mm]
> gibt, mit [mm]x^2 \equiv 13 \ mod \ p[/mm] UND [mm]x^2 \equiv 17 \ mod \ p[/mm]
> UND [mm]x^2 \equiv 221 \ mod \ p[/mm] ist.
Nein.
Du suchst ein $a$ mit [mm] $a^2 \equiv [/mm] 13 [mm] \mod [/mm] p$ ODER [mm] $\ldots$, [/mm] denn ein Produkt ist genau dann gleich 0, wenn einer der Faktoren gleich 0 ist.
> Existiert ein solches [mm]a[/mm], so ist dies doch ein
> quadratischer Rest modulo p.
Wieso?
Es soll ein $a$ geben mit [mm] $a^2 \equiv [/mm] 13$ (oder 17 oder 221), also muss $13,17$ oder $221$ ein quadratischer Rest sein.
> Um ein solches [mm]a[/mm] zu finden,haben wir in unserer Vorlesung
> mit Legendre-Symbolen [mm]\left( \bruch{a}{p} \right)[/mm]
> gerechnet. Gilt [mm]\left( \bruch{a}{p} \right) = 1[/mm], so ist [mm]a[/mm]
> ein quadratischer Rest.
Ja, Legendre ist schon eine sehr gute Idee.
Überlege dir mal folgende drei Fälle:
1. $p = 13$ oder $p=17$.
2. $13$ ist quadratischer Rest modulo $p$ oder $17$ ist quadratischer Rest modulo $p$ (da quadratische Reste nach Definition immer Einheiten sein müssen, musst du den ersten Fall zuerst ausschließen).
3. Weder $13$ noch $17$ sind quadratische Reste modulo $p$. Dann musst du folgern, dass $221$ ein quadratischer Rest ist (in diesem Fall steckt die eigentliche Arbeit).
Wenn du alle drei Fälle abgeklappert hast (und gezeigt bzw. begründet hast, dass du damit nichts vergisst) sollte das so passen.
lg
Schadow
|
|
|
| |
|
N'Abend,
> > Mein bisheriger Ansatz:
> >
> > Ich suche ja eine Zahl [mm]a \in \IZ[/mm], so dass es ein [mm]x \in \IZ[/mm]
> > gibt, mit [mm]x^2 \equiv 13 \ mod \ p[/mm] UND [mm]x^2 \equiv 17 \ mod \ p[/mm]
> > UND [mm]x^2 \equiv 221 \ mod \ p[/mm] ist.
>
> Nein.
> Du suchst ein [mm]a[/mm] mit [mm]a^2 \equiv 13 \mod p[/mm] ODER [mm]\ldots[/mm], denn
> ein Produkt ist genau dann gleich 0, wenn einer der
> Faktoren gleich 0 ist.
OH, das war ja mal selten dumm... Klar, "ODER" ist natürlich klar...
>
>
> > Existiert ein solches [mm]a[/mm], so ist dies doch ein
> > quadratischer Rest modulo p.
>
> Wieso?
> Es soll ein [mm]a[/mm] geben mit [mm]a^2 \equiv 13[/mm] (oder 17 oder 221),
> also muss [mm]13,17[/mm] oder [mm]221[/mm] ein quadratischer Rest sein.
Sicher, ich suche ja ein $a [mm] \in \IZ/p\IZ$ [/mm] mit [mm] $a^2 \equiv [/mm] 13$ (oder 17 oder 221), also ist [mm]13,17[/mm] oder [mm]221[/mm] ein quadratischer Rest.
>
>
> > Um ein solches [mm]a[/mm] zu finden,haben wir in unserer Vorlesung
> > mit Legendre-Symbolen [mm]\left( \bruch{a}{p} \right)[/mm]
> > gerechnet. Gilt [mm]\left( \bruch{a}{p} \right) = 1[/mm], so ist [mm]a[/mm]
> > ein quadratischer Rest.
>
> Ja, Legendre ist schon eine sehr gute Idee.
> Überlege dir mal folgende drei Fälle:
> 1. [mm]p = 13[/mm] oder [mm]p=17[/mm].
> 2. [mm]13[/mm] ist quadratischer Rest modulo [mm]p[/mm] oder [mm]17[/mm] ist
> quadratischer Rest modulo [mm]p[/mm] (da quadratische Reste nach
> Definition immer Einheiten sein müssen, musst du den
> ersten Fall zuerst ausschließen).
Ok, an sich erstmal klar. ABER
1) Ich hatte das jetzt so verstanden, dass $13$ oder $17$ oder $221$ auf jeden Fall ein quadratischer Rest sein muss, damit die Gleichung lösbar ist. Sehe ich das richtig?
2) Was soll ich denn dann in "1." tun/ für $a$ annehmen? Wenn ich "2." richtig verstehe, dann ist hier ja noch nicht anzunehmen, dass $13$ oder $17$ quadratischer Rest ist. Das kommt ja erst in "2.". Oder soll ich hier eine beliebige Primzahl p annehmen und in "1." mit $p = 13$ und $p = 17$ testen,ob $13$ oder $17$ quadratischer Rest ist?
> 3. Weder [mm]13[/mm] noch [mm]17[/mm] sind quadratische Reste modulo [mm]p[/mm]. Dann
> musst du folgern, dass [mm]221[/mm] ein quadratischer Rest ist (in
> diesem Fall steckt die eigentliche Arbeit).
Soweit habe ich jetzt ehrlich gesagt noch nicht gedacht, da ja schon weiter oben Probleme bestehen. Aber prinzipiell ist mir das Vorgehen klar...
>
>
> Wenn du alle drei Fälle abgeklappert hast (und gezeigt
> bzw. begründet hast, dass du damit nichts vergisst) sollte
> das so passen.
>
>
> lg
>
> Schadow
LG fagottator
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:37 Mi 04.07.2012 | | Autor: | felixf |
Moin!
> > > Existiert ein solches [mm]a[/mm], so ist dies doch ein
> > > quadratischer Rest modulo p.
> >
> > Wieso?
> > Es soll ein [mm]a[/mm] geben mit [mm]a^2 \equiv 13[/mm] (oder 17 oder
> 221),
> > also muss [mm]13,17[/mm] oder [mm]221[/mm] ein quadratischer Rest sein.
>
> Sicher, ich suche ja ein [mm]a \in \IZ/p\IZ[/mm] mit [mm]a^2 \equiv 13[/mm]
> (oder 17 oder 221), also ist [mm]13,17[/mm] oder [mm]221[/mm] ein
> quadratischer Rest.
Genau.
> > > Um ein solches [mm]a[/mm] zu finden,haben wir in unserer Vorlesung
> > > mit Legendre-Symbolen [mm]\left( \bruch{a}{p} \right)[/mm]
> > > gerechnet. Gilt [mm]\left( \bruch{a}{p} \right) = 1[/mm], so ist [mm]a[/mm]
> > > ein quadratischer Rest.
> >
> > Ja, Legendre ist schon eine sehr gute Idee.
> > Überlege dir mal folgende drei Fälle:
> > 1. [mm]p = 13[/mm] oder [mm]p=17[/mm].
> > 2. [mm]13[/mm] ist quadratischer Rest modulo [mm]p[/mm] oder [mm]17[/mm] ist
> > quadratischer Rest modulo [mm]p[/mm] (da quadratische Reste nach
> > Definition immer Einheiten sein müssen, musst du den
> > ersten Fall zuerst ausschließen).
>
> Ok, an sich erstmal klar. ABER
> 1) Ich hatte das jetzt so verstanden, dass [mm]13[/mm] oder [mm]17[/mm] oder
> [mm]221[/mm] auf jeden Fall ein quadratischer Rest sein muss, damit
> die Gleichung lösbar ist. Sehe ich das richtig?
Ja. Und eins davon reicht voellig aus.
Mach das ganze doch einfacher. Beachte, dass $221 = 13 * 17$ ist.
Kennst du das Legendre-Symbol (und weisst, dass es multiplikativ ist) oder das Eulerkriterium fuer quadratische Reste?
Koennen alle drei Legendre-Symbole $(13/p)$, $(17/p)$ und $(221/p)$ gleichzeitig -1 sein?
LG Felix
|
|
|
|
