Ugrás a tartalomhoz

Új matematikai mozaik

Ambrus Gergely, Bárszi Gergely, Csikós Balázs, Frenkel Péter, Gács András, Gyárfás András, Hraskó András, Kiss Emil, Laczkovich Miklós, Lovász László, Montágh Balázs, Moussong Gábor, Pach János, Pelikán József, Recski András, Reiman István

Typotex

2. Számolás maradékokkal

2. Számolás maradékokkal

A továbbiakban szükségünk lesz a számelmélet néhány alapfogalmára. Először a moduláris összeadás és szorzás, a moduláris inverz, majd a moduláris négyzetgyökvonás fogalmával és néhány alaptulajdonságával ismerkedünk meg. Közben szükségünk lesz a kínai maradéktétel egy speciális esetére is. E fejezetet átugorhatja a számelmélet elemi alapfogalmaiban járatos olvasó. A számelmélettel való ismerkedéshez Sárközi András művét [5] valamint Szalay Mihálynak a Speciális Matematika Tankönyvek sorozatban megjelent könyvét [8] ajánljuk. További tanulmányokhoz Freud Róbert és Gyarmati Edit egyetemi tankönyve javasolható [2], de az érdeklődő több érdekes és olvasásra érdemes számelméleti témájú könyvet talál az elmúlt évtizedekben magyarul megjelent könyvek között.

2.1. Moduláris összeadás és szorzás

Ismeretes, hogy a maradékos osztás egész számok között egyértelműen elvégezhető, azaz, ha a és m egész számok és m //>// 0 , akkor egyetlen olyan q és r egész létezik, hogy a = m q + r és 0 ? r //<// m . Az r számot az a szám m -mel való osztási maradékának nevezzük. Azt is szokás mondani a fenti r maradékra, hogy az „ a maradéka modulo m ”. E maradékra az a mod m jelölést használjuk. Itt tehát mod egy kétváltozós művelet jele. Példaként legyen a = 17 és m = 5 . Ekkor 17 = 5 · 3 + 2 , tehát q = 3 és r = 2 , azaz 17 mod 5 = 2 .

Ha a és b az m -mel osztva azonos maradékot ad, akkor azt mondjuk, hogy a kongruens b -vel modulo m , és ezt úgy jelöljük, hogy a ? b ( mod m ) . Például 11 ? 47 ( mod 9 ) , mert 9-cel osztva 11, és 47 is 2-t ad maradékul. Ne keverjük össze a két „mod” jelölést: a ? b ( mod m ) azzal ekvivalens, hogy a mod m = b mod m . Az előbbi példánkban 11 mod 9 = 2 és 47 mod 9 = 2 , tehát valóban 11 ? 47 ( mod 9 ) .

Könnyen látható, hogy a ? b ( mod m ) pontosan akkor teljesül, ha m osztója b - a -nak. E tulajdonság felhasználásával igazolható, hogy ha a ? b ( mod m ) és c ? d ( mod m ) , akkor a + c ? b + d ( mod m ) , a - c ? b - d ( mod m ) és a c ? b d ( mod m ) . Például a ? 1 ( mod 2 ) , b ? 0 ( mod 2 ) esetén a + b ? 1 ( mod 2 ) és a b ? 0 ( mod 2 ) , ami egyébként azzal ekvivalens, hogy egy páros és egy páratlan szám összege páratlan, míg szorzata páros.

Az előzőekből azonnal adódik, hogy ha egy egészekből álló kifejezésben csak az összeadás, kivonás és szorzás művelete szerepel, akkor e kifejezés értékének modulo m vett maradéka nem fog megváltozni, ha benne bármelyik számot kicseréljük egy vele modulo m kongruens számmal. Például ( - 5 + 12 ) ( - 6 + 10 ) ? ( 4 - 6 ) ( 12 - 8 ) ( mod 9 ) , mivel - 5 ? 4 ( mod 9 ) , 12 ? - 6 ( mod 9 ) és 10 ? - 8 ( mod 9 ) . Ez vezet a maradékosztályokkal való számolás, más néven a moduláris aritmetika fogalmához.

Az egész számok osztályokba sorolhatók úgy, hogy egy osztályba kerüljenek azok a számok, amelyek egy rögzített pozitív egész m számmal osztva azonos maradékot adnak. Jelölje [ k ] m vagy egyszerűen csak [ k ] azt az osztályt, melynek minden eleme k maradékot ad. Például modulo 3 a következő három maradékosztály létezik: [ 0 ] 3 = { , - 3 , 0 , 3 , 6 , } , [ 1 ] 3 = { , - 2 , 1 , 4 , 7 , } , [ 2 ] 3 = { , - 1 , 2 , 5 , 8 , } . Miután az, hogy a fenti három művelettel elvégzett számolás eredménye melyik osztályba esik csak attól függ, hogy mely osztályba eső számmal számoltunk, természetes módon definiálhatjuk a maradékosztályok közti műveleteteket. [ a ] m + [ b ] m = [ c ] m , illetve [ a ] m [ b ] m = [ d ] m , ha egy [ a ] m és egy [ b ] m osztályból vett szám összege a [ c ] m , illetve szorzata a [ d ] m osztályba esik. Például [ 2 ] 3 + [ 1 ] 3 = [ 0 ] 3 és [ 2 ] 3 [ 1 ] 3 = [ 2 ] 3 , mert például 4 + 2 = 6 és 4 · 2 = 8 . Azt a struktúrát, amit a modulo m maradékosztályok a köztük definiált fenti műveletekkel alkotnak Z m -mel jelöljük. Például Z 3 elemei { [ 0 ] 3 , [ 1 ] 3 , [ 2 ] 3 } , míg az elemek közt definiált két művelet táblája:

+ [ 0 ] 3 [ 1 ] 3 [ 2 ] 3 [ 0 ] 3 [ 0 ] 3 [ 1 ] 3 [ 2 ] 3 [ 1 ] 3 [ 1 ] 3 [ 2 ] 3 [ 0 ] 3 [ 2 ] 3 [ 2 ] 3 [ 0 ] 3 [ 1 ] 3 × [ 0 ] 3 [ 1 ] 3 [ 2 ] 3 [ 0 ] 3 [ 0 ] 3 [ 0 ] 3 [ 0 ] 3 [ 1 ] 3 [ 0 ] 3 [ 1 ] 3 [ 2 ] 3 [ 2 ] 3 [ 0 ] 3 [ 2 ] 3 [ 1 ] 3

Könnyen látható, hogy ha a és m relatív prímek, azaz a és m legnagyobb közös osztója 1, akkor [ a ] m minden eleme relatív prím m -hez. Ha két modulo m maradékosztály ilyen tulajdonságú, akkor a szorzatuk is.

Az olyan maradékosztályoknak, melyek elemei relatív prímek m -hez, a szorzás műveletével alkotott struktúráját Z m * -gal jelöljük. Például Z 12 * elemei: [ 1 ] 12 , [ 5 ] 12 , [ 7 ] 12 , [ 11 ] 12 ; művelettáblája:

× [ 1 ] 12 [ 5 ] 12 [ 7 ] 12 [ 11 ] 12 [ 1 ] 12 [ 1 ] 12 [ 5 ] 12 [ 7 ] 12 [ 11 ] 12 [ 5 ] 12 [ 5 ] 12 [ 1 ] 12 [ 11 ] 12 [ 7 ] 12 [ 7 ] 12 [ 7 ] 12 [ 11 ] 12 [ 1 ] 12 [ 5 ] 12 [ 11 ] 12 [ 11 ] 12 [ 7 ] 12 [ 5 ] 12 [ 1 ] 12

A továbbiakban az egyszerűség kedvéért Z m és Z m * elemeit a szögletes zárójeleket elhagyva, a maradékosztályból választott valamely reprezentánssal fogjuk jelölni. E reprezentánsokat leggyakrabban a { 0 , 1 , , m - 1 } halmazból választjuk. Tehát e megállapodás után Z 12 * elemeinek halmaza { 1 , 5 , 7 , 11 } , ha pedig m prím, akkor Z m * elemeinek halmaza { 1 , 2 , , m - 1 } . A - 1 mint Z m egy eleme, ugyanazt jelöli, mint m - 1 . Ha m = 1 , akkor Z m -nek csak egy eleme van, Z m * pedig nem is létezik, ezért a továbbiakban feltesszük, hogy m //>// 1 .

2.2. Moduláris inverz

Könnyen megmutatható, hogy Z m * elemeit beszorozva egy a ? Z m * elemmel, Z m * elemeinek egy permutációját kapjuk, amit másként úgy is kifejezhetünk, hogy az a · x = b egyenlet minden a , b ? Z m * esetén egyértelműen megoldható (az a és x közti szorzásjel a Z m * -beli művelet jelöli!). Speciálisan b = 1 esetén azt kapjuk, hogy minden a ? Z m * maradékosztályhoz található egyetlen olyan a ¯ ? Z m * maradékosztály, melyre a · a ¯ = 1 . Ezt a maradékosztályt nevezzük az a maradékosztály inverzének. Az a ? Z egész moduláris inverzén az a -val reprezentált maradékosztály a ¯ inverzének 0 és m közé eső reprezentánsát értjük, és erre az elemre az a - 1 mod m jelölést használjuk.

A moduláris inverz létezése a kongruenciák nyelvén így fogalmazható meg: az a x ? 1 ( mod m ) kongruencia minden m //>// 1 egész és minden m -hez relatív prím a ? Z esetén egyértelműen megoldható, azaz egyetlen olyan a ' ? Z , 0 //<// a ' //<// m egész létezik, hogy a fenti kongruenciát kielégítő x számok pontosan azok, melyek eleget tesznek az x ? a ' ( mod m ) kongruenciának.

Lássunk két példát: Z 7 * -ban 1 ¯ = 1 , 2 ¯ = 4 , 3 ¯ = 5 és 6 ¯ = 6 , míg a fenti művelettáblán könnyen ellenőrizhető, hogy Z 12 * minden eleme saját maga moduláris inverze, azaz a ? Z 12 * esetén a - 1 mod 12 = a .

Kérdés, hogy miként számítható ki minél gyorsabban a moduláris inverz. A következőkben az euklideszi algoritmus egy erre a feladatra kihegyezett változatát fogjuk ismertetni. Kezdjük egy egyszerű példával. Számítsuk ki 5 - 1 mod 13 értékét! A részeredményeket egy kétoszlopos táblázatban fogjuk feljegyezni, melynek első sorában m és 0, míg második sorában a és 1 áll:

m 0 a 1 , azaz esetünkben 13 0 5 1

Ezután a táblázat további sorait rekurzív módon a megelőző kettőből a következő egyszerű képlettel fogjuk kiszámítani: [12]

y 1 x 1 y 2 x 2 y 1 - ? y 1 y 2 ? y 2 x 1 - ? y 1 y 2 ? x 2

Ezt az eljárást addig ismételjük, amíg a bal oldalon 1-et nem kapunk. Ekkor a jobb oldalon a inverze fog állni, egészen pontosan az inverz maradékosztály egy eleme. Az m = 13 , a = 5 értékekkel számolva a következő táblázatot kapjuk (a második oszlop mellett zárójelben megadjuk a részletszámításhoz használt ? y 1 y 2 ? értékeket is):

13 0 5 1 ( ? 13 5 ? = 2 ) 3 - 2 ( ? 5 3 ? = 1 ) 2 3 ( ? 3 2 ? = 1 ) 1 - 5

Azt kaptuk tehát, hogy az 5-tel reprezentált Z 13 -beli mellékosztály inverze a - 5 -tel reprezentált maradékosztály, de mivel - 5 ? 8 ( mod 13 ) , ezért ez megegyezik a 8 ? Z 13 mellékosztállyal. Összefoglalva tehát: 5 - 1 mod 13 = 8 .

Annak bebizonyításához, hogy ha m és a relatív prímek ( m //>// a ), akkor a fenti eljárással megkapjuk a - 1 mod m értékét, két állítást kell igazolni:

  1. A bal oldali oszlopban véges sok lépésen belül eljutunk az 1-eshez.

  2. A táblázat mindegyik sorának bal oszlopában álló y és jobb oszlopában álló x számok teljesítik az a x ? y ( mod m ) feltételt, így az utolsó sorban álló x számra a x ? 1 ( mod m ) .

Az első állítás bizonyításához elég megmutatni, hogy az egymás után következő számok mindig relatív prímek, továbbá hogy szigorúan monoton csökkenő sorozatot alkotnak. A második állítás nyilvánvalóan igaz a táblázat első két sorára, a továbbiakra pedig a kongruenciák korábban említett tulajdonságaiból levezethető. A bizonyítások kidolgozását az olvasóra bízzuk.

Még meglehetősen nagy számok esetén is gyorsan számolható a moduláris inverz. A következő feladat számítógép használata nélkül is gyorsan megoldható.

2. feladat. Határozzuk meg 242 424 242 - 1 mod 12 121 212 121 értékét! (A két adott szám relatív prím, mivel 12 121 212 121 prím.)

2.3. Kínai maradéktétel

A kínai maradéktétel lineáris kongruenciarendszerek megoldhatóságáról szól. Nekünk csak egy speciális esetére lesz szükségünk. Legyen p és q két különböző prím, és a , b ? Z tetszőleges egészek. Ekkor az

x ? a ( mod p ) x ? b ( mod q )

kongruenciarendszer megoldható, és a megoldás egyértelmű modulo p q . A megoldás egyszerűen meg is konstruálható. Jelölje p ¯ q a p inverzét mod q , míg q ¯ p a q inverzét mod p , azaz legyenek igazak a q q ¯ p ? 1 ( mod p ) és p p ¯ q ? 1 ( mod q ) kongruenciák. Nagyon könnyű ellenőrizni, hogy ekkor az x = a q q ¯ p + b p p ¯ q megoldása a fenti kongruenciarendszernek. Az egyértelműség bizonyításához csak azt kell megmutatni, hogy bármely két megoldás különbsége osztható p q -val. Ezek igazolását az olvasóra bízzuk.

3. feladat. Oldjuk meg az

x ? 2 ( mod 7 ) x ? 3 ( mod 11 )

és az

x ? - 2 ( mod 7 ) x ? - 3 ( mod 11 )

kongruenciarendszereket!

2.4. Moduláris hatványozás és négyzetgyökvonás

Egy szám moduláris négyzetreemelése nem jelent újat, hisz ez csak egy moduláris szorzás. Segítségével a moduláris hatványozás is gyorsan elvégezhető. A módszer lényege, hogy a részletszámításokat is modulárisan végezzük, így mindig kisebb számokkal kell számolnunk, másrészt ismételt négyzetreemelésekkel kiszámítjuk az alap kettőhatvány-kitevőjű hatványait, amelyek közül a megfelelőek összeszorzásával megkapjuk az eredményt. További magyarázat helyett csak egy egyszerű példát mutatunk.

Számítsuk ki 9 22 ( mod 79 ) értékét számológép használata nélkül! Először ismételt négyzetreemelésekkel kiszámítjuk 9 kettőhatvány-kitevőjű hatványait: 9 2 = 81 ? 2 ( mod 79 ) , 9 4 = ( 9 2 ) 2 ? 2 2 ? 4 ( mod 79 ) , 9 8 = ( 9 4 ) 2 ? 4 2 ? 16 ( mod 79 ) , 9 16 = ( 9 8 ) 2 ? 16 2 = 256 ? 19 ( mod 79 ) . Ezután a kitevőt, azaz 22-t felbontjuk kettőhatványok összegére (ez a kitevő kettes számrendszerbeli alakjának felírásával ekvivalens feladat): 22 = 16 + 4 + 2 (a 22 kettes számrendszerbeli alakja 10110). Így 9 22 = 9 16 · 9 4 · 9 2 ? 19 · 4 · 2 ? 73 ( mod 79 ) , tehát 9 22 ? 73 ( mod 79 ) .

A négyzetgyökvonás elvégzése általában már korántsem ilyen egyszerű feladat. Mielőtt ennek vizsgálatára térnénk, felelevenítünk egy definíciót és két fontos számelméleti alaptételt:

Legyen n pozitív egész, és legyen ( a , n ) = 1 . Azt mondjuk, hogy az a szám négyzetelem modulo n , ha van olyan x egész, hogy x 2 ? a ( mod n ) .

  • kis Fermat-tétel: Ha p prím és a nem osztható p -vel, akkor

    a p - 1 ? 1 ( mod p ) .

  • Euler-feltétel: Ha p //>// 2 prím és a nem osztható p -vel, akkor az x 2 ? a ( mod p ) kongruencia pontosan akkor oldható meg – azaz a pontosan akkor négyzetelem modulo p –, ha

    a p - 1 2 1 ( mod p ) ,

    és ekkor a fenti kongruenciának modulo p két különböző megoldása van. Ha az egyik megoldás x 0 , akkor a másik - x 0 (ha a gyökök 0 és p közé eső reprezentánsait keressük, tehát 0 //<// x 0 //<// p , akkor a másik megoldás reprezentánsa p - x 0 ).

Az utóbbi tétel felhasználásával könnyen bizonyítható, hogy abban az esetben, ha p 4 k + 3 alakú prím és a négyzetelem, akkor a két négyzetgyöke

± a p + 1 4 ,

ugyanis ( ± a p + 1 4 ) 2 = a p + 1 2 = a p - 1 2 a ? a ( mod p ) .

4. feladat. Határozzuk meg 2 és 5 négyzetgyökeit modulo 31.

Ha a modulus nem prím, de két 4 k + 3 alakú prím szorzata, akkor e prímtényezők ismeretében könnyen kiszámítható bármely négyzetelem négyzetgyöke. A két 4 k + 3 alakú prím szorzataként előálló egészeket Blum-egészeknek nevezik.

Legyen n = p q , ahol p és q két különböző prím, és tegyük fel, hogy az x 2 ? a ( mod n ) ( 0 //<// a //<// n ) kongruenciának x 0 egy megoldása. Először megmutatjuk, hogy e kongruenciának modulo n négy különböző megoldása, azaz a -nak négy különböző négyzetgyöke van, ha a és n relatív prímek. Legyen x p , illetve x q az a két egész szám, melyekre x p ? x 0 ( mod p ) és 0 //<// x p //<// p , illetve x q ? x 0 ( mod q ) és 0 //<// x q //<// q . Minthogy x 2 ? a ( mod n ) megoldható, ezért x 2 ? a ( mod p ) is, és a két gyöke x p és - x p . Hasonlóképpen x 2 ? a ( mod q ) két gyöke x q és - x q . A kínai maradéktételből következik, hogy az x 2 ? a ( mod n ) ( ( a , n ) = 1 ) kongruenciának pontosan négy megoldása van, melyeket a következő négy kongruenciarendszer megoldásából kaphatunk meg:

x ? x p ( mod p ) x ? x q ( mod q ) (1) x ? x p ( mod p ) x ? - x q ( mod q ) (2) x ? - x p ( mod p ) x ? x q ( mod q ) (3) x ? - x p ( mod p ) x ? - x q ( mod q ) (4)

Könnyen bizonyítható, hogy a négy különböző gyök közül kiválasztható kettő úgy – jelölje ezeket x 1 és x 2 –, hogy a négy négyzetgyök kongruens legyen az alábbi négy számmal modulo n : x 1 , x 2 , - x 1 , - x 2 .

Az előbbiekben feltételeztük, hogy már ismerjük az x 2 ? a ( mod n ) kongruencia egy megoldását. Ez általában persze nincs így, ha azonban n Blum-egész, azaz p ? q ? 3 ( mod 4 ) , akkor az x 2 ? a ( mod p ) , illetve az x 2 ? a ( mod q ) kongruenciákat x 0 ismerete nélkül is meg tudjuk oldani, így az (1)(4) kongruenciarendszerek az alábbi alakba írhatóak:

x ? ± a p + 1 4 ( mod p ) x ? ± a q + 1 4 ( mod q )

(5)

5. feladat. Határozzuk meg 53-nak modulo 77 vett négyzetgyökeit!

2.5. A prímtényezős felbontás és a gyökvonás

A titkosítás tudományának mai módszerei közül igen sok egyrészt arra a sejtésre épül, hogy egy egész szám prímtényezőkre bontása igen számításigényes feladat, másrészt arra a tényre, hogy vannak olyan számítási feladatok, melyek a prímtényezők ismeretében igen gyorsan elvégezhetők, a prímtényezők ismerete nélkül viszont csak legalább olyan nagy munkával, mint maga a prímtényezőkre bontás. Például ha valaki csak annyit tud egy számról, hogy az két 200-jegyű prím szorzata, akkor ismereteink és a számítástechnika mai fejlettsége mellett prímtényezőkre bontásához sok évtizednyi gépidőre lenne szükség a leggyorsabb mai gépeken is. Tetszőleges, n -hez relatív prím egész szám négy négyzetgyökének meghatározása a korábban megismert algoritmussal a másodperc tört része alatt elvégezhető még egy egyszerű PC-n is, ugyanakkor a prímtényezők ismerete nélkül is gyorsan lefutó algoritmus nem ismeretes. Az, hogy ilyen algoritmus nem létezik, nincs bizonyítva, azt azonban magunk is ellenőrizhetjük, hogy ha volna, akkor lenne a prímtényezős felbontásra is gyors algoritmus.

Tegyük fel tehát, hogy „gyorsan” ki tudjuk számolni egy n -nel relatív prím a szám modulo n vett négy négyzetgyökét. Jelölje a négy gyököt x 1 , x 2 , - x 1 és - x 2 , ahol 0 //<// x 1 //<// x 2 //<// n . Mivel x 1 2 ? x 2 2 ( mod n ) , azaz x 2 2 - x 1 2 ? 0 ( mod n ) , de x 1 ? ± x 2 ( mod n ) , ezért ( x 2 - x 1 , n ) valódi osztója n -nek. A legnagyobb közös osztó a prímtényezők ismerete nélkül is gyorsan számolható az euklideszi algoritmussal, ezért n „gyorsan” faktorizálható.

Vajon mi történik, ha csak olyan algoritmust ismerünk, mely egy szám négyzetgyökei közül csak egyet (illetve annak ellentettjével együtt kettőt) képes meghatározni? Vajon ekkor meg tudjuk határozni n prímtényezős felbontását? Erre az esetre nagyon egyszerű véletlen algoritmus van. Erről szól a következő feladat.

6. feladat. Legyen n = p q , és tegyük fel, hogy ismerünk egy olyan f eljárást, mely tetszőleges a ? Z n * elemhez megadja ennek egy f ( a ) négyzetgyökét. Konstruáljunk olyan véletlen algoritmust, mely 1-hez tetszőlegesen közeli valószínűséggel meghatározza valamely a szám összes gyökét, s ezzel lehetővé teszi n gyors tényezőkre bontását!

Megemlítünk egy másik problémát is, mely a prímtényezők ismeretében könnyen megoldható, ellenkező esetben azonban nem ismeretes gyors algoritmus az eldöntésére. Ez az ún. négyzetes maradék probléma, mely a következőképpen szól. Tegyük fel, hogy n = p q két prím szorzata, és jelölje Q azon m ? Z n * egészek halmazát, melyekre az x 2 ? m ( mod p ) és a x 2 ? m ( mod q ) kongruenciák közül vagy mindkettő megoldható, vagy egyik sem! Másként fogalmazva az m vagy a Z p -ben és a Z q -ban is négyzetelem, vagy egyikben sem. Talán meglepő, de az, hogy m eleme-e Q -nak, vagy nem, könnyen és igen gyorsan eldönthető akkor is, ha nem ismerjük p és q értékét[13]. Ezek után a kérdés az, hogy egy m ? Q elemről hogyan dönthető el, hogy négyzetelem-e Z n -ben? Tudjuk, hogy m ? Q pontosan akkor négyzetelem Z n -ben, ha négyzetelem Z p -ben és a Z q -ban is, azaz ha mindkét kongruencia megoldható. Prím modulus esetén az Euler-feltétellel könnyen eldönthető, hogy egy szám négyzetelem-e vagy sem, így ha ismerjük n prímtényezőit, a kérdést gyorsan meg tudjuk válaszolni. Nem ismeretes olyan módszer azonban, melynek segítségével ez a kérdés a prímtényezők ismerete nélkül is gyorsan megválaszolható volna.

Minthogy az m ? Q számokról nehéz eldönteni, hogy négyzetelemek-e vagy sem, ezért az m ? Q elemet álnégyzetnek, vagy álnégyzetelemnek nevezzük, ha nem négyzetelem.

7. feladat. Döntsük el, hogy 19 négyzetelem, álnégyzetelem vagy egyik sem modulo 77. Számítógépet használva soroljuk fel Z 77 * elemei közül az összes négyzetelemet és az összes álnégyzetelemet.



[12] Az ? x ? az x valós szám egész részét jelöli, azaz azt a legnagyobb egészt, mely nem nagyobb x -nél. Például ? 4 3 ? = 1 , ? - ? ? = - 4 . Ha m //>// 0 és a egészek, akkor a maradékos osztás szerinti a = m q + r ( 0 ? r //<// m ) összefüggésben szereplő q és r kifejezhető e függvény segítségével: q = ? a m ? , r = a - ? a m ? m .

[13] E téma részletesebb taglalására e cikk keretei között nincs módunk, csak annyit jegyzünk meg, hogy ha az m n -nel jelölt ún. Jacobi-szimbólum értéke 1, akkor m ? Q , ha - 1 , akkor m ? Q . Definíció szerint m n = m p m q , ahol m p értéke 1 vagy - 1 aszerint, hogy m négyzetelem vagy nem modulo p . Bár a definícióban szerepelnek n prímtényezői, a Jacobi-szimbólum kiszámításához nincs szükség ismeretükre.