Kongruencia

A kongruencia a számelméletben az oszthatósági kérdéseket, a maradékokkal való számolást radikálisan leegyszerűsítő jelölésmód.

A kongruencia egy reláció, amelyet az egész számok halmazán értelmezünk. Egy ilyen reláció kifejezi, hogy két szám adott számmal vett osztási maradéka egyenlő-e. Ezen relációkon és azok között végezhetünk műveleteket (összeadás, kivonás, szorzás, osztás, hatványozás – elvégzésükhöz különböző feltételeknek kell teljesülni, ezeket lásd lejjebb). Azonban ennél komolyabb dolgokra is használatos, amire példa a maradékosztályok vagy Chevalley tétele.

Ha két egész szám nem kongruens, akkor inkongruensnek nevezik őket.

Definíció

Legyen ${\displaystyle a,b}$ tetszőleges egész szám, ${\displaystyle m}$ zérótól különböző természetes szám.

Azt mondjuk, hogy a kongruens b-vel modulo m, azaz hogy a és b egészek m-mel vett osztási maradéka egyenlő, ha

${\displaystyle m\mid a-b}$

azaz

${\displaystyle \exists k\in \mathbb {Z} :a=km+b}$

Jelölése: ${\displaystyle a\equiv b{\pmod {m}}}$ vagy ${\displaystyle a\equiv b\quad (m)}$.

Lehet találkozni a következő jelölésekkel is:

• ${\displaystyle a\equiv b\mod m}$
• ${\displaystyle a\equiv b\mod m\mathbb {Z} }$
• ${\displaystyle a\equiv _{m}b}$

Ha a nem kongruens b-vel modulo m, azt mondjuk, inkongruens vele, és ${\displaystyle a\not \equiv b{\pmod {m}}}$ vagy ${\displaystyle a\not \equiv b\quad (m)}$ alakban jelöljük.

Az itt szereplő ${\displaystyle \operatorname {mod} }$ a matematikai maradékképző függvény, ami a maradékos osztás maradékát rendeli a számhoz.

Példák

Az 5 kongruens 11-gyel modulo 3, mert ${\displaystyle 5:3=1{\text{ maradék }}2}$, és ${\displaystyle 11:3=3{\text{ maradék }}2}$. A két maradék megegyezik, mivel ${\displaystyle 11-5=6=2\cdot 3}$.

Az 5 inkongruens 11-gyel modulo 4, mivel ${\displaystyle 5:4=1{\text{ maradéka }}1}$ és ${\displaystyle 11:4=2{\text{ maradék }}3}$; a maradékok nem egyeznek.

A −8 kongruens 10-zel modulo 6, hiszen a 6-tal vett osztási maradék mindkét esetben 4. Valóban, ${\displaystyle -8=(-2)\cdot 6+4}$.

Története

A kongruenciák ma is használatos elméletét 1801-ben Carl Friedrich Gauss dolgozta ki Disquisitiones Arithmeticae című művében. Magát a fogalmat már Christian Goldbach 1730-ban Leonhard Euler-nek írt levelében is használta, azonban korántsem olyan mélységben, mint Gauss. Goldbach a ${\displaystyle \equiv }$ szimbólum helyett a ${\displaystyle \mp }$ jelet használta.^[1]

Sőt, már Ch'in Chiu-Shao kínai matematikus is ismerte a fogalmat, amivel kapcsolatos elméletét az 1247-ben írt Matematikai értekezés kilenc fejezetben című művében le is írt. Ebben szerepelt a kínai maradéktétel egy formája is.^[2]

Elemi tulajdonságai

A kongruencia ekvivalenciareláció, azaz reflexív, szimmetrikus és tranzitív: tetszőleges ${\displaystyle a,b,c\in \mathbb {Z} }$, valamint ${\displaystyle m\in \mathbb {Z} ^{+}}$ esetén

• ${\displaystyle a\equiv a{\pmod {m}}}$
• ${\displaystyle a\equiv b{\pmod {m}}\Rightarrow b\equiv a{\pmod {m}}}$
• ${\displaystyle a\equiv b{\pmod {m}},\ b\equiv c{\pmod {m}}\Rightarrow a\equiv c{\pmod {m}}}$

Az ekvivalenciaosztályokat maradékosztályoknak nevezzük. Az elnevezés arra utal, hogy megfeleltethetőek az m-mel való osztás lehetséges maradékainak.

Bővebben: Maradékosztály

A kongruenciára kimondható számos, az egyenlőségre érvényes azonosság megfelelője: kongruens számok összege és szorzata is kongruens. Legyen ${\displaystyle a,b,c,d\in \mathbb {Z} }$ és ${\displaystyle m,n\in \mathbb {Z} ^{+}}$. Ekkor

• ${\displaystyle a\equiv b{\pmod {m}},\ c\equiv d{\pmod {m}}\Rightarrow a+c\equiv b+d{\pmod {m}}}$
• ${\displaystyle a\equiv b{\pmod {m}},\ c\equiv d{\pmod {m}}\Rightarrow a-c\equiv b-d{\pmod {m}}}$
• ${\displaystyle a\equiv b{\pmod {m}},\ c\equiv d{\pmod {m}}\Rightarrow ac\equiv bd{\pmod {m}}}$

Az egyenlőség a kongruencia speciális esetének is tekinthető:

${\displaystyle a\equiv b{\pmod {0}}\Rightarrow a=b}$.

Ha ${\displaystyle f\in \mathbb {Z} [X]}$ polinom az egész számok fölött, akkor

${\displaystyle f(a)\equiv f(a'){\pmod {m}}}$

Kongruencia osztása egész számmal

Az osztásnál már nem olyan egyszerű a helyzet, mint az egyenleteknél, ugyanis ha a szám amivel osztani szeretnénk nem relatív prím a modulussal, akkor a modulust is osztani kell.
Legyen ${\displaystyle \ d=(c,m)}$ a c és m egészek legnagyobb közös osztója. Ekkor ${\displaystyle ac\equiv bc{\pmod {m}}\Leftrightarrow a\equiv b{\pmod {\frac {m}{d}}}}$.
Megjegyzés: a tétel következménye, hogy ${\displaystyle ac\equiv bc{\pmod {m}},(c,m)=1\Rightarrow a\equiv b{\pmod {m}}}$.

Ez azt is jelenti, hogy, ha ${\displaystyle d}$ osztója ${\displaystyle m}$-nek, akkor ${\displaystyle a\equiv b{\pmod {m}}}$ esetén ${\displaystyle a\equiv b{\pmod {d}}}$.

Ennek az állításnak megnézzük a bizonyítását is, a többi állításé is hasonlóan történik.

Definíció alapján: ${\displaystyle ac\equiv bc{\pmod {m}}\Leftrightarrow m\mid (a-b)c}$, ami ekvivalens a ${\displaystyle {\frac {m}{d}}\mid (a-b){\frac {c}{d}}}$ oszthatósággal.
Mivel ${\displaystyle \left({\frac {m}{d}},{\frac {c}{d}}\right)=1}$, ezért a fenti oszthatóság pontosan akkor teljesül, ha ${\displaystyle {\frac {m}{d}}\mid a-b}$, ami a kongruencia definíciója alapján épp az állítás.

Fontos megemlítenünk a következő két tételt, ugyanis a kongruenciákkal kapcsolatban nagyon gyakran felmerülnek, és nagy segítséget nyújtanak bizonyos feladatok, tételek megoldásában.

Euler–Fermat-tétel

Bővebben: Euler–Fermat-tétel

A tétel a moduláris számelmélet egyik legfontosabb állítása, nagyon sok komolyabb tétel bizonyításánál felhasználható, és ami által azok bizonyítása is lényegesen leegyszerűsödik.
A tétel állítása:

${\displaystyle a,m\in \mathbb {Z} ,m>1,(a,m)=1\Rightarrow a^{\varphi (m)}\equiv 1{\pmod {m}}}$

A kis Fermat-tétel

Bővebben: kis Fermat-tétel

A tétel az Euler-Fermat-tétel egy speciális esete, mely időben korábban fogalmazódott meg, és a bizonyítása egy évszázaddal megelőzte az általános esetet. Itt a modulus prím, ekkor a ${\displaystyle \varphi (p)=p-1}$ miatt a következő állítást kapjuk:

Ha ${\displaystyle a}$ egész szám, ${\displaystyle p}$ olyan prím, ami nem osztja ${\displaystyle a}$-t, akkor ${\displaystyle a^{p-1}\equiv 1{\pmod {p}}}$.

A tétel egy másik, gyakori alakja:

Ha ${\displaystyle a}$ egész szám, ${\displaystyle p}$ prím, akkor ${\displaystyle a^{p}\equiv a{\pmod {p}}}$.

Kínai maradéktétel

A kínai maradéktétel szerint: Ha ${\displaystyle m_{1},m_{2},\dotsc ,m_{k}}$ nullától különböző egész számok, és ${\displaystyle m}$ a legkisebb közös többszörösük, akkor:

${\displaystyle a\equiv a'{\pmod {m_{\kappa }}}}$ minden ${\displaystyle \kappa =1,2,\dotsc ,k\quad \Leftrightarrow \quad a\equiv a'{\pmod {m}}}$

Hatványozás

Ha ${\displaystyle n\in \mathbb {N} _{0}}$ természetes szám, akkor

${\displaystyle a^{n}\equiv (a')^{n}{\pmod {m}}}$

Relatív prím ${\displaystyle a}$ és ${\displaystyle m}$ esetén teljesül az Euler-tétel:

${\displaystyle a^{\varphi (m)}\equiv 1{\pmod {m}}}$,

ahol ${\displaystyle \varphi (m)}$ az Euler-féle φ-függvény. Ebből következik ${\displaystyle a^{n}\equiv a^{n'}{\pmod {m}}}$, hogyha ${\displaystyle n\equiv n'{\pmod {\varphi (m)}}}$. Ennek speciális esete a kis Fermat-tétel.

Példák

• Ha ${\displaystyle t\neq 0}$, akkor ${\displaystyle t\cdot a\equiv t\cdot b{\pmod {|t|\cdot m}}}$.
• Ha ${\displaystyle a}$ páratlan, akkor ${\displaystyle a^{2}\equiv 1{\pmod {8}}}$.
• Minden egész számra teljesül a következők valamelyike:

${\displaystyle a^{3}\equiv 0{\pmod {9}}}$ vagy ${\displaystyle a^{3}\equiv 1{\pmod {9}}}$ vagy ${\displaystyle a^{3}\equiv 8{\pmod {9}}}$.

• Ha ${\displaystyle a}$, akkor ${\displaystyle a^{3}\equiv a{\pmod {6}}}$.
• Minden egész számra teljesül a következők valamelyike:

${\displaystyle a^{3}\equiv 0{\pmod {7}}}$ vagy ${\displaystyle a^{3}\equiv 1{\pmod {7}}}$ vagy ${\displaystyle a^{3}\equiv 6{\pmod {7}}}$.

• Minden egész számra teljesül a következők valamelyike:

${\displaystyle a^{4}\equiv 0{\pmod {5}}}$ vagy ${\displaystyle a^{4}\equiv 1{\pmod {5}}}$.

• Hogyha ${\displaystyle a}$ teljes hatodik hatvány, azaz négyzet- és köbszám is, akkor ${\displaystyle a\equiv 0{\pmod {36}}}$ vagy ${\displaystyle a\equiv 1{\pmod {36}}}$ vagy ${\displaystyle a\equiv 9{\pmod {36}}}$ vagy ${\displaystyle a\equiv 28{\pmod {36}}}$.
• Legyen ${\displaystyle p}$ prímszám úgy, hogy ${\displaystyle n<p<2n}$. Ekkor ${\displaystyle {2n \choose n}\equiv 0{\pmod {p}}}$.
• Legyen ${\displaystyle a}$ páratlan, ${\displaystyle n>0}$ pozitív egész szám. Ekkor ${\displaystyle a^{2^{n}}\equiv 1{\pmod {2^{n+2}}}}$.
• Legyen ${\displaystyle p>3}$, illetve ${\displaystyle p}$ és ${\displaystyle q=p+2}$ ikerprímek. Ekkor ${\displaystyle p\cdot q\equiv -1{\pmod {9}}}$.

A kongruenciaosztályok gyűrűje

A modulo n nullával kongruens számok az egész számok egy ideálját alkotják, az ${\displaystyle n\mathbb {Z} }$ a más számokkal kongruensek pedig ennek mellékosztályait. Így definiálhatjuk a ${\displaystyle \mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z} }$ faktorcsoportot, amelynek elemei az ${\displaystyle {\overline {a}}_{n}=\left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}}$ maradékosztályok. (Néha az ${\displaystyle [a]}$ jelölést is használják.) A faktorcsoport a ${\displaystyle {\overline {0}}_{n},{\overline {1}}_{n},{\overline {2}}_{n},\ldots ,{\overline {n-1}}_{n}}$ elemekből áll, műveletei egyszerűen visszavezethetőek az egész számok műveleteire:

• ${\displaystyle {\overline {a}}_{n}+{\overline {b}}_{n}={\overline {a+b}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}-{\overline {b}}_{n}={\overline {a-b}}_{n}}$
• ${\displaystyle {\overline {a}}_{n}{\overline {b}}_{n}={\overline {ab}}_{n}}$

${\displaystyle \mathbb {Z} _{n}}$ ezekkel a műveletekkel egy kommutatív gyűrű; ha n prím, akkor (és csak akkor) test.

Algebra

Bővebben: Magasabb fokú kongruenciák

Azt mondjuk, hogy n szám teljes maradékrendszert alkot modulo m, ha páronként inkongruensek, és n=m. A teljes maradékrendszer teljes marad, ha minden eleméhez hozzáadjuk ugyanazt az egész számot, vagy minden elemét megszorozzuk egy, az m modulushoz relatív prím tényezővel.

Egy maradékosztály redukált maradékosztály, ha reprezentánsai relatív prímek a modulushoz. Ha minden redukált maradékosztályt egy szám reprezentál, akkor a reprezentánsok redukált maradékrendszert alkotnak. Számuk éppen az m modulusnál kisebb, m-hez relatív prímek száma (Euler-féle ${\displaystyle \varphi }$ függvény).

Adott m modulus esetén a redukált maradékrendszer maradékosztályai csoportot alkotnak a szorzásra, de az összeadásra nem. Például, ha m kettőhatvány, akkor a redukált maradékrendszer éppen a páratlan maradékosztályokból fog állni. A modulo m összes maradékosztály csoportot alkot az összeadásra, de a szorzásra általában nem; a maradékosztályok gyűrűje nem nullosztómentes. Például modulo 6 a 2 és a 3 maradékosztályának szorzata a 6 maradékosztálya, ami éppen a 0 maradékosztály. Ez prím modulusra nem fordulhat elő; prím modulussal nincsenek nullosztók, és minden nem nulla maradékosztálynak van inverze. Ha a modulus prím, akkor a maradékosztályok testet alkotnak.

Rend

Bővebben: multiplikatív rend

Legyen ${\displaystyle \ (a,m)=1}$. A legkisebb olyan ${\displaystyle k\in \mathbb {Z} ^{+}}$ számot, melyre ${\displaystyle a^{k}\equiv 1{\pmod {m}}}$, az a (multiplikatív) rendjének nevezzük modulo m.
Jelölése: ${\displaystyle \ o_{m}(a)}$.

Megjegyzés: Az Euler${\displaystyle -}$Fermat-tételből következik, hogy minden ${\displaystyle \ (a,m)=1}$ esetén létezik az a-nak rendje és ${\displaystyle o_{m}(a)\leq \varphi (m)}$. Ha ${\displaystyle (a,m)\neq 1}$, akkor a-nak nem létezik ilyen szám.

Primitív gyök

Egy g számot primitív gyöknek nevezünk modulo m, ha ${\displaystyle o_{m}(g)=\varphi (m)}$, azaz ha a g rendje a nála kisebb, m-hez relatív prímek száma (Euler-féle ${\displaystyle \varphi }$ függvény).

Primitív gyök létezik, ha a modulus prím, kettőhatvány, prímnégyzet, vagy egy prímszám kétszerese.

Index (diszkrét logaritmus)

Legyen p prím, g primitív gyök modulo p és ${\displaystyle (a,p)=1}$. Ekkor az a-nak a g alapú indexén azt a ${\displaystyle 0\leq k\leq p-2}$ számot értjük, melyre ${\displaystyle a\equiv g^{k}{\pmod {p}}}$.
Jelölés: ${\displaystyle \ ind_{g,p}(a)}$ (Ha a g primitív gyök vagy a p prím egyértelmű adott feladatnál, akkor a jelölésből elhagyható.)

Lineáris kongruenciák

Bővebben: lineáris kongruenciák

${\displaystyle ax\equiv b{\pmod {m}}\qquad a,b\in \mathbb {Z} ,m\in \mathbb {Z} ^{+}}$

Ezen kongruenciák megoldásakor azokat az egészeket keressük, ami egy bizonyos számmal (modulus) osztva meghatározott maradékot ad. Ezek a diofantoszi egyenletek megfelelői, mindössze más alakban írjuk fel. A megoldásokat maradékosztályokként keressük, és a megoldásszámon a megoldó maradékosztályok számát értjük. Ez a lineáris kongruencia akkor oldható meg, ha ${\displaystyle g=\operatorname {lnko} (a,m)}$ a ${\displaystyle b}$ számnak is osztója. Ekkor ${\displaystyle g}$-vel lehet egyszerűsíteni, és modulo ${\displaystyle {\tfrac {m}{g}}}$ megoldani a kongruenciát. Visszahelyettesítve a megoldást az eredeti kongruenciába, ${\displaystyle g}$ megoldást találunk.

A megoldást kibővített euklideszi algoritmussal megtalálhatjuk, ahonnan kapjuk az ${\displaystyle s}$, ${\displaystyle t}$ egészeket úgy, hogy:

${\displaystyle g=\operatorname {lnko} (a,m)=s\cdot a+t\cdot m}$

Innen egy megoldás kapható, mint:

${\displaystyle \textstyle x_{1}={\frac {s\cdot c}{g}}}$,

a többi pedig ettől ${\displaystyle {\tfrac {m}{g}}}$-szeresben különbözik.

Például ${\displaystyle 4x\equiv 10{\pmod {18}}}$ megoldható, hiszen ${\displaystyle \operatorname {lnko} (4,18)=2}$ osztója a ${\displaystyle 10}$-nek is, és a megoldásszám ${\displaystyle 2}$. A kibővített euklideszi algoritmus eredménye ${\displaystyle 2=-4\cdot 4+1\cdot 18}$, amiből adódik az ${\displaystyle \textstyle x_{1}={\frac {-4\cdot 10}{2}}=-20}$ megoldás. A megoldások egy maradékosztályt alkotnak modulo ${\displaystyle \textstyle {\frac {18}{2}}=9}$, így a megoldáshalmaz ${\displaystyle \{\cdots ,-20,-11,-2,7,16,25,\cdots \}}$.

Magasabb fokú kongruenciák

Bővebben: Magasabb fokú kongruenciák

Legyen m>0 adott, ${\displaystyle f(x)=a_{0}+a_{1}x+\dots a_{k}x^{k}}$ egész együtthatós polinom. Ekkor tekinthetjük az ${\displaystyle f(x)\equiv 0{\pmod {m}}}$ egyismeretlenes kongruenciát, melynek megoldásait modulo m keressük, azaz azon maradékosztályokat, amelyek kielégítik a kongruenciát.

Ezen kongruenciákat hasonlíthatjuk a magasabb fokú egyenletekhez. Ezek megoldása bizonyos esetekben nagyon leegyszerűsíthető, de nincsenek megoldóképletek, csak algoritmusok, amelyek elvezetnek a kívánt eredményhez.

Szimultán kongruenciák

Egy

${\displaystyle \qquad a_{1}x\equiv c_{1}{\pmod {m_{1}}}}$

${\displaystyle \qquad a_{2}x\equiv c_{2}{\pmod {m_{2}}}}$

${\displaystyle \qquad a_{3}x\equiv c_{3}{\pmod {m_{3}}}}$

alakú szimultán kongruencia megoldható, ha:

• minden ${\displaystyle i}$-re ${\displaystyle c_{i}}$ osztható ${\displaystyle g_{i}=\operatorname {lnko} (a_{i},m_{i})}$-vel, azaz minden kongruencia egyenként megoldható,
• és minden ${\displaystyle {\tfrac {m_{i}}{g_{i}}}}$ relatív prím.

A kínai maradéktétel bizonyítása megoldási módszert ad a szimultán kongruenciákra.

Kapcsolat a modulo függvénnyel

Ha ${\displaystyle a,b,m\in \mathbb {Z} }$, ${\displaystyle m\neq 0}$, akkor:

${\displaystyle a\equiv b{\pmod {m}}\quad \Leftrightarrow \quad (a{\bmod {m}})=(b{\bmod {m}})\quad \Leftrightarrow \quad (a-b){\bmod {m}}=0}$

Programozáskor ügyelni kell arra, hogy több programozási nyelv a matematikaitól eltérően definiálja a maradékot negatív számokra. A szimmetrikus maradékképzés helyett az

${\displaystyle (a{\bmod {m}}):=a-\left\lfloor {\frac {a}{m}}\right\rfloor \cdot m}$

matematikai modulo függvényt kell alkalmazni, melynek előjele ${\displaystyle m}$ előjelétől függ. Ezzel a definícióval ${\displaystyle (-1){\bmod {7}}=6}$, és az azonos maradékosztályba tartozó számok ugyanazt a maradékot adják ugyanarra a modulusra.

Alkalmazások

A következőkben a kongruenciák néhány alkalmazása következik.

• A nehezebb (nagyon nagy számok, hatványok) maradékos osztások kongruenciává alakítása során könnyebb kiszámolni az eredményt (az ismert tételek segítségével).
• Számos egyszerű ellenőrző összeg, például a személyi azonosítókban, bankkártyákban használt Luhn-formula egyszerű lineáris kongruenciaként számítható ki.
• A lineáriskongruencia-generátor az egyik széles körben elterjedt pszeudorandom generátor.
• A kriptográfiában egyes nyílt kulcsú titkosítások, például az RSA-eljárás és a Diffie–Hellman alapjául szolgál. Számos szimmetrikus kulcsú rejtjelezés is használja, például az AES, az IDEA vagy az RC4.
• A prímtesztelések (Pepin-teszt, Rabin–Miller-teszt, Fermat-teszt) bizonyos kongruenciák vizsgálatát követelik.

Források

• Freud–Gyarmati: Számelmélet, Nemzeti Tankönyvkiadó, 2000
• Christian Spannagel: Kongruenzen und Restklassen. Vorlesungsreihe, 2012.

Fordítás

Ez a szócikk részben vagy egészben a Kongruenz (Zahlentheorie) 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.

Jegyzetek