Residu Kuadratik

Definisi :
Misalkan p bilangan prima, dan x bilangan bulat yang relatif prima terhadap p. Bilangan bulat x dikatakan residu kuadratik dari p jika ada suatu bilangan bulat y sedemikian hingga x=y^2(mod p). Jika x bukan residu kuadratik dari p maka x dikatakan bukan residu kuadratik dari p.

Proposisi I :
Taruhlah p bilangan prima ganjil, serta a, b, dan c bilangan-bilangan bulat dengan a relatif prima terhadap p. Maka ada bilangan bulat x yang memenuhi kongruensi ax^2+bx+c=0(mod p) jika dan hanya jika b^2-4ac=0(mod p) atau b^2-4ac=0(mod p).

Bukti :
Misalkan x bilangan bulat. Maka ax^2+bx+c=0(mod p) jika dan hanya jika 4(a^2)(x^2)+4abx+4ac=0(mod p). (Mengapa ? Diketahui p dan a relatif prima maka 4a dan p juga relatif prima karena p dan 4 juga relatif prima. karena p prima dan tidak membagi habis a maupun 4 maka sekaligus p tidak membagi 4a maka 4a dan p relatif prima.)
Karena 4(a^2)(x^2)+4abx+4ac = {(2ax)^2+4abx+b^2} - b^2 + 4ac
= (2ax+b)^2 - (b^2-4ac), maka berarti :
ax^2+bx+c=0(mod p) jika dan hanya jika (2ax+b)^2 - (b^2-4ac)=0(mod p) jika dan hanya jika (2ax+b)^2 = (b^2-4ac) (mod p).
Sehingga jika ada bilangan bulat yang memenuhi kongruensi ax^2+bx+c=0(mod p) maka
b^2-4ac adalah residu kuadratik dari p atau kalau tidak maka b^2-4ac=0(mod p).

Sebaliknya , andaikan b^2-4ac residu kuadratik dari p atau b^2-4ac=0(mod p). Maka ada bilangan bulat y sedemikian hingga y^2=b^2-4ac (mod p).
2a dengan p juga relatif prima sehingga kita bisa melihat ada bilangan bulat d dan f yang membuat 2ad+pf=1 atau 2ad=1 (mod p). Jika kita ambil x=d(y-b) (mod p) maka
2ax+b (mod p)=2a(d(y-b))+b) (mod p)=(2ady - 2adb +2ab) (mod p)
= 2ady (mod p) = y(mod p) .
Dan dari sini (2ax+b)^2=(b^2-4ac) (mod p). Yang berarti lalu ax^2+bx+c=0(mod p).