Korkeamman asteen kongruensseista

Abstract

Luvun a sanotaan olevan kongruentti luvun b kanssa modulo m, jos luku m jakaa erotuksen a-b. Tällöin merkitään a ≡ b (mod m). Polynomikongruenssilla tarkoitetaan kongruenssia, joka on muotoa f(x) ≡ 0 (mod m), missä f(x) on polynomifunktio. Polynomikongruenssit saadaan ratkaistua käyttämällä kiinalaista jäännöslausetta silloin, kun modulo m voidaan jakaa pareittain suhteellisiksi alkuluvuiksi.

Kun polynomikongruenssin modulo m on alkuluku, voidaan ratkaisua etsiä testaamalla lukuja täydellisestä jäännössysteemistä modulo m tai käyttää nostoperiaatetta. Nostoperiaatteella tarkoitetaan menetelmää, jonka mukaan etsitään ensin kongruenssin f(x) ≡ 0 (mod p) ratkaisu. Tämän jälkeen oletetaan, että tunnetaan ratkaisut kongruenssiin f(x) ≡ 0 (mod p^k), jonka jälkeen etsitään ratkaisut kongruenssiin f(x) ≡ 0 (mod p^{k+1}).

Toisen asteen kongruenssin ax^2 + bx + c ≡ 0 (mod p) ratkaisut saadaan kongruenssin 2ax ≡ -b + y (mod p) ratkaisusta, missä y on kongruenssiin y^2 ≡ b^2 - 4ac (mod p) ratkaisu. Polynomikongruenssilla, jonka aste on n, on korkeintaan n ratkaisua.

Olkoon p alkuluku. Kongruenssin y^2 ≡ a (mod p) ratkaisua a sanotaan neliönjäännökseksi modulo p. Jos ratkaisua ei löydy, niin lukua a sanotaan neliönepäjäännökseksi modulo p. Jokainen supistettu jäännössysteemi modulo p sisältää (p - 1)/2 neliönjäännöstä sekä yhtä monta neliönepäjäännöstä modulo p. Legendren symbolin (a/p) arvo on 1, jos a on neliönjäännös modulo p, ja -1, jos a on neliönepäjäännös modulo p.

Legendren symbolin arvon määrittämiseksi on olemassa useita keinoja. Eulerin kriteerin mukaan (a/p) ≡ a^{(p-1)/2} (mod p). Gaussin lemman nojalla Legendren symbolin arvo on (a/p) = (-1)^s, kun s on joukon {a, 2a, . . . , ((p -1)/2)a} niiden alkioiden lukumäärä, joiden jakojäännös modulo p on suurempi kuin p/2. Neliönjäännösten resiprookkilain mukaan (p/q)(q/p) =(-1)^{((p-1)/2 )((q-1)/2 )}