Kínai maradéktétel

A kínai maradéktétel a több kongruenciából álló szimultán kongruenciarendszerek megoldhatóságára ad választ. Már több mint 2000 évvel ezelőtt ismerte egy kínai matematikus, Szun Cu; innen a tétel mai neve.

A tétel tulajdonképpen a következő feladatra ad választ (továbbá kimondja, hogy a megoldás egyértelmű maradékosztály): keressük azt az egész számot (maradékosztályt), ami bizonyos számokkal osztva, amelyek páronként relatív prímek, meghatározott maradékot ad.

A következőkben a tétel formális kimondása és bizonyítása található.

Tétel

Legyenek ${\displaystyle m_{1},m_{2},\dots ,m_{k}>0}$ páronként relatív prímek, ${\displaystyle c_{1},c_{2},\dots ,c_{k}}$ pedig tetszőleges egészek. Ekkor az

kongruencia-rendszer megoldható, és a megoldás egyetlen maradékosztály lesz ${\displaystyle \mod {M}}$, ahol ${\displaystyle M=m_{1}\cdot m_{2}\dots m_{k}}$.

Bizonyítás

A megoldás egyértelműsége

Tegyük fel, hogy ${\displaystyle \ x_{1}}$ és ${\displaystyle \ x_{2}}$ is megoldások. Ekkor minden ${\displaystyle i=0,1,\dots ,k}$ esetén ${\displaystyle m_{i}\mid x_{1}-x_{2}\Rightarrow M\mid x_{1}-x_{2}}$ (mivel ${\displaystyle \ m_{i}}$-k relatív prímek), amiből a kongruenciák definíciója alapján következik, hogy ${\displaystyle x_{1}\equiv x_{2}{\pmod {M}}}$. Tehát ${\displaystyle \ x_{1}}$ és ${\displaystyle \ x_{2}}$ (azaz bármely két megoldás) ugyanabba a maradékosztályba tartoznak ${\displaystyle \mod {M}}$, így csak egy megoldó maradékosztálya van a kongruencia-rendszernek.

A megoldás létezése

Legyen ${\displaystyle M=m_{1}\cdot m_{2}\dots m_{k}}$ és ${\displaystyle M_{i}={\frac {M}{m_{i}}}}$. Legyen ${\displaystyle z_{i}\in \mathbb {Z} }$ olyan, hogy ${\displaystyle M_{i}z_{i}\equiv 1{\pmod {m_{i}}}}$. A megoldások számára vonatkozó tétel alapján ilyen${\displaystyle \ z_{i}}$ létezik, mert ${\displaystyle \ (M_{i},m_{i})=1}$. Az ${\displaystyle s=M_{1}z_{1}c_{1}+M_{2}z_{2}c_{2}+\dots +M_{k}z_{k}c_{k}}$ jó megoldás lesz. Ennek bizonyításához nézzük meg, hogy ${\displaystyle s\equiv c_{i}{\pmod {m_{i}}}}$ valóban teljesül-e (${\displaystyle i=0,1,\dots ,k}$). A kongruencia ekvivalens ${\displaystyle s\equiv M_{i}z_{i}c_{i}{\pmod {m_{i}}}}$ kongruenciával, mert ${\displaystyle \ m_{i}\mid M_{j}}$, ha ${\displaystyle i\neq j}$. Mivel ${\displaystyle M_{i}z_{i}\equiv 1{\pmod {m_{i}}}}$, ezért ${\displaystyle s\equiv c_{i}{\pmod {m_{i}}}}$ áll fenn, ami épp a bizonyítandó állítás.

Alkalmazásai

A kínai maradéktételt meglepő módon rengeteg helyen lehet használni, sok problémánál pedig nem is kapható meg nélküle az eredmény.

Polinom helyettesítési értéke

Tegyük fel, hogy ki szeretnénk számolni egy ${\displaystyle f(x_{1},x_{2},\dots ,x_{n})}$ egész együtthatós többváltozós polinom helyettesítési értékét adott ${\displaystyle (x_{1},x_{2},\dots ,x_{n})=(a_{1},a_{2},\dots ,a_{n})}$ helyen, és ismerjük, hogy ${\displaystyle |f(a_{1},a_{2},\dots ,a_{n})|<{\frac {M}{2}}}$ teljesül. Ekkor válasszunk olyan ${\displaystyle m_{1},m_{2},\dots ,m_{k}}$ egymáshoz relatív prím egészeket (praktikusan prímszámokat szokás) a kínai maradéktételhez, amelyekre: ${\displaystyle m_{1}m_{2}\dots m_{k}<M}$ teljesül, majd számoljuk ki a polinom helyettesítési értékeit minden ${\displaystyle i}$-re ${\displaystyle {\pmod {m_{i}}}}$, legyen az eredmény ${\displaystyle c_{i}}$, majd a kínai maradéktételt használva azt az egyértelmű ${\displaystyle x}$ egész számot, amelyre ${\displaystyle -{\frac {M}{2}}\leq x<{\frac {M}{2}}}$ és

teljesül. Ekkor ${\displaystyle f(a_{1},a_{2},\dots ,a_{n})=x}$ lesz.

Így nagy számokkal való műveleteket nem kell végezni, csak amikor az eljárás elején redukáljuk a polinom együtthatóit ${\displaystyle {\pmod {m_{i}}}}$, illetve a végén, amikor megoldjuk a kongruenciarendszert. Ezáltal lényegesen kevesebb memóriát használva ki tudjuk számítani a végeredményt.

Rejtjelezés

Az RSA legtöbb implementációja a kínai maradéktételt használja a HTTPS hitelesítésre és a visszafejtésre.

A tétel használható a titokmegosztásra, amivel úgy lehet titkot megosztani, hogy csak néhányan közösen tudjanak hozzáférni. Az érzékeny adat egy kongruenciarendszer megoldása, amiből minden résztvevő egy egyenletet ismer. Van arra is algoritmus, hogy megkonstruálja a modulusokat, hogy a kívánt számnál kevesebb ember együtt ne férhessen hozzá a titokhoz.

Hermite-interpoláció

Az általános Hermite-interpoláció: Adva vannak a ${\displaystyle \lambda _{1},\dots ,\lambda _{r}}$ komplex pontok, és hozzájuk rendre az ${\displaystyle a_{j,k}:\ 1\leq j\leq r,\ 0\leq k<\nu _{j}}$ értékek. Keressünk egy ${\displaystyle P(x)\in \mathbb {C} [x]}$ polinomot úgy, hogy:

${\displaystyle P^{(k)}(\lambda _{j})=a_{j,k}\qquad 1\leq j\leq r,\quad 0\leq k<\nu _{j}.}$

A megoldás: Vezessük be az

${\displaystyle A_{j}(x):=\sum _{k=0}^{\nu _{j}-1}{\frac {a_{j,k}}{k!}}(x-\lambda _{j})^{k}}$

polinomokat, így a rendszer szimultán kongruenciákra írható át:

${\displaystyle P(x)\equiv A_{j}(x){\pmod {(x-\lambda _{j})^{\nu _{j}}}},\qquad 1\leq j\leq r}$

A kínai maradéktétel szerint ${\displaystyle \mathbb {C} [x]}$-ben van egy egyértelmű ${\displaystyle P(x)}$ polinom, hogy:

${\displaystyle \deg(P)<n:=\sum _{j}\nu _{j}.}$

A közvetlen konstrukció így valósítható meg: Definiáljuk a

${\displaystyle {\begin{aligned}Q&=\prod _{i=1}^{r}(x-\lambda _{i})^{\nu _{i}}\\Q_{j}&={\frac {Q}{(x-\lambda _{j})^{\nu _{j}}}}\end{aligned}}}$

polinomokat. Ekkor ${\displaystyle {\frac {1}{Q}}}$ törtfelbontása ${\displaystyle r}$ polinomot ad, a továbbiakban ezeket ${\displaystyle S_{j}}$ jelöli, és fokszámuk ${\displaystyle \deg(S_{j})<\nu _{j}}$. Ezzel

${\displaystyle {\frac {1}{Q}}=\sum _{i=1}^{r}{\frac {S_{i}}{(x-\lambda _{i})^{\nu _{i}}}}}$

így

${\displaystyle 1=\sum _{i=1}^{r}S_{i}Q_{i}.}$

Tehát a kongruenciarendszer megoldása

${\displaystyle \sum _{i=1}^{r}A_{i}S_{i}Q_{i}=A_{j}+\sum _{i=1}^{r}(A_{i}-A_{j})S_{i}Q_{i}\equiv A_{j}{\pmod {(x-\lambda _{j})^{\nu _{j}}}}\qquad 1\leq j\leq r,}$

ami az egyértelmű ${\displaystyle n}$-nél kisebb fokú polinom.

Dedekind-tétel

Dedekind tétele a lineárisan független karakterekről: Legyen ${\displaystyle M}$ monoid, ${\displaystyle k}$ integritási tartomány, amit szintén monoidnak tekintünk a rajta vett szorzással. Ekkor minden véges ${\displaystyle (f_{i})_{i\in I}}$ egyenként különböző monoidhomomorfia független, ahol minden ${\displaystyle f_{i}:\ M\rightarrow k}$. Más szavakkal, ${\displaystyle (\alpha _{i}){}_{i\in I}}$ elemek minden családja, ahol ${\displaystyle \alpha _{i}\in k}$ és ${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}$, ugyanaz, mint ${\displaystyle (0){}_{i\in I}}$.

Bizonyítás: Először is tegyük fel, hogy ${\displaystyle k}$ test; ha nem az, helyettesítsük hányadostestével, és semmi sem változik. Lineárisan kiterjesztjük az ${\displaystyle f_{i}:\ M\rightarrow k}$ homomorfiákat ${\displaystyle k}$-algebra homomorfiákká, ahol ${\displaystyle k[M]}$ ${\displaystyle M}$ monoid gyűrűje ${\displaystyle k}$ fölött. Ekkor a linearitás miatt a

${\displaystyle \sum _{i\in I}\alpha _{i}f_{i}=0}$

feltételből következik

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0.}$

Állítjuk, hogy az ${\displaystyle i,j\in I;\ i\neq j}$ indexekre ${\displaystyle F_{i}:\ k[M]\rightarrow k}$ és ${\displaystyle F_{j}:\ k[M]\rightarrow k}$ nem arányosak egymáshoz. Különben ${\displaystyle f_{i}}$ és ${\displaystyle f_{j}}$ is arányos lenne, így monoid homomorfiaként egyenlőek lennének, emiatt ${\displaystyle f_{i}(1)=1=f_{j}}$, ami ellentmond annak, hogy különböznek.

Ezért a ${\displaystyle \operatorname {Ker} F_{i}}$ és ${\displaystyle \operatorname {Ker} F_{j}}$ magok különböznek. Mivel ${\displaystyle k[M]/\operatorname {Ker} F_{i}\cong F_{i}(k[M])=k}$ test, ${\displaystyle \operatorname {Ker} F_{i}}$ maximális ideálja ${\displaystyle k[M]}$-nek, minden ${\displaystyle i\in I}$ indexre. Mivel ezek különbözők és maximálisak, ezért relatív prímek egymáshoz. A kínai maradéktétel a következő izomorfiát adja:

${\displaystyle {\begin{aligned}\phi :k[M]/K&\to \prod _{i\in I}k[M]/\operatorname {Ker} F_{i}\\\phi (x+K)&=\left(x+\operatorname {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

ahol

${\displaystyle K=\prod _{i\in I}\operatorname {Ker} F_{i}=\bigcap _{i\in I}\operatorname {Ker} F_{i}.}$

Következik, hogy a

${\displaystyle {\begin{aligned}\Phi :k[M]&\to \prod _{i\in I}k[M]/\operatorname {Ker} F_{i}\\\Phi (x)&=\left(x+\operatorname {Ker} F_{i}\right)_{i\in I}\end{aligned}}}$

leképezés szürjektív. A ${\displaystyle k[M]/\operatorname {Ker} F_{i}\rightarrow F_{i}(k[M])=k}$, izomorfiákkal a ${\displaystyle \Phi }$ leképezés megfelel ennek:

${\displaystyle {\begin{aligned}\psi :k[M]&\to \prod _{i\in I}k\\\psi (x)&=\left[F_{i}(x)\right]_{i\in I}\end{aligned}}}$

Most abból, hogy

${\displaystyle \sum _{i\in I}\alpha _{i}F_{i}=0}$

kapjuk, hogy:

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

minden ${\displaystyle (u_{i}){}_{i\in I}}$ vektorra a ${\displaystyle \psi }$ leképezés szerinti képben. Mivel ${\displaystyle \psi }$ szürjektív, ez azt jelenti, hogy

${\displaystyle \sum _{i\in I}\alpha _{i}u_{i}=0}$

minden

${\displaystyle \left(u_{i}\right){}_{i\in I}\in \prod _{i\in I}k}$

vektorra. Tehát ${\displaystyle (\alpha _{i}){}_{i\in I}=(0){}_{i\in I}}$.

Más alkalmazások

Egész elemű mátrixok determinánsának kiszámolása klasszikus példa az alkalmazására, illetve a gyors szorzás FFT módszerénél is gyakran felbukkan, ott a számítógép felépítése miatt ${\displaystyle 2}$ hatványhoz közeli prímeket célszerű választani a módszer gyorsításához. Az algoritmus a tétel alapján újraindexeli az adatokat. Gödel nemteljességi tételéhez a sorozatok számozását is elegánsan lehet megoldani a kínai maradéktétellel.

A módszer kiterjeszthető arra az esetre is, amikor osztani is kell egy feladatban. Ekkor persze problémák adódhatnak, hiszen előfordulhat, hogy ${\displaystyle 0}$-val osztani is kell (legyen most ${\displaystyle m_{i}}$ prím), ha az adott szám osztható ${\displaystyle m_{i}}$-vel, ez pedig ${\displaystyle {\pmod {m_{i}}}}$ nem elvégezhető művelet. Ilyenkor dobjuk el az ${\displaystyle m_{i}}$ prímet és válasszunk helyette egy másikat. Így például már egész elemű lineáris egyenletrendszerek is megoldhatóak a kínai maradéktétellel, kevés memóriával (illetve felszorzás miatt racionális elemű lineáris egyenletrendszerek is).

A radarral végzett felméréseknél a tartományfelosztás egyértelműsítésére is használják.

A megoldás menete

Mivel minden ${\displaystyle i}$-re az ${\displaystyle m_{i}}$ számok és ${\displaystyle M_{i}:=M/m_{i}}$ relatív prímek, azért a kiterjesztett euklideszi algoritmussal találhatók ${\displaystyle r_{i}}$ és ${\displaystyle s_{i}}$ számok, hogy

${\displaystyle r_{i}\cdot m_{i}+s_{i}\cdot M_{i}=1}$.

Végezzük el az ${\displaystyle e_{i}:=s_{i}\cdot M_{i}}$ helyettesítést, ezzel

${\displaystyle {\begin{aligned}e_{i}&\equiv 1{\pmod {m_{i}}}\\e_{j}&\equiv 0{\pmod {m_{j}}},\ j\neq i.\end{aligned}}}$.

Ekkor

${\displaystyle x:=\sum _{i=1}^{n}a_{i}e_{i}}$

a szimultán kongruencia egy megoldása.

Példa

Keresünk egy ${\displaystyle x}$ egész számot, amire teljesülnek a következők:

${\displaystyle {\begin{aligned}x&\equiv 2{\pmod {3}}\\x&\equiv 3{\pmod {4}}\\x&\equiv 2{\pmod {5}}\\\end{aligned}}}$

Itt ${\displaystyle M=3\cdot 4\cdot 5=60,\ M_{1}=M/3=20,\ M_{2}=M/4=15,\ M_{3}=M/5=12}$. A kibővített euklideszi algoritmussal kiszámítható, hogy

${\displaystyle 7\cdot 3+(-1)\cdot 20=1}$, tehát ${\displaystyle e_{1}=-20}$

${\displaystyle 4\cdot 4+(-1)\cdot 15=1}$, tehát ${\displaystyle e_{2}=-15}$

${\displaystyle 5\cdot 5+(-2)\cdot 12=1}$, tehát ${\displaystyle e_{3}=-24}$

Eszerint ${\displaystyle x=2\cdot (-20)+3\cdot (-15)+2\cdot (-24)=-133}$ az egyenletrendszer egy megoldása. Mivel ${\displaystyle -133\equiv 47\mod 60}$, azért az összes megoldás kongruens 47-tel modulo 60.

Általános eset

Általános esetben nem tesszük fel, hogy a modulusok relatív prímek. Néha még így is létezik megoldás, de a modulusok szorzata helyett a legkisebb közös többszöröst kell venni. A létezés feltétele: Minden ${\displaystyle i\neq j}$ párra

${\displaystyle a_{i}\equiv a_{j}{\pmod {\operatorname {lnko} (m_{i},m_{j})}}}$.^[1]

Ekkor a szimultán kongruencia szukcesszív helyettesítéssel oldható meg.

Például egy klasszikus feladat megkeresni azt a legkisebb pozitív egész számot, ami a 2, 3, 4, 5 és 6 számokkal osztva egyet ad maradékul, de osztható héttel. Tehát keressük ennek az egyenletrendszernek a megoldását:

${\displaystyle {\begin{aligned}x&\equiv 1\mod 2\\x&\equiv 1\mod 3\\x&\equiv 1\mod 4\\x&\equiv 1\mod 5\\x&\equiv 1\mod 6\\x&\equiv 0\mod 7\\\end{aligned}}}$

Mivel a modulusok nem relatív prímek, azért nem alkalmazható közvetlenül a kínai maradéktétel. Az első öt feltételt összefoglalhatjuk a következőbe:

${\displaystyle x\equiv 1\mod \operatorname {lkkt} (2,3,4,5,6)}$

így az egyenletrendszer a következő alakra hozható:

${\displaystyle {\begin{aligned}x&\equiv 1\mod 60\\x&\equiv 0\mod 7\\\end{aligned}}}$

amire már alkalmazható a kínai maradéktétel. A megoldások kongruensek 301-gyel modulo 420. Ezek közül a legkisebb pozitív egész a 301.

Közvetlen megoldás

Adva legyen a következő két kongruenciából álló rendszer:

${\displaystyle {\begin{aligned}x&\equiv a{\pmod {n}}\\x&\equiv b{\pmod {m}}\\\end{aligned}}}$

Ha ezek megoldhatók, akkor ${\displaystyle a\equiv b{\pmod {d}}}$, ezért ekvivalensek az

${\displaystyle x\equiv a-yn{\frac {a-b}{d}}{\pmod {\frac {nm}{d}}}}$

kongruenciával, ahol

${\displaystyle d=\operatorname {lnko} (n,m)=yn+zm}$.

Ez akkor is működik, ha ${\displaystyle n}$ és ${\displaystyle m}$ nem relatív prímek, így nagyban megkönnyíti a szimultán kongruenciák megoldását.

Ha több kongruencia tartozik a rendszerhez, akkor többször kell alkalmazni az egyszerűsítést.

Főideálgyűrűkben

Ha ${\displaystyle R}$ főideálgyűrű, akkor a tétel a következő formát ölti:

Ha az ${\displaystyle m_{1},\ldots ,m_{n}}$ elemek páronként relatív prímek, és szorzatuk ${\displaystyle m}$, akkor az ${\displaystyle R/mR}$ hányadosgyűrű izomorf az ${\displaystyle R/m_{1}R\times \cdots \times R/m_{n}R}$ szorzatgyűrűvel, mégpedig az alábbi izomorfia van köztük:

${\displaystyle {\begin{matrix}f:&R/mR&\to &R/m_{1}R\times \cdots \times R/m_{n}R\\&x+mR&\mapsto &(x+m_{1}R,\ldots ,x+m_{n}R)\end{matrix}}}$

Egységelemes gyűrűkben

Ha ${\displaystyle R}$ egységelemes gyűrű, akkor a következők tudhatók: Ha ${\displaystyle I_{1},\ldots ,I_{n}}$ ideálok, és ${\displaystyle I_{i}+I_{j}=R}$ minden ${\displaystyle i\neq j}$ indexre, és az ideálok metszete ${\displaystyle I}$, akkor az ${\displaystyle R/I}$ gyűrű izomorf az ${\displaystyle R/I_{1}\times \cdots \times R/I_{n}}$ szorzatgyűrűvel, mégpedig ezzel az izomorfiával:

${\displaystyle {\begin{matrix}f:&R/I&\to &R/I_{1}\times \cdots \times R/I_{n}\\&x+I&\mapsto &(x+I_{1},\ldots ,x+I_{n}).\end{matrix}}}$

Ha ${\displaystyle R}$ még kommutatív is, akkor ${\displaystyle I}$ az ${\displaystyle I_{j}}$ ideálok szorzata. Ehhez a kommutatív tulajdonság szükséges, mivel erre ellenpélda is adható nem kommutatív esetben.

Vesszük a nem kommutatív polinomok gyűrűjét (például mátrixok fölött) ${\displaystyle x}$ és ${\displaystyle y}$ határozatlanokkal, és tekintjük ezeket az ideálokat: ${\displaystyle I}$ az ${\displaystyle x}$ által generált principiális ideál és ${\displaystyle J}$ az ${\displaystyle xy+1}$ által generált principiális ideál. Ekkor ${\displaystyle I+J=R}$, de ${\displaystyle I\cap J\neq IJ}$.

Az ${\displaystyle I}$ ideál azokból a polinomokból áll, amelyek minden monomjában tényezőként szerepel ${\displaystyle x}$. A ${\displaystyle J}$ polinomjai eltűnnek, ha ${\displaystyle y=-1/x}$. Ekkor ${\displaystyle p=(xy+1)x\in I\cap J}$. Definiáljuk ${\displaystyle R}$ termjeit úgy, mint ${\displaystyle R}$ ${\displaystyle x}$ és ${\displaystyle y}$ által generált multiplikatív monoidjának elemét, és foka a szokásos fok az ${\displaystyle y=x}$ helyettesítés után.

Másrészt legyen egy ${\displaystyle q\in J}$. Ekkor ${\displaystyle q}$ minden maximális fokú egytagja függ ${\displaystyle y}$-tól, különben az ${\displaystyle y=-1/x}$ helyettesítés nem tüntetné el a polinomot. Hasonlóak igazak, ha ${\displaystyle q\in IJ}$. Vegyük észre, hogy a legmagasabb fokú egytagokban a legutolsó ${\displaystyle y}$-os tényezőt legalább egy ${\displaystyle x}$ megelőzi. Például az ${\displaystyle x^{2}yxyx^{5}}$ polinomban az utolsó ${\displaystyle y}$-t három ${\displaystyle x}$ előzi meg. Eszerint ${\displaystyle p=(xy+1)x\notin IJ}$, mivel benne az utolsó ${\displaystyle y}$-t csak egy ${\displaystyle x}$ előzi meg. Tehát ${\displaystyle I\cap J\neq IJ}$.

Ezzel szemben ${\displaystyle I+J=R}$ általánosan implikálja, hogy ${\displaystyle I\cap J=IJ+JI}$. Ehhez elég belátni, hogy ${\displaystyle I\cap J=(I\cap J)(I+J)\subset IJ+JI}$, mivel a másik irány triviális. Ha ${\displaystyle I_{1},\dots ,I_{m}}$ páronként relatív prímek, akkor az

${\displaystyle R/(I_{1}\cap \cdots \cap I_{m})\to R/I_{1}\oplus \cdots \oplus R/I_{m}}$

természetes leképezés izomorfia.

Jegyzetek

Fordítás

• Ez a szócikk részben vagy egészben a Chinesischer Restsatz című német Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
• Ez a szócikk részben vagy egészben a Chinese remainder theorem című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

• Alice és Bob - 22. rész: Alice, Bob és a kínaiak

Források

• Freud Róbert – Gyarmati Edit: Számelmélet. Budapest: Nemzeti Tankönyvkiadó. 2000. ISBN 963-19-0784-8  
• Joseph W. Dauben: Chapter 3: Chinese Mathematics. In Victor J. Katz: The Mathematics of Egypt, Mesopotamia, China, India and Islam: A Sourcebook. Princeton: Princeton University Press. 2007. 187–384. o. ISBN 978-0-691-11485-9  
• Pierre Duchet: Hypergraphs. In Ronald L. Graham – Martin Grötschel – Lovász László: Handbook of Combinatorics, 1–2. kötet. Amszterdam: Elsevier. 1995. 381–432. o. ISBN 978-0-444-82346-5 Lásd különösen a 2.5. fejezetet (Helly property, 393–394. o.), MathSciNet  
• Carl Friedrich Gauss: Disquisitiones Arithemeticae. Angolra ford. Arthur A. Clarke. 2., jav. kiad. New York: Springer. 1986. ISBN 978-0-387-96254-2 Hozzáférés: 2017. december 22.  
• Kenneth Ireland – Michael Rosen: A Classical Introduction to Modern Number Theory. 2. kiad. New York: Springer. 1990. ISBN 0-387-97329-X  
• Subhash Kak: Computational aspects of the Āryabhaṭa algorithm. Indian Journal of History of Science, XXI. évf. 1. sz. (1986) 62–71. o. Hozzáférés: 2017. december 22.
• Victor J. Katz: A History of Mathematics: An Introduction. 2. kiad. (hely nélkül): Addison-Wesley. 1998. ISBN 978-0-321-01618-8  
• Oystein Ore: Number Theory and Its History. Reprint kiad. New York: Dover. 1988. ISBN 978-0-486-65620-5 Eredeti kiadás: 1948  
• Kenneth H. Rosen: Elementary Number Theory and its Applications. 3. kiad. (hely nélkül): Addison-Wesley. 1993. ISBN 978-0-201-57889-8