Quadratische Reste und mod

Question

d ∈ Z

1) d ist QR(2)

2) d ist QR(4) ⇔ d ≡ 0,1,4 mod 4

3) d ist QR(2^r) ⇔ u ≡ 1 mod 8      (r≥3, d = 2^r * u , u ungerade , s kleiner als r , d ( nicht ≡) 0 mod 2^r

Comments

In 3) sehe ich nicht, wo s vorkommt.

Answer 1

d ∈ Z.

1) d ist QR(2)   Soll man das beweisen ? Dann so:

mod 2 gibt es nur die Reste 1 und 0 , dass sind beides Quadrate

denn 0*0=0   und 1*1=1 .

Also ist jedes d ein quadratischer Rest mod 2.

2) d ist QR(4) ⇔ d ≡ 0,1,4 mod 4  

d ≡ 0 mod 4   und d ≡ 4 mod 4         bedeuten ja das Gleiche.

Das soll bestimmt heißen:

d ist QR(4) ⇔ d ≡ 0,1 mod 4        !!!!

Dann erst mal entsprechend zu 1

0*0=0  und 1*1=1  also sind

0, 1  quadratische Reste mod 4. Für die

eine Richtung brauchst du noch, dass 3∉QR(4) und  2∉QR(4)

Dazu brauchst du nur alle möglichen Quadrate zu checken:

0*0=0  und 1*1=1  und 2*2=4=0 und 3*3=1

Es kommt also nie 3 oder 2 raus ==>   3∉QR(4) und 2∉QR(4).

Comments

Wieso soll 2 quadratischer Rest mod 4 sein?

---

Hast recht, war wohl noch was früh. Danke !

Korrigiere ich.