Lösungen? < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:59 So 18.09.2011 | | Autor: | wauwau |
| Aufgabe | für jede ungerade Primzahl $p$ und Rest $r, 0 [mm] \le [/mm] r < p$ hat die Gleichung
[mm] $x^2+y^2 \equiv [/mm] r(p)$ eine Lösung in x und y |
Ich glaube zwar, dass dass stimmt, denn
[mm] $x^2$ [/mm] nimmt immer [mm] $\frac{p+1}{2}$ [/mm] verschiedene Reste an, aber so einen richtig stichhaltigen Beweis habe ich nicht, da liegen meine Kenntnisse über quadratische Reste schon zu weit zurück!
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 18:31 So 18.09.2011 | | Autor: | hippias |
Mein Tip lautet: Fuer die multiplikative Gruppe $G:= [mm] \IZ_{p}\backslash\{0\}$ [/mm] ist [mm] $G^{2}$ [/mm] eine Untergruppe vom Index $2$ und sicherlich nicht additiv abgeschlossen.
Fuer $p=2$ gilt die Behauptung uebrigens auch.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:46 So 18.09.2011 | | Autor: | felixf |
Moin!
> für jede ungerade Primzahl [mm]p[/mm] und Rest [mm]r, 0 \le r < p[/mm] hat
> die Gleichung
>
> [mm]x^2+y^2 \equiv r(p)[/mm] eine Lösung in x und y
> Ich glaube zwar, dass dass stimmt, denn
> [mm]x^2[/mm] nimmt immer [mm]\frac{p+1}{2}[/mm] verschiedene Reste an, aber
> so einen richtig stichhaltigen Beweis habe ich nicht, da
> liegen meine Kenntnisse über quadratische Reste schon zu
> weit zurück!
Hast du (oder irgendwer anderes) das mal fuer alle Primzahlen $p [mm] \le [/mm] 100$ vom Computer durchprobieren lassen?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:45 So 18.09.2011 | | Autor: | wauwau |
Mach ich morgen im Laufe des Tages...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:18 So 18.09.2011 | | Autor: | felixf |
Moin,
ich hab gerade selber ein kleines Programm dafuer geschrieben. Die Aussage stimmt zumindest fuer alle $p [mm] \le [/mm] 10000$.
Bei einer kurzen google-Suche bin ich auf folgendes Dokument gestossen: http://www.math.ttu.edu/~cmonico/research/qnr-charv5.pdf Das behandelt glaube ich (hab nur sehr kurz reingeschaut) nicht deine Frage, koennte aber Ideen liefern wie man deine Aussage beweisen kann.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:21 So 18.09.2011 | | Autor: | felixf |
![[]](/images/popup.gif) Diese Diskussion enthaelt vermutlich auch etwas brauchbares.
LG Felix
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:45 Mo 19.09.2011 | | Autor: | hippias |
Meine Variante geht so:
Sei $p>2$ Primzahl und $K:= [mm] \IZ$. $K^{2}$ [/mm] enthaelt offensichtlich [mm] $\bruch{p+1}{2}$ [/mm] Elemente. [mm] $K^{2}$ [/mm] ist nicht additiv abgeschlossen, denn dann waere es sogar eine Untergruppe der additiven Gruppe des Koerpers, welche von Primzahlordung ist, was ein Widerspruch zu [mm] $\abs{K^{2}}= \bruch{p+1}{2}$ [/mm] waere.
Also existieren [mm] $x,y\in [/mm] K$ so, dass [mm] $x^{2}+y^{2}$ [/mm] kein Quadrat in $K$ ist. Nun hat [mm] $G^{2}$ [/mm] den Index $2$ in $G:= [mm] K\backslash\{0\}$, [/mm] sodass $G= [mm] G^{2}\cup G^{2}(x^{2}+y^{2})$ [/mm] folgt, bzw. $K= [mm] K^{2}\cup K^{2}(x^{2}+y^{2})$. [/mm] Wegen [mm] $K^{2}(x^{2}+y^{2})\subseteq K^{2}+ K^{2}$ [/mm] folgt jetzt die Behauptung.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 10:18 Mo 19.09.2011 | | Autor: | wauwau |
Leider verstehe ich diesen Schritt nicht...
> Nun hat [mm]G^{2}[/mm] den Index [mm]2[/mm] in [mm]G:= K\backslash\{0\}[/mm],
> sodass [mm]G= G^{2}\cup G^{2}(x^{2}+y^{2})[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:28 Mo 19.09.2011 | | Autor: | hippias |
> Leider verstehe ich diesen Schritt nicht...
>
> > Nun hat [mm]G^{2}[/mm] den Index [mm]2[/mm] in [mm]G:= K\backslash\{0\}[/mm],
> > sodass [mm]G= G^{2}\cup G^{2}(x^{2}+y^{2})[/mm]
Wenn [mm] $G^{2}$ [/mm] den Index $2$ hat, sie also genau $2$ Nebenklassen in $G$ hat, und [mm] $x^{2}+y^{2}$ [/mm] ein Nichtquadrat ist - und beachte, dass nach Konstruktion [mm] $x^{2}+y^{2}\neq [/mm] 0$ ist- also [mm] $x^{2}+y^{2}\not \in G^{2}$, [/mm] dann muss [mm] $(x^{2}+y^{2})G^{2}$ [/mm] die "andere" Nebenklasse neben [mm] $G^{2}$ [/mm] sein. Die Vereinigung der Nebenklassen ergibt dann die gesamte Gruppe.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:00 Mo 19.09.2011 | | Autor: | wauwau |
Natürlich - mich hat nur die Schreibweise etwas verwirrt...
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:29 Mo 19.09.2011 | | Autor: | felixf |
Moin,
> Leider verstehe ich diesen Schritt nicht...
>
> > Nun hat [mm]G^{2}[/mm] den Index [mm]2[/mm] in [mm]G:= K\backslash\{0\}[/mm],
> > sodass [mm]G= G^{2}\cup G^{2}(x^{2}+y^{2})[/mm]
$G$ ist (disjunkte) Vereinigung der Nebenklassen von [mm] $G^2$ [/mm] in $G$. Da der Index von [mm] $G^2$ [/mm] in $G$ zwei ist, gibt es genau zwei solche Nebenklassen. Die eine ist $1 [mm] \cdot G^2 [/mm] = [mm] G^2$, [/mm] und jedes Element $z [mm] \in [/mm] G [mm] \setminus G^2$ [/mm] erzeugt eine andere Nebenklasse $z [mm] G^2$, [/mm] womit $G = [mm] G^2 \cup [/mm] z [mm] G^2$ [/mm] sein muss.
Da [mm] $x^2 [/mm] + [mm] y^2 \not\in G^2$ [/mm] gilt (nach Annahme), kann man $z = [mm] x^2 [/mm] + [mm] y^2$ [/mm] waehlen und es folgt somit $G = [mm] G^2 \cup (x^2 [/mm] + [mm] y^2) G^2$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:27 Mo 19.09.2011 | | Autor: | felixf |
Moin!
> Meine Variante geht so:
> Sei [mm]p>2[/mm] Primzahl und [mm]K:= \IZ[/mm]. [mm]K^{2}[/mm] enthaelt
> offensichtlich [mm]\bruch{p+1}{2}[/mm] Elemente. [mm]K^{2}[/mm] ist nicht
> additiv abgeschlossen, denn dann waere es sogar eine
> Untergruppe der additiven Gruppe des Koerpers, welche von
> Primzahlordung ist, was ein Widerspruch zu [mm]\abs{K^{2}}= \bruch{p+1}{2}[/mm]
> waere.
> Also existieren [mm]x,y\in K[/mm] so, dass [mm]x^{2}+y^{2}[/mm] kein Quadrat
> in [mm]K[/mm] ist. Nun hat [mm]G^{2}[/mm] den Index [mm]2[/mm] in [mm]G:= K\backslash\{0\}[/mm],
> sodass [mm]G= G^{2}\cup G^{2}(x^{2}+y^{2})[/mm] folgt, bzw. [mm]K= K^{2}\cup K^{2}(x^{2}+y^{2})[/mm].
> Wegen [mm]K^{2}(x^{2}+y^{2})\subseteq K^{2}+ K^{2}[/mm] folgt jetzt
> die Behauptung.
Sieht gut aus.
LG Felix
|
|
|
| |
|
Hallo wauwau,
es geht auch ganz ohne Primzahlen und quadratische Reste.
Sei m=2n+1 ein ungerader Modul, [mm] R=\{r_1,...,r_{n+1}\} [/mm] eine beliebige Auswahl verschiedener Restklassen.
Dann ist jede Restklasse [mm] a\mod{m} [/mm] als Summe [mm] a\equiv r_i+r_j\mod{m} [/mm] mit [mm] r_i, r_j\in{R} [/mm] darstellbar.
Das ist leicht zu zeigen:
Für jedes a gibt es n+1 verschiedene additive Zerlegungen, wovon nur eine die Form [mm] a=b+b\mod{m} [/mm] hat. Ist [mm] b\in{R}, [/mm] ist damit eine gültige Zerlegung gefunden.
Ist [mm] b\not\in{R}, [/mm] sind die anderen n additiven Zerlegungen zu betrachten. In ihnen kommt jede Restklasse nur einmal als Summand vor. Wenigstens eine der Zerlegungen muss daher die Form [mm] r_i+r_j [/mm] haben, da R n+1 Elemente hat.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:11 Mo 19.09.2011 | | Autor: | wauwau |
Warum gilt deine 1. Aussage??
|
|
|
| |
|
Hallo,
> Warum gilt deine 1. Aussage??
Welche? n+1 additive Zerlegungen? Das folgt leicht, wenn Du die Kommutativität der Addition berücksichtigst.
Nimm [mm] a\equiv c+(a-c)\mod{m} [/mm] und lass c alle m möglichen Werte annehmen. Dann hast Du 2n+1 Äquivalenzen, von denen eine nur einmal vorkommt, alle anderen zweimal, aber eben wegen der Kommutativität nur einfach zu zählen sind, also insgesamt n+1 Zerlegungen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:49 Mo 19.09.2011 | | Autor: | wauwau |
Nein deine erste Aussage betr. der Darstellung der Reste als summe zweier Elemente der von dir angegebenen beliebigen n+1-mächtigen Restklassenteilmenge...
|
|
|
| |
|
Hallo wauwau,
ich verstehe die Frage nicht.
> Nein deine erste Aussage betr. der Darstellung der Reste
> als summe zweier Elemente der von dir angegebenen
> beliebigen n+1-mächtigen Restklassenteilmenge...
Das zeige ich doch danach erst. ![[haee]](/images/smileys/haee.gif "[haee]")
Zitier doch mal den ganzen Post, wenn noch Rückfragen sind.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 11:59 Mo 19.09.2011 | | Autor: | felixf |
Moin reverend,
mit deiner Aussage folgt es fuer alle Moduln der Form $2 m + 1$ und $2 (2 m + 1)$, $m [mm] \in \IN$, [/mm] wenn man den chinesischen Restsatz verwendet. Da die Aussage modulo 4 falsch ist, folgt damit:
Die Aussage gilt genau dann fuer einen Modul $m$, wenn $m$ hoechstens einmal durch 2 teilbar ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 12:30 Mo 19.09.2011 | | Autor: | wauwau |
d.h. also:
[mm] $x^2+y^2 \equiv [/mm] r(M)$ ist immer lösbar wenn [mm] $\{\frac{M}{4}\}\not=0$
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 14:02 Mo 19.09.2011 | | Autor: | felixf |
Moin,
> d.h. also:
>
> [mm]x^2+y^2 \equiv r(M)[/mm] ist immer lösbar wenn
> [mm]\{\frac{M}{4}\}\not=0[/mm]
nein, leider doch nicht. Momentaner Stand der Vermutung: es geht genau dann, wenn der Modul $M$ quadratfrei ist. Falls $M$ quadratfrei ist geht es auf jeden Fall, und falls $M$ die Primzahlen 2 oder 3 mehrfach enthaelt, geht es nicht, mehr wissen wir noch nicht.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 16:33 Mo 19.09.2011 | | Autor: | reverend |
Nur so zwischendurch:
für 25 stimmt die Behauptung, für 49 nicht.
Ich sehe gerade keinen Grund dafür.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:14 Mo 19.09.2011 | | Autor: | felixf |
Moin,
ehrlich gesagt verwirrt mich das ganze gerade. Man kann naemlich zeigen: ist $p$ eine ungerade Primzahl und gilt [mm] $x^2 [/mm] + [mm] y^2 \equiv [/mm] r [mm] \pmod{p}$, [/mm] so gibt es zu jedem $n [mm] \in \N$ [/mm] $x', y' [mm] \in \IZ$ [/mm] mit [mm] $(x')^2 [/mm] + [mm] (y')^2 \equiv [/mm] r [mm] \pmod{p^n}$. [/mm] Das folgt recht einfach mit dem Henselschen Lemma.
Insofern sollte es fuer $9 = [mm] 3^2$, [/mm] $25 = [mm] 5^2$ [/mm] und $49 = [mm] 7^2$ [/mm] jeweils stimmen.
(Womit man wieder die urspruengliche Behauptung von mir erhalten wuerde: es stimmt fuer einen Modulus $M$ genau dann, wenn $M$ hoechstens einmal durch 2 teilbar ist.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:22 Mo 19.09.2011 | | Autor: | felixf |
Moin,
> ehrlich gesagt verwirrt mich das ganze gerade. Man kann
> naemlich zeigen: ist [mm]p[/mm] eine ungerade Primzahl und gilt [mm]x^2 + y^2 \equiv r \pmod{p}[/mm],
> so gibt es zu jedem [mm]n \in \N[/mm] [mm]x', y' \in \IZ[/mm] mit [mm](x')^2 + (y')^2 \equiv r \pmod{p^n}[/mm].
> Das folgt recht einfach mit dem Henselschen Lemma.
das stimmt so leider nicht ganz. Das Argument funktioniert naemlich nur, wenn die Loesung (sagen wir fuer $x$), die man liften will, nicht durch $p$ teilbar ist. Das geht z.B. bei $p = 3$, $n = 2$ und $r = 3$ schief: man nimmt $x = y = 0$, und es gilt [mm] $x^2 [/mm] + [mm] y^2 \equiv [/mm] r [mm] \pmod{p}$, [/mm] jedoch kann man das Henselsche Lemma nicht auf $f(X) := [mm] X^2 [/mm] + [mm] y^2 [/mm] - r$ bei $X = x$ anwenden, da $f'(x) [mm] \equiv [/mm] 0 [mm] \pmod{p}$ [/mm] gilt.
Hier ist es sogar so, dass man $x$ und $y$ immer so waehlen muss: ist eins von beiden nicht durch 3 teilbar, so ist das Quadrat davon kongruent zu 1 modulo 3, womit die Summe der Quadrate nicht 0 modulo 3 sein kann. Es muss also $x, y [mm] \equiv [/mm] 0 [mm] \pmod{3}$ [/mm] sein, und man kann mit Hensel keine Loesung modulo $9 = [mm] 3^2$ [/mm] erhalten.
LG Felix
PS: Nachtrag: die Moduli [mm] $\le [/mm] 200$, die nicht durch 4 teilbar sind, und fuer die die Gleichung nicht immer loesbar sind, sind 9, 18, 27, 45, 49, 54, 63, 81, 90, 98, 99, 117, 121, 126, 135, 147, 153, 162, 171, 189). Laesst man einfach vorkommende Primfaktoren weg, so reduziert sich die Liste auf die Moduli $9 = [mm] 3^2$, [/mm] $27 = [mm] 3^3$, [/mm] $49 = [mm] 7^2$, [/mm] $81 = [mm] 3^4$, [/mm] $121 = [mm] 11^2$. [/mm] Der Modulus [mm] $17^2$ [/mm] geht uebrigens wieder, waehrend [mm] $19^2$ [/mm] und [mm] $23^2$ [/mm] nicht gehen. [mm] $29^2$ [/mm] geht wieder, [mm] $31^2$ [/mm] wieder nicht.
PPS: Die Primzahlen $p [mm] \le [/mm] 263$, fuer die der Modulus [mm] $p^2$ [/mm] nicht immer Loesungen zulaesst, sind gerade 2, 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131, 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251, 263. Alle Primzahlen $p [mm] \le [/mm] 263$, fuer die es modulo [mm] $p^2$ [/mm] immer eine Loesung gibt, sind 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, 97, 101, 109, 113, 137, 149, 157, 173, 181, 193, 197, 233, 229, 241, 257. Wenn man sich diese Primzahllisten modulo 4 anschaut, sieht man: die Primzahlen, bei denen es nicht immer geht, sind alle kongruent zu 3 modulo 4 (und $p = 2$ ist eine Ausnahme), und die anderen erfuellen $p [mm] \equiv [/mm] 1 [mm] \pmod{4}$.
[/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:57 Mo 19.09.2011 | | Autor: | felixf |
Moin,
> PPS: Die Primzahlen [mm]p \le 263[/mm], fuer die der Modulus [mm]p^2[/mm]
> nicht immer Loesungen zulaesst, sind gerade 2, 3, 7, 11,
> 19, 23, 31, 43, 47, 59, 67, 71, 79, 83, 103, 107, 127, 131,
> 139, 151, 163, 167, 179, 191, 199, 211, 223, 227, 239, 251,
> 263. Alle Primzahlen [mm]p \le 263[/mm], fuer die es modulo [mm]p^2[/mm]
> immer eine Loesung gibt, sind 5, 13, 17, 29, 37, 41, 53,
> 61, 73, 89, 97, 101, 109, 113, 137, 149, 157, 173, 181,
> 193, 197, 233, 229, 241, 257. Wenn man sich diese
> Primzahllisten modulo 4 anschaut, sieht man: die
> Primzahlen, bei denen es nicht immer geht, sind alle
> kongruent zu 3 modulo 4 (und [mm]p = 2[/mm] ist eine Ausnahme), und
> die anderen erfuellen [mm]p \equiv 1 \pmod{4}[/mm].
nach numerischen Experimenten mit den Moduli [mm] $p^e \le [/mm] 10000$ fuer alle moeglichen Kombinationen von $p$ und $e$ stelle ich folgende Behauptung auf:
Die Gleichung [mm] $x^2 [/mm] + [mm] y^2 \equiv [/mm] z [mm] \pmod{N}$ [/mm] ist genau dann fuer alle $z [mm] \in \IZ$ [/mm] loesbar, wenn fuer jede Primzahl $p$ mit [mm] $p^2 \mid [/mm] N$ gilt $p [mm] \equiv [/mm] 1 [mm] \pmod{4}$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:59 Mo 19.09.2011 | | Autor: | wauwau |
Erinnert mich sehr an den Fermat-Euler Zwei-Quadrate Satz:
Jede Primzahl der Form 4k+1 ist eindeutig die Summe von zwei Quadraten!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:15 Mo 19.09.2011 | | Autor: | reverend |
Hallo Felix,
ein langer Sitzungsabend (der erste von fünf :-( in dieser Woche) liegt hinter mir. Daher erst einmal nur eine kurze Reaktion:
> nach numerischen Experimenten mit den Moduli [mm]p^e \le 10000[/mm]
> fuer alle moeglichen Kombinationen von [mm]p[/mm] und [mm]e[/mm] stelle ich
> folgende Behauptung auf:
>
> Die Gleichung [mm]x^2 + y^2 \equiv z \pmod{N}[/mm] ist genau dann
> fuer alle [mm]z \in \IZ[/mm] loesbar, wenn fuer jede Primzahl [mm]p[/mm] mit
> [mm]p^2 \mid N[/mm] gilt [mm]p \equiv 1 \pmod{4}[/mm].
Hm. Noch nicht ganz. Mir scheint, dass die Gleichung nie für alle [mm] z\in\IZ [/mm] lösbar ist, wenn es ein [mm] p\in\IP [/mm] mit [mm] p^3|N [/mm] gibt, so z.B. für N=125. Die Reste 25,50,75,100 sind nicht darstellbar.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 05:54 Di 20.09.2011 | | Autor: | felixf |
Moin rev,
> > nach numerischen Experimenten mit den Moduli [mm]p^e \le 10000[/mm]
> > fuer alle moeglichen Kombinationen von [mm]p[/mm] und [mm]e[/mm] stelle ich
> > folgende Behauptung auf:
> >
> > Die Gleichung [mm]x^2 + y^2 \equiv z \pmod{N}[/mm] ist genau dann
> > fuer alle [mm]z \in \IZ[/mm] loesbar, wenn fuer jede Primzahl [mm]p[/mm] mit
> > [mm]p^2 \mid N[/mm] gilt [mm]p \equiv 1 \pmod{4}[/mm].
>
> Hm. Noch nicht ganz. Mir scheint, dass die Gleichung nie
> für alle [mm]z\in\IZ[/mm] lösbar ist, wenn es ein [mm]p\in\IP[/mm] mit
> [mm]p^3|N[/mm] gibt, so z.B. für N=125.
dochdoch, das geht. Fuer $N = 125$ hast du:
> Die Reste 25,50,75,100 sind nicht darstellbar.
$25 = [mm] 5^2 [/mm] + [mm] 0^2$, [/mm] $50 = [mm] 5^2 [/mm] + [mm] 5^2$, [/mm] $75 = [mm] 1^2 [/mm] + [mm] 18^2 [/mm] - 2 [mm] \cdot [/mm] 125 [mm] \equiv 1^2 [/mm] + [mm] 18^2$, [/mm] $100 = [mm] 10^2 [/mm] + [mm] 0^2$.
[/mm]
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:32 Di 20.09.2011 | | Autor: | reverend |
> [mm]25 = 5^2 + 0^2[/mm], [mm]50 = 5^2 + 5^2[/mm], [mm]75 = 1^2 + 18^2 - 2 \cdot 125 \equiv 1^2 + 18^2[/mm],
> [mm]100 = 10^2 + 0^2[/mm].
Hmpf. Klar. Ich hatte einen netten Programmierfehler, gerade weil ich die Vielfachen von [mm] p^2 [/mm] prüfen wollte.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 10:25 Di 20.09.2011 | | Autor: | hippias |
> stelle ich
> folgende Behauptung auf:
>
> Die Gleichung [mm]x^2 + y^2 \equiv z \pmod{N}[/mm] ist genau dann
> fuer alle [mm]z \in \IZ[/mm] loesbar, wenn fuer jede Primzahl [mm]p[/mm] mit
> [mm]p^2 \mid N[/mm] gilt [mm]p \equiv 1 \pmod{4}[/mm].
>
> LG Felix
>
Sehe ich auch so, wobei mir der Fall $p= 2$ noch unklar ist, aber hoechstwahrscheinlich ist er trivial. Der folgende Beweis fuer Deine Behauptung ist stellenweise erlaeuterungsbeduerftig, aber sicherlich richtig und auch ganz elementar. Also beweise ich ersteinmal nur den Fall $n$ ungerade.
Sei [mm] $n\in \IN$, [/mm] $n>1$ und $R:= [mm] \IZ_{n}$. [/mm] Es ist [mm] $R^{2}+ R^{2}= [/mm] R$ genau dann, wenn fuer alle Primzahlen $p$ gilt: Ist [mm] $p^{2}\vert [/mm] n$, so gilt [mm] $p\equiv_{4} [/mm] 1$.
Beweis: Nach dem Chinesischen Restsatz genuegt es die Behauptung fuer $n= [mm] p^{m}$ [/mm] Primzahlpotenz zu betrachten. Ferner wurde die Behauptung schon fuer alle Primzahlen bewiesen.
Daraus ergibt sich
1. $R$ ist ein lokaler Hauptidealring. Sei $G$ seine Einheiten Gruppe. Es gilt
2. $G= [mm] A\times [/mm] C$, wo $A$ eine abelsche Gruppe der Ordnung [mm] $p^{n-1}$ [/mm] und $C$ eine zyklische Gruppe der Ordnung $p-1$ ist. Folglich ist [mm] $|G:G^{2}|= [/mm] 2$ und wegen $p>2$ sind alle Elemente von $A$ Quadrate. Fuer alle [mm] $0\neq r\in [/mm] R$ gibt es ein eindeutig bestimmtes [mm] $\varepsilon\in [/mm] G$ und eindeutig bestimmtes [mm] $e\in\{0,\ldots, n-1\}$ [/mm] mit $r= [mm] \varepsilon p^{e}$.
[/mm]
Es sei $L:= pR$ das eindeutig bestimmte maximale Ideal von $R$. Dann ist
3. $R= [mm] L\dot{\cup} G^{2}\dot{\cup} G^{2}x$, [/mm] wobei [mm] $x\in [/mm] G$ ein Nichtquadrat ist, und [mm] $R^{2}= p^{2}R\dot{\cup} G^{2}$. [/mm] Man erkennt hier schon, dass es sich eigentlich nur die Darstellbarkeit von $p$ und $x$ dreht.
Als erstes sei [mm] $R^{2}+ R^{2}= [/mm] R$ vorausgesetzt und $m>1$. Es ist insbesondere [mm] $p\equiv_{p^{m}} r^{2}+ s^{2}$, $r,s\in \IZ$. [/mm] Waere nun [mm] $r\equiv_{p} [/mm] 0$, so auch [mm] $s\equiv_{p} [/mm] 0$. Wegen $m>1$ waere dann aber [mm] $p\vert [/mm] 1$; Widerspruch. Damit sind $r,s$ invertierbar in [mm] $\Z_{p}$, [/mm] sodass $-1$ ein Quadrat modulo $p$ ist und somit [mm] $p\equiv_{4} [/mm] 1$.
Nun sei $m>1$ vorausgesetzt und [mm] $p\equiv_{4} [/mm] 1$. Dann ist $p$ in [mm] $\IZ$ [/mm] darstellbar als Summe zweier Quadrate, also erst recht darstellbar als Summe zweier Quadrate in $R$. Es ist [mm] $R/L\simeq \IZ_{p}$, [/mm] wofuer die Behauptung schon bewiesen wurde, sodass fuer das $x$ aus 3. gilt $x= [mm] r^{2}+ s^{2}+ [/mm] pt$ fuer gewisse [mm] $r,s,t\in [/mm] R$. Nun ist wegen [mm] $x\in [/mm] G$ auch $qs:= [mm] r^{2}+ s^{2}\in [/mm] G$. Also $x= qs(1+ [mm] p(qs)^{-1}l)$. [/mm] Man prueft leicht nach, dass die Elemente der Gestalt $1+pk$, [mm] $k\in [/mm] R$, $p$-Elemente sind, also Quadrate, wegen $p>2$. Somit ist $x= [mm] (r^{2}+ s^{2})g^{2}= (rg)^{2}+ (sg)^{2} [/mm] $ Summe zweier Quadrate.
Nun folgt [mm] $R^{2}+ R^{2}= [/mm] R$: [mm] $0\in R^{2}+ R^{2}$ [/mm] ist klar. Sei [mm] $0\neq r\in [/mm] R$, also $r= [mm] \eps p^{e}$, $\varepsilon\in [/mm] G$. Ist $e$ gerade, so ist [mm] $p^{e}\in R^{2}\subseteq R^{2}+ R^{2}$. [/mm] Ist $e$ ungerade, so ist [mm] $p^{e}= pp^{e-1}\in (R^{2}+ R^{2})R^{2}= R^{2}+ R^{2}$. [/mm] Ist [mm] $\varepsilon$ [/mm] kein Quadrat, so ist es nach 3. von der Gestalt [mm] $\lambda^{2} x\in R^{2}(R^{2}+ R^{2})= R^{2}+ R^{2}$. [/mm] Folglich ist $r$ Produkt zweier Elemente aus [mm] $R^{2}+ R^{2}$, [/mm] aber wie im $2$-Quadrate-Satz gilt auch hier, dass so ein Produkt wieder in [mm] $R^{2}+ R^{2}$ [/mm] liegt. Somit $R= [mm] R^{2}+ R^{2}$. [/mm]
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:34 Di 20.09.2011 | | Autor: | felixf |
Moin,
> > folgende Behauptung auf:
> >
> > Die Gleichung [mm]x^2 + y^2 \equiv z \pmod{N}[/mm] ist genau dann
> > fuer alle [mm]z \in \IZ[/mm] loesbar, wenn fuer jede Primzahl [mm]p[/mm] mit
> > [mm]p^2 \mid N[/mm] gilt [mm]p \equiv 1 \pmod{4}[/mm].
>
> Sehe ich auch so, wobei mir der Fall [mm]p= 2[/mm] noch unklar ist,
> aber hoechstwahrscheinlich ist er trivial. Der folgende
ja, ist er: sei $n = [mm] p^m$. [/mm] Ist $m = 1$, so gilt die Aussage. Ist $m = 2$, so laesst sich etwa 3 nicht darstellen. Ist $m > 2$ und wuerde die Aussage gelten, so koennte man sich das ganze modulo [mm] $2^2$ [/mm] anschauen und somit wuerde sie auch fuer $m = 2$ gelten, was aber nicht so ist. Also gilt sie fuer kein $m [mm] \ge [/mm] 2$.
> Beweis fuer Deine Behauptung ist stellenweise
> erlaeuterungsbeduerftig, aber sicherlich richtig und auch
> ganz elementar. Also beweise ich ersteinmal nur den Fall [mm]n[/mm]
> ungerade.
>
> Sei [mm]n\in \IN[/mm], [mm]n>1[/mm] und [mm]R:= \IZ_{n}[/mm]. Es ist [mm]R^{2}+ R^{2}= R[/mm]
> genau dann, wenn fuer alle Primzahlen [mm]p[/mm] gilt: Ist
> [mm]p^{2}\vert n[/mm], so gilt [mm]p\equiv_{4} 1[/mm].
>
> Beweis: Nach dem Chinesischen Restsatz genuegt es die
> Behauptung fuer [mm]n= p^{m}[/mm] Primzahlpotenz zu betrachten.
> Ferner wurde die Behauptung schon fuer alle Primzahlen
> bewiesen.
>
> Daraus ergibt sich
> 1. [mm]R[/mm] ist ein lokaler Hauptidealring. Sei [mm]G[/mm] seine Einheiten
> Gruppe. Es gilt
> 2. [mm]G= A\times C[/mm], wo [mm]A[/mm] eine abelsche Gruppe der Ordnung
> [mm]p^{n-1}[/mm] und [mm]C[/mm] eine zyklische Gruppe der Ordnung [mm]p-1[/mm] ist.
> Folglich ist [mm]|G:G^{2}|= 2[/mm] und wegen [mm]p>2[/mm] sind alle Elemente
> von [mm]A[/mm] Quadrate. Fuer alle [mm]0\neq r\in R[/mm] gibt es ein
> eindeutig bestimmtes [mm]\varepsilon\in G[/mm] und eindeutig
> bestimmtes [mm]e\in\{0,\ldots, n-1\}[/mm] mit [mm]r= \varepsilon p^{e}[/mm].
>
> Es sei [mm]L:= pR[/mm] das eindeutig bestimmte maximale Ideal von [mm]R[/mm].
> Dann ist
> 3. [mm]R= L\dot{\cup} G^{2}\dot{\cup} G^{2}x[/mm], wobei [mm]x\in G[/mm] ein
> Nichtquadrat ist, und [mm]R^{2}= p^{2}R\dot{\cup} G^{2}[/mm]. Man
> erkennt hier schon, dass es sich eigentlich nur die
> Darstellbarkeit von [mm]p[/mm] und [mm]x[/mm] dreht.
>
> Als erstes sei [mm]R^{2}+ R^{2}= R[/mm] vorausgesetzt und [mm]m>1[/mm]. Es
> ist insbesondere [mm]p\equiv_{p^{m}} r^{2}+ s^{2}[/mm], [mm]r,s\in \IZ[/mm].
> Waere nun [mm]r\equiv_{p} 0[/mm], so auch [mm]s\equiv_{p} 0[/mm]. Wegen [mm]m>1[/mm]
> waere dann aber [mm]p\vert 1[/mm]; Widerspruch. Damit sind [mm]r,s[/mm]
> invertierbar in [mm]\Z_{p}[/mm], sodass [mm]-1[/mm] ein Quadrat modulo [mm]p[/mm] ist
> und somit [mm]p\equiv_{4} 1[/mm].
![[ok]](/images/smileys/ok.gif "[ok]")
> Nun sei [mm]m>1[/mm] vorausgesetzt und [mm]p\equiv_{4} 1[/mm]. Dann ist [mm]p[/mm] in
> [mm]\IZ[/mm] darstellbar als Summe zweier Quadrate, also erst recht
> darstellbar als Summe zweier Quadrate in [mm]R[/mm]. Es ist
> [mm]R/L\simeq \IZ_{p}[/mm], wofuer die Behauptung schon bewiesen
> wurde, sodass fuer das [mm]x[/mm] aus 3. gilt [mm]x= r^{2}+ s^{2}+ pt[/mm]
> fuer gewisse [mm]r,s,t\in R[/mm]. Nun ist wegen [mm]x\in G[/mm] auch [mm]qs:= r^{2}+ s^{2}\in G[/mm].
> Also [mm]x= qs(1+ p(qs)^{-1}l)[/mm]. Man prueft leicht nach, dass
Hier ist $l = t$, oder?
> die Elemente der Gestalt [mm]1+pk[/mm], [mm]k\in R[/mm], [mm]p[/mm]-Elemente sind,
> also Quadrate, wegen [mm]p>2[/mm]. Somit ist [mm]x= (r^{2}+ s^{2})g^{2}= (rg)^{2}+ (sg)^{2}[/mm]
> Summe zweier Quadrate.
>
> Nun folgt [mm]R^{2}+ R^{2}= R[/mm]: [mm]0\in R^{2}+ R^{2}[/mm] ist klar. Sei
> [mm]0\neq r\in R[/mm], also [mm]r= \epsilon p^{e}[/mm], [mm]\varepsilon\in G[/mm]. Ist [mm]e[/mm]
> gerade, so ist [mm]p^{e}\in R^{2}\subseteq R^{2}+ R^{2}[/mm]. Ist [mm]e[/mm]
> ungerade, so ist [mm]p^{e}= pp^{e-1}\in (R^{2}+ R^{2})R^{2}= R^{2}+ R^{2}[/mm].
> Ist [mm]\varepsilon[/mm] kein Quadrat, so ist es nach 3. von der
> Gestalt [mm]\lambda^{2} x\in R^{2}(R^{2}+ R^{2})= R^{2}+ R^{2}[/mm].
> Folglich ist [mm]r[/mm] Produkt zweier Elemente aus [mm]R^{2}+ R^{2}[/mm],
> aber wie im [mm]2[/mm]-Quadrate-Satz gilt auch hier, dass so ein
> Produkt wieder in [mm]R^{2}+ R^{2}[/mm] liegt. Somit [mm]R= R^{2}+ R^{2}[/mm].
Super 
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:58 Mo 19.09.2011 | | Autor: | wauwau |
p=3, r=3 ist ja auch ein "entartetes" Beispiel 
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:18 Mo 19.09.2011 | | Autor: | reverend |
Hallo Felix,
nein, die ursprüngliche Aussage von wauwau gilt damit noch nicht für n=2(2m+1).
Für n=18 sind z.B. die Restklassen 3,6,12,15 nicht als Summe von Quadraten darzustellen. Oder schon für n=9 die Restklassen 3 und 6.
Meine Aussage bezieht sich doch nur auf n=2m+1 und m+1 Restklassen. Dieser Fall ist für ungerade Primzahlen und ihre quadratischen Reste gegeben.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 13:39 Mo 19.09.2011 | | Autor: | felixf |
Moin rev,
> nein, die ursprüngliche Aussage von wauwau gilt damit noch
> nicht für n=2(2m+1).
>
> Für n=18 sind z.B. die Restklassen 3,6,12,15 nicht als
> Summe von Quadraten darzustellen. Oder schon für n=9 die
> Restklassen 3 und 6.
es gilt fuer $n = 18$ genau dann, wenn es fuer $n = 2$ und $n = 9$ gilt (chinesischer Restsatz).
> Meine Aussage bezieht sich doch nur auf n=2m+1 und m+1
> Restklassen. Dieser Fall ist für ungerade Primzahlen und
> ihre quadratischen Reste gegeben.
Ooh, da hab ich mich etwas verlesen. Ok, ja, du hast Recht.
Zumindest gilt es fuer alle quadratfreien $n$.
Man koennte jetzt vermuten: fuer Primzahlpotenzen gilt es nicht. [mm] $2^2 [/mm] = 4$ und [mm] $3^2 [/mm] = 9$ sind schonmal Beispiele, wo das stimmt. Stimmt das auch fuer andere Primzahlpotenzen?
(Mein Programm hab ich zuhause, ich probier das heute abend etwas aus wenn ich dran denke...)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 20:41 Mo 19.09.2011 | | Autor: | wauwau |
| Aufgabe | Wie schauts allgemein aus?
Für welche $k [mm] \ge [/mm] 2$ und $m [mm] \in \IN$ [/mm] gibts für alle $0 [mm] \le [/mm] r [mm] \le [/mm] m-1$ eine Lösung von
[mm] $x^k [/mm] + [mm] y^k \equiv [/mm] r(m)$ |
Für k=3, m=5 gehts z.B.
Oder modulare Varianten von FLT?
Für welche Module m gilt z.b.
[mm] $x^k+y^k \equiv z^k [/mm] (m)$
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 23:21 Mo 19.09.2011 | | Autor: | reverend |
Guten Abend,
> Wie schauts allgemein aus?
> Für welche [mm]k \ge 2[/mm] und [mm]m \in \IN[/mm] gibts für alle [mm]0 \le r \le m-1[/mm]
> eine Lösung von
> [mm]x^k + y^k \equiv r(m)[/mm]
>
> Für k=3, m=5 gehts z.B.
Es könnte leichter sein, die k,m zu identifizieren, für die es nicht gilt, z.B. k=3, m=7 oder k=5, m=7 etc.
> Oder modulare Varianten von FLT?
> Für welche Module m gilt z.b.
> [mm]x^k+y^k \equiv z^k (m)[/mm]
Dazu gab es doch reichlich Untersuchungen. Man braucht bloß die Literatur ab ca. 1860 zu durchforsten (und ein paar frühere Publikationen). Das könnte ich mir gern für den Ruhestand vornehmen, also etwa ab 2030.
Vielleicht genügt es aber auch, Kummer, Wieferich und Mirimanoff zu lesen.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:08 Di 20.09.2011 | | Autor: | felixf |
Moin!
> Wie schauts allgemein aus?
> Für welche [mm]k \ge 2[/mm] und [mm]m \in \IN[/mm] gibts für alle [mm]0 \le r \le m-1[/mm]
> eine Lösung von
> [mm]x^k + y^k \equiv r(m)[/mm]
Ist etwa $m$ prim und $k = m$, so geht es immer (da dann [mm] $x^k \equiv [/mm] x [mm] \pmod{m}$ [/mm] fuer alle $x [mm] \in \IZ$ [/mm] gilt).
Ist $m$ prim, so kann man erstmal $k$ modulo $p - 1$ betrachten. Dann kann man das Geschlecht der alg. Kurve [mm] $X^k [/mm] + [mm] Y^k [/mm] + r = 0$ nach oben abschaetzen und dann mit Hasse-Weil nach oben abschaetzen, wieviele Punkte es in [mm] $\IF_m$ [/mm] gibt. Ist die Schranke $> 0$ (abzueglich moeglicher projektiver Punkte), so weiss man dass die Gleichung [mm] $x^k [/mm] + [mm] y^k \equiv [/mm] -r [mm] \pmod{m}$ [/mm] loesbar ist.
(Das Geschlecht ist etwa durch $(k + [mm] 1)^2/2$ [/mm] nach oben beschraenkt. Nach Hasse-Weil hat die projektive Kurve somit mindestens $m - 2 g [mm] m^{1/2}$ [/mm] Punkte.
Die projektive Kurve ist durch die homogene Gleichung [mm] $X^k [/mm] + [mm] Y^k [/mm] + r [mm] Z^k [/mm] = 0$ gegeben; die affinen Punkte sind die mit $Z = 1$, die echt projektiven die mit $Z = 0$. Also muss man jetzt abschaetzen, wieviele projektive Punkte es fuer $Z = 0$ gibt. In dem Fall ist [mm] $X^k [/mm] + [mm] Y^k [/mm] = 0$, also muessen sowohl $X$ und $Y$ [mm] $\neq [/mm] 0$ sein. Ohne Einschraenkung kann man durch [mm] $X^k$ [/mm] teilen, also bekommt man $1 + [mm] (Y/X)^k [/mm] = 0$. Die Anzahl der echt projektiven Punkte ist also gleich der Anzahl der Loesungen von [mm] $w^k [/mm] = -1$. (Und diese laesst sich durch die Anzahl der Loesungen von [mm] $w^{2 k} [/mm] = 1$ nach oben abschaetzen.) Die Gleichung [mm] $w^{2 k} [/mm] = 1$ hat $ggT(2 k, m - 1)$ Loesungen, womit es also immer mindestens $m - 2 (k + [mm] 1)^2 m^{1/2} [/mm] - ggT(2 k, m - 1)$ affine Punkte in [mm] $\IF_m$ [/mm] gibt.
Gilt also $m > 2 (k + [mm] 1)^2 m^{1/2} [/mm] + ggT(2 k, m - 1)$ (mit $m$ prim), so ist die Gleichung [mm] $x^k [/mm] + [mm] y^k \equiv [/mm] r [mm] \pmod{m}$ [/mm] definitiv fuer alle $r$ loesbar. Ist also $k$ klein und $m$ gross, so gibt es immer eine Loesung (es gilt etwa $ggT(2 k, m - 1) [mm] \le [/mm] 2 k [mm] \le [/mm] 2 (k + [mm] 1)^2 m^{1/2}$, [/mm] womit fuer $m > 16 (k + [mm] 1)^4$ [/mm] die Gleichung immer loesbar ist.)
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 21:22 Mi 28.09.2011 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
