Lösung einer mod - Gleichung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:08 So 15.07.2007 | | Autor: | peder |
| Aufgabe | Bestimmen sie alle n mit [mm] 1\le [/mm] n [mm] \le999; n\in\IN [/mm] für die gilt:
[mm] n^{2}=500 [/mm] mod 1000 |
Hallo erstmal, und schönen Sonntag!
hoffe ihr könnt mir mit der Aufgabe helfen.
Mein erster Gedanke war das Reziprozitätsgesetz anzuwenden, aber das hat mich nicht wirklich weiter gebracht.
habe auch mal die 1000 auf gespallten in [mm] 5^{3}*2^{3} [/mm] und dann [mm] n^{2}=500 [/mm] mod 8 bzw. [mm] n^{2}=500 [/mm] mod 125 betrachtet mit euklidischen Algorithmus usw. bekomme ich so die zwei Lösungen 250 und 750, aber dass kann nicht der richtige Weg sein,oder? denn alleine durch raten komme ich schon auf die Lösungen 50, 150, 250, ..., 950
also mein Problem ist somit weniger nur die richtige Lösung als vielmehr ein vernünftiger Weg, der mich dahinführt 
danke,
Michi
p.s.: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:29 So 15.07.2007 | | Autor: | felixf |
Hallo Michi!
> Bestimmen sie alle n mit [mm]1\le[/mm] n [mm]\le999; n\in\IN[/mm] für die
> gilt:
> [mm]n^{2}=500[/mm] mod 1000
> Hallo erstmal, und schönen Sonntag!
> hoffe ihr könnt mir mit der Aufgabe helfen.
> Mein erster Gedanke war das Reziprozitätsgesetz
> anzuwenden, aber das hat mich nicht wirklich weiter
> gebracht.
> habe auch mal die 1000 auf gespallten in [mm]5^{3}*2^{3}[/mm] und
> dann [mm]n^{2}=500[/mm] mod 8 bzw. [mm]n^{2}=500[/mm] mod 125 betrachtet mit
> euklidischen Algorithmus usw. bekomme ich so die zwei
> Lösungen 250 und 750, aber dass kann nicht der richtige Weg
> sein,oder?
Dann hast du etwas nicht ganz vollstaendig gemacht. :)
Hast du wirklich alle Loesungen von [mm] $n^2 \equiv [/mm] 500 [mm] \pmod{8}$ [/mm] und alle Loesungen von [mm] $n^2 \equiv [/mm] 500 [mm] \pmod{125}$ [/mm] berechnet? (Es gibt da i.A. mehrere!) Fuer jedes Paar von Loesungen modulo 8 und modulo 125 ergibt sich genau eine Loesung modulo 1000. (Sprich, die Anzahl der Loesungen multipliziert sich.)
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 15:50 So 15.07.2007 | | Autor: | peder |
Hallo Felix,
zuerst mal danke für die schnelle Antwort. Also auf deinen Tipp hin bin ich die Aufgabe nochmal durchgegangen, aber ändert leider nix :-(
Hab folgendes gemacht:
[mm] n^{2} [/mm] = 500 mod 1000 nach chin. Restsatz aufgesplittet in [mm] n^{2} [/mm] = 500 mod 125 und [mm] n^{2} [/mm] = 500 mod 8
[mm] n^{2} [/mm] = 500 mod 125 [mm] \gdw n^{2} [/mm] = 0 mod 125 [mm] \Rightarrow [/mm] n = 0 mod 125
[mm] n^{2} [/mm] = 500 mod 8 [mm] \gdw n^{2} [/mm] = 4 mod 8 [mm] \Rightarrow [/mm] n = 2 mod 8 bzw. n = -2 mod 8 (es gibt auch noch n = 6 mod 8 bzw. n = -6 mod 8, aber die laufen auf die ersten beiden Fälle hinaus)
bekomme also nur die zwei Fälle:
n = 0 mod 125 und n = 2 mod 8
oder n = 0 mod 125 und n = -2 mod 8
aus diesen Fällen komme ich dann mit dem euklidischen Algorithmus usw. auf die Lösungen 250 und 750
Also ist entweder irgendwo der Wurm drin, oder man muss hier ganz anders vorgehen.
Gruß, Michi
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:52 So 15.07.2007 | | Autor: | felixf |
Hallo Michi
> Hallo Felix,
> zuerst mal danke für die schnelle Antwort. Also auf deinen
> Tipp hin bin ich die Aufgabe nochmal durchgegangen, aber
> ändert leider nix :-(
> Hab folgendes gemacht:
> [mm]n^{2}[/mm] = 500 mod 1000 nach chin. Restsatz aufgesplittet in
> [mm]n^{2}[/mm] = 500 mod 125 und [mm]n^{2}[/mm] = 500 mod 8
> [mm]n^{2}[/mm] = 500 mod 125 [mm]\gdw n^{2}[/mm] = 0 mod 125 [mm]\Rightarrow[/mm] n =
> 0 mod 125
Die letzte Implikation stimmt nicht: etwa fuer $n = [mm] 5^2$ [/mm] ist auch [mm] $n^2 \equiv [/mm] 0 [mm] \pmod{5^3}$. [/mm] Und fuer jedes Vielfache von [mm] $5^2$, [/mm] etwa $0, [mm] 5^2, [/mm] 2 [mm] \cdot 5^2, [/mm] 3 [mm] \cdot 5^2, [/mm] 4 [mm] \cdot 5^2$. [/mm] Man kann sich jetzt allerdings ueberlegen, dass dies schon alle Loesungen sind.
(Warum das so ist: [mm] $n^2 \equiv [/mm] 0 [mm] \pmod{5^3}$ [/mm] heisst ja, dass [mm] $5^3 \mid n^2$ [/mm] gilt. Da 5 eine Primzahl ist, muss also $5$ ein Teiler von $n$ sein, und sogar [mm] $5^2$ [/mm] ein Teiler von $n$ sein (wenn nur $5$ ein Teiler von $n$ ist aber nicht [mm] $5^2$, [/mm] dann ist [mm] $5^3$ [/mm] kein Teiler von [mm] $n^2$). [/mm] Also ist $n = [mm] 5^2 \cdot [/mm] k$, $k [mm] \in \IZ$. [/mm] Die einzigen Moeglichkeiten, damit $n$ zwischen $0$ und [mm] $5^3 [/mm] - 1$ liegt, sind jedoch $k = 0, 1, 2, 3, 4$.)
Damit bekommst du also $2 [mm] \cdot [/mm] 5 = 10$ Loesungen.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 07:43 Mo 16.07.2007 | | Autor: | peder |
also darauf bin ich natürlich nicht gekommen. -Vielen Dank Felix! - werd mir das jetzt gleich nochmal genauer anschaun.
schönen Tag noch,
Michi
|
|
|
|
