Voor een oneven priemgetal p is het Legendre symbool (a/p) gedefinieerd als: 0 als a=0, 1 als a een kwadraat is mod p, -1 als a geen kwadraat is mod p. Dus, voor p=5: (0/5) = 0, (1/5)=(4/5)=1, (2/5)=(3/5)=-1. En voor p=7: (0/7) = 0. (1/7)=(2/7)=(4/7)=1, (3/7)=(5/7)=(6/7)=-1.
Er geldt (a/p) = a^((p-1)/2) (mod p). Kennelijk is (ab/p) = (a/p)(b/p).
Om (a/p) uit te rekenen volstaat het dus om (-1/p) en (2/p) en (q/p) te kennen, voor alle priemgetallen q kleiner dan p.
Er geldt (-1/p)=1 als p=1 (mod 4) en (-1/p)=-1 als p=3 (mod 4).
Er geldt (2/p)=1 als p=1,7 (mod 8) en (2/p)=-1 als p=3,5 (mod 8).
Er geldt (p/q)(q/p) = (-1)^((p-1)/2)((q-1)/2), met andere woorden:
(p/q) = (q/p) tenzij p en q beide 3 (mod 4) zijn.
Voorbeeld:
Is 20 een kwadraat modulo 43?
Wel, 20=2.2.5 en (5/43)=(43/5)=(3/5)=(5/3)=(2/3)=-1, dus het
antwoord luidt nee.
Is 21 dan een kwadraat modulo 43?
Wel, (21/43)=(3/43)(7/43)=-(43/3).-(43/7)=(1/3)(1/7)=1, dus
21 is inderdaad een kwadraat. Voor welke x is dan x^2=21 (mod 43)?
Voor x=8 en x=35.
Voor oneven m is het Jacobisymbool (a/m) per definitie gelijk aan het product van (a/p_i) als m het product van de p_i is. Dus (a/45)=(a/3)(a/3)(a/5). Dit symbool kan uitgerekend worden met bovenstaande regels voor het Legendresymbool, zonder de factorisatie van m te kennen. Maar als m niet priem is dan is de kans dat (a/m) = a^((m-1)/2) (mod m) kleiner dan 1/2, dus na een aantal a's geprobeerd te hebben krijg je, als deze gelijkheid steeds geldt, er vertrouwen in dat m wel priem zal zijn. Zo'n m heet een "waarschijnlijk priem"-getal. Kijk bijvoorbeeld naar 1001. (23/1001)=(1001/23)=(12/23)=(3/23)=-(23/3)=-(2/3)=1. En 23^500=529 (mod 1001). Dus is 1001 niet priem, en het blijkt al bij de eerste test.