Ist 4 quadratischer Rest (mod 3)?

Neue Frage »

Very Auf diesen Beitrag antworten »
Ist 4 quadratischer Rest (mod 3)?
Hallo,
ich habe folgende Aufgabe bearbeitet und wüsste gerne, ob das richtig ist.

Aufgabe: Ist 4 quadratischer Rest (mod 3)?

Ich habe also das Eulerkriterium angewandt. Das darf ich da 4 modulo 3 equivalent zu 1 und damit ungleich 0 ist (das ist die Voraussetzung)



Da das Legendre-Symbol gleich 1 ist, ist 4 ein quadratischer Rest modulo 3.

Ist das richtig so? Ist meine erste solche Aufgabe...
Danke
weisbrot Auf diesen Beitrag antworten »
RE: Ist 4 quadratischer Rest (mod 3)?
ja, aber dass 4 quadrat mod 3 ist kannst du auch direkt sehen weil 1^2=1.
lg
Very Auf diesen Beitrag antworten »

Meintest du ?

Ach so, heißt quadratischer Rest einfach, dass ich die Zahl quadriere und dann schaue was (in dem Fall modulo 3) als Rest herauskommt?
weisbrot Auf diesen Beitrag antworten »

ne, a quadratischer rest mod p heißt es gibt q sodass q^2=a mod p.
lg
HAL 9000 Auf diesen Beitrag antworten »

Und deswegen ist auch 4 ein quadratischer Rest modulo für alle , schlicht und einfach weil . Augenzwinkern
weisbrot Auf diesen Beitrag antworten »

außer mod 2Augenzwinkern
 
 
Very Auf diesen Beitrag antworten »

ah, ok.
Für die Frage ist 4 quadratischer Rest modulo 3 gilt also

Es gibt also ein q=1 mit

Geht das bei anderen Beispielen auch so einfach?
z.B. wenn ich betrachte: Ist 7 quadratischer Rest modulo 5?

Über das Eulerkriterium habe ich erhalten



Die Antwort ist hier also nein.

Kann ich das auch so einfach sehen?
Ich muss also zeigen, dass es kein q gibt mit

Wie könnte ich denn das zeigen?
Reicht es, einfach alle q von 0 bis 6 einzusetzen und zu schauen obs passt? Und da wir in modulo 7 sind, gibt es keine Lösung, falls es eine von diesen ist..
weisbrot Auf diesen Beitrag antworten »

genau, um zu zeigen dass etwas nicht quadrat(ischer rest) ist kannst du die quadrate aller reste mod p untersuchen (denn alle anderen zahlen sind ja zu einer dieser zahlen kongruent mod p). wird natürlich etwas aufwändig sobald die zahlen größer werden.
lg
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von weisbrot
außer mod 2Augenzwinkern

Nein, keine Ausnahme. unglücklich

EDIT: Ja, Ok, wenn man den Begriff des quadratischen Rests "enger" fasst, hast du Recht. Im engeren Sinn müsste man aber auch gleich alle geraden m herausnehmen. Augenzwinkern
weisbrot Auf diesen Beitrag antworten »

doch, per definition (zumindest in diesen zusammenhängen) ist 0 kein quadrat(ischer rest).
lg
Very Auf diesen Beitrag antworten »

@HAL_9000
Zitat:
Und deswegen ist auch 4 ein quadratischer Rest modulo für alle , schlicht und einfach weil . Augenzwinkern


Das verstehe ich noch nicht. Wie hast du das gemacht?
Wenn ich modulo irgendwas nehme, das kleiner als 4 ist, kann doch da gar nicht mehr 4 rauskommen...

Das Eulerkriterium hat hier auch nicht geklappt da

ich habe also weder -1 noch 1 und kann daher mit diesem Kriterium keine Aussage treffen..
HAL 9000 Auf diesen Beitrag antworten »

Ich gebe mich geschlagen - die Auffassung im "engeren" Sinne hat ihre Vorteile, weil man dann keine Teilerfremdheit bei Euler-Kriterium etc. pp. extra voraussetzen muss. Augenzwinkern
Very Auf diesen Beitrag antworten »

@weißbrot

Zitat:
genau, um zu zeigen dass etwas nicht quadrat(ischer rest) ist kannst du die quadrate aller reste mod p untersuchen (denn alle anderen zahlen sind ja zu einer dieser zahlen kongruent mod p). wird natürlich etwas aufwändig sobald die zahlen größer werden. lg


Ich habe das jetzt mal versucht und erhalten, dass 7 quadratischer Nichtrest modulo 5 ist, da

(dies gilt alles modulo 5) :
q=0 --> q²=0
q=1 --> q²=1
q=2 --> q²=-1
q=3 --> q²=-1
q=4 --> q²=-1
q=5 --> q²=0
q=6 --> q²=1

Ich habe also nirgendwo zwei rausbekommen.

Ist das hier eigentlich ein Zufall, dass ich immer 0,-1 und 1 erhalte? Also die 2 habe ich nicht erwartet, denn dann wäre es ja ein quadratischer Rest. Aber die -2 ist z.B. gar nicht aufgetaucht... (andere Zahlen sind ja bei modulo 5 nicht möglich)

Und du hast Recht, irgendwann wird das aufwendig. Aber bei kleinen Zahlen gehts smile Gibts noch eine andere Methode, die da leichter gehen würde? (wenn z.B. das Kriterium von Euler mal nicht klappt..)?
Very Auf diesen Beitrag antworten »

Zitat:
doch, per definition (zumindest in diesen zusammenhängen) ist 0 kein quadrat(ischer rest).


heißt das, dass ich wenn ich beim Eulerkriterium 0 erhalte, einen quadratischen Nichtrest habe? Ich dachte das gilt nur wenn ich -1 erhalte...
HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von Very
Wenn ich modulo irgendwas nehme, das kleiner als 4 ist, kann doch da gar nicht mehr 4 rauskommen...

Wie so viele Leute verwechselst du die Operation im Bereich der ganzen Zahlen mit dem inhaltlich anderen im Restklassenring .
weisbrot Auf diesen Beitrag antworten »

@hal: genau. ich hab mich auch erst gewundert als ich die definition vom legendresymbol zum ersten mal gesehen hab ob die nicht ans tertium non datur glaubenBig Laugh

@very:
Zitat:
heißt das, dass ich wenn ich beim Eulerkriterium 0 erhalte, einen quadratischen Nichtrest habe? Ich dachte das gilt nur wenn ich -1 erhalte...
nein, das ist der fall dass die betrachtete zahl vielfaches von p ist (edit: das war übrigends auch eine antwort an hal).
Zitat:
Ist das hier eigentlich ein Zufall, dass ich immer 0,-1 und 1 erhalte?
ne, das kommt daher dass du die quadrate falsch gerechnet hast^^
und was meinst du damit dass du nirgendwo 2 rausbekommen hast? das aus meinem post davor bezog sich auf hal's post dass 4 überall quadratischer rest ist (kann eigendlich erstmal egal sein).

ist jetzt alles irgendwie geklärt? geht ja grad etwas durcheinander..
lg
Very Auf diesen Beitrag antworten »

ja, wahrscheinlich... Ich sehe den Unterschied zwischen den beiden aber noch nicht...

Also ich kenne das so:

z.B. . Das ist also dein als 2. genannter Fall im Restklassenring...

Und was ist dann der andere Fall? Und wo liegt jetzt mein Fehler bei:
Zitat:
Wenn ich modulo irgendwas nehme, das kleiner als 4 ist, kann doch da gar nicht mehr 4 rauskommen...
?
Very Auf diesen Beitrag antworten »

ok, also ich versuch das man nochmals zusammenzufassen: Noch offene Fragen habe ich mal dick markiert:

Würde mich freuen, wenn du das kurz überprüfen könntest.

Um festzustellen, ob eine Zahl a ein quadratischer Rest (modulo p ) ist, habe ich mehrere Möglichkeiten

1) verwende das Eulerkriterium.
Ist das Ergebnis = 1 ist a ein quadratischer Rest.
Ist das Ergebnis gleich -1 ist a ein quadratischer Nichtrest.
Ist das Ergebnis gleich 0 ist die betrachtete Zahl a ein Vielfaches von p (Was heißt das jetzt im Bezug auf Rest oder Nichtrest?)
Und: Gibt es noch ein anderes mögliches Ergebnis? Also was wäre wenn das Ergebnis gleich 2 oder -2 ist (das wäre bei p=5 ja z.B. grundsätzlich möglich)

2) verwende die Definition für quadratischer Rest.

a ist quadratischer Rest genau dann, wenn es existiert ein q : q²=a (mod p)
(Wenn ich ein solches q finde (ich untersuche nur die q die zwischen 0 und p-1 liegen, da in in bin, ist a ein quadratischer Rest.
Finde ich kein solches q, ist a ein quadratischer Nichtrest.
Für große p kann dieses Verfahren aber sehr lange dauern.

Ich hatte vorher bei der Berechnung der Quadrate für q² nur 0,-1 und 1 erhalten (den von dir genannten Rechenfehler habe ich hier nicht gefunden - was war denn daran falsch?)

Zitat:
Ich habe das jetzt mal versucht und erhalten, dass 7 quadratischer Nichtrest modulo 5 ist, da (dies gilt alles modulo 5) : q=0 --> q²=0
q=1 --> q²=1
q=2 --> q²=-1
q=3 --> q²=-1
q=4 --> q²=-1
q=5 --> q²=0
q=6 --> q²=1


Und ich hatte mich jetzt nur gewundert, dass da nie eine 2 rauskommt (aber das ist wohl Zufall - falls ich mich nicht doch verrechnet und nur den Fehler nicht gefunden habe?)
weisbrot Auf diesen Beitrag antworten »

edit: also das war noch zu dem post vorher, antwort auf deinen letzten folgt sogleichAugenzwinkern

also nochmal: die ganze unterhaltung mit hal 9000 ging darum, dass er meinte 4 ist sowieso (also mod jeder zahl m) ein quadrat (weil ja 2^2=4 immer gilt). aber 4 ist ja mod 2 (und auch mod 4) gleich 0 - was man in diesen zusammenhängen nicht als quadratischen rest betrachtet (obwohl ja immer 0^2=0) - das ist einfach nur definition - also quadratischer rest mod p heißt eigendlich dass die zahl quadrat sein muss aber auch kein vielfaches von p.

ging die frage vom (edit: vor-)letzten post jetzt an mich oder hal 9000?

lg
Very Auf diesen Beitrag antworten »

die ging an HAL_9000 (Ich hätte wohl besser ein @ verwendet... )
weisbrot Auf diesen Beitrag antworten »

Zitat:
Ist das Ergebnis gleich 0 ist die betrachtete Zahl a ein Vielfaches von p (Was heißt das jetzt im Bezug auf Rest oder Nichtrest?)
ist etwas vielfaches von p dann ist es weder quadratischer rest noch nichtrest mod p, sondern einfach rest 0, was man als gesondert sieht.

Zitat:
Gibt es noch ein anderes mögliches Ergebnis? Also was wäre wenn das Ergebnis gleich 2 oder -2 ist (das wäre bei p=5 ja z.B. grundsätzlich möglich)
mögliches ergebnis wofür?

Zitat:
a ist quadratischer Rest genau dann, wenn es existiert ein q : q²=a (mod p)
beachte nochmal meinen post von davor.

Zitat:
Ich hatte vorher bei der Berechnung der Quadrate für q² nur 0,-1 und 1 erhalten (den von dir genannten Rechenfehler habe ich hier nicht gefunden - was war denn daran falsch?) Zitat: Ich habe das jetzt mal versucht und erhalten, dass 7 quadratischer Nichtrest modulo 5 ist, da (dies gilt alles modulo 5) : q=0 --> q²=0 q=1 --> q²=1 q=2 --> q²=-1 q=3 --> q²=-1 q=4 --> q²=-1 q=5 --> q²=0 q=6 --> q²=1

4^2=1 mod 5 - das meinte ich aber nicht, ich hab mich einfach verguckt/verrechnet. ja das kann man zufall nennen wenn man möchte. das bedeutet hierfür dass weder 2 noch 3 quadrate mod 5 sind, also auch nicht 7 (7=2 mod 5).

lg
Very Auf diesen Beitrag antworten »

@ weißbrot:
zur Unterhaltung mit HAL_9000
also habe ich das richtig verstanden, dass gilt:
nach Definition ist 4 kein quadratischer Rest (modulo 2) und 4 ist kein quadratischer Rest (modulo 4), aber 4 ist quadratischer Rest modulo allen anderen natürlichen Zahlen (für p=1 und p=3 müsste man das ja noch extra ausrechnen, aber das klappt) und für alle p>4 gilt immer , da kann das modulo ja nichts mehr "kaputt machen".

Also ist 4 quadratischer Nichtrest (modulo 2) und (modulo 4) (nach Definition, da 4 ein Vielfaches von 2 bzw. 4 ist)

Analog könnte man dann sag, dass 6 quadratischer Nichtrest modulo 3 ist, weil 6 ein Vielfaches von 3 ist,...
Very Auf diesen Beitrag antworten »

Zitat:
ist etwas vielfaches von p dann ist es weder quadratischer rest noch nichtrest mod p, sondern einfach rest 0, was man als gesondert sieht.


nach der Antwort von dir war diese Aussage von mir falsch:
Zitat:
Also ist 4 quadratischer Nichtrest (modulo 2) und (modulo 4) (nach Definition, da 4 ein Vielfaches von 2 bzw. 4 ist)


Es gilt also richtig: 4 ist weder quadratischer Rest, noch quadratischer Nichtrest (modulo 2) und (modulo 4)
weisbrot Auf diesen Beitrag antworten »

also das ist meine antwort auf deinen vorletzten post:

Zitat:
(für p=1 und p=3 müsste man das ja noch extra ausrechnen, aber das klappt) und für alle p>4 gilt immer , da kann das modulo ja nichts mehr "kaputt machen".

das modulo macht auch für p=3 nichts kaputt, und mod 1 ist sowieso alles 0.

Zitat:
Also ist 4 quadratischer Nichtrest (modulo 2) und (modulo 4) (nach Definition, da 4 ein Vielfaches von 2 bzw. 4 ist)

ne, guck nochmal meine posts von davor, 4 ist mod 2 oder 4 weder quadr. rest noch nichtrest, sondern vielfaches von 2 bzw. 4, was in beiden fällen (rest/ nichtrest) ausgeschlossen ist. genauso mit 6 mod 3.

und das meine antwort auf deinen letzten:

je genauAugenzwinkern

lg
Very Auf diesen Beitrag antworten »

@weisbrot
Zitat:
mögliches ergebnis wofür?

Für das Ergebnis das ich erhalte, wenn ich das Eulerkriterium anwende. Wenn ich 1 erhalte hab ich einen quadratischen Rest, für -1 einen quadratischen Nichtrest und für 0 keines von beidem.
Wäre es möglich, dass ich weder 1 noch -1 noch 0 sondern z.B. 2 erhalte? Ich betrachte ja eine Zahl nur modulo p und für p=5 könnte ich ja alle Zahlen zwischen 0 und 4 (bzw. -2 und 2) erhalten.

Zitat:
beachte nochmal meinen post von davor.

besser: a ist quadratischer Rest genau dann, wenn es existiert ein q : q²=a (mod p) und q ist kein Vielfaches von p

Zitat:
das bedeutet hierfür dass weder 2 noch 3 quadrate mod 5 sind

Das gilt, da ich weder 2 noch 3 als Ergebnis erhalte.

Zitat:
also auch nicht 7 (7=2 mod 5)

Kann ich dann sagen: Also auch nicht ...=22=17=12=7=2 mod 5?
weisbrot Auf diesen Beitrag antworten »

1. ne, mit dem eulerkriterium berechnet man ja das legendresymbol (für ungerade primzahlen), das nimmt nach def. nur -1, 1 oder 0 an.

2. nicht ganz, a soll kein vielfaches von p sein!

3. ja.

4. ja genau. wäre a=2 mod p und a ein quadratischer rest mod p, dann doch auch 2, denn es wird ja alles mod p betrachtet.

so ich hoffe jetzt ist alles etwas klarer. ist auch neigendlich total einfach, unser thread ging nur etwas durcheinander, was mir leid tut. ich entlasse mich selbst jetzt ins wochenende und wünsche dir eine schönes selbiges! wenn noch fragen sind kann die dir bestimmt noch wer anders beantworten, oder stell sie nochmal explizit in einem neuen thread.

lg
Very Auf diesen Beitrag antworten »

Zitat:
nicht ganz, a soll kein vielfaches von p sein!

oh, ja das meinte ich auch.

ok, jetzt hab ich alles verstanden smile
Vielen vielen Dank für die Hilfe und deine Geduld. Hat mir wirklich sehr viel geholfen.
Wünsche dir ein schönes Wochenende.
lg Very
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »