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 $a,b$ tetszőleges egész szám, $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

$m\mid a-b$

azaz

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

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

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

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 $\equiv$ szimbólum helyett a $\mp$ jelet használta.

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.

Elemi tulajdonságai

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

• $a\equiv a{\pmod {m}}$
• $a\equiv b{\pmod {m}}\Rightarrow b\equiv a{\pmod {m}}$
• $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.

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 $a,b,c,d\in \mathbb {Z}$ és $m,n\in \mathbb {Z} ^{+}$. Ekkor

• $a\equiv b{\pmod {m}},\ c\equiv d{\pmod {m}}\Rightarrow a+c\equiv b+d{\pmod {m}}$
• $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ő:

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

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 $\ d=(c,m)$. Ekkor $ac\equiv bc{\pmod {m}}\Leftrightarrow a\equiv b{\pmod {\frac {m}{d}}}$.
Megjegyzés: a tétel következménye, hogy $ac\equiv bc{\pmod {m}},(c,m)=1\Rightarrow a\equiv b{\pmod {m}}$.

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: $ac\equiv bc{\pmod {m}}\Leftrightarrow m\mid (a-b)c$, ami ekvivalens a ${\frac {m}{d}}\mid (a-b){\frac {c}{d}}$ oszthatósággal.
Mivel $\left({\frac {m}{d}},{\frac {c}{d}}\right)=1$, ezért a fenti oszthatóság pontosan akkor teljesül, ha ${\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

A tétel a 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:

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

A 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 $\varphi (p)=p-1$ miatt a következő állítást kapjuk:

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

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

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

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 $n\mathbb {Z}$ a más számokkal kongruensek pedig ennek mellékosztályait. Így definiálhatjuk a $\mathbb {Z} _{n}=\mathbb {Z} /n\mathbb {Z}$ faktorcsoportot, amelynek elemei az ${\overline {a}}_{n}=\left\{\ldots ,a-2n,a-n,a,a+n,a+2n,\ldots \right\}$ maradékosztályok. (Néha az $[a]$ jelölést is használják.) A faktorcsoport a ${\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:

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

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

Algebra

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 $\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

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

Megjegyzés: Az Euler$-$Fermat-tételből következik, hogy minden $\ (a,m)=1$ esetén létezik az a-nak rendje és $o_{m}(a)\leq \varphi (m)$. Ha $(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 $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 $\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 $(a,p)=1$. Ekkor az a-nak a g alapú indexén azt a $0\leq k\leq p-2$ számot értjük, melyre $a\equiv g^{k}{\pmod {p}}$.
Jelölés: $\ 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

$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.

Magasabb fokú kongruenciák

Legyen m>0 adott, $f(x)=a_{0}+a_{1}x+\dots a_{k}x^{x}$ egész együtthatós polinom. Ekkor tekinthetjük az $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.

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) bizonyos kongruenciák vizsgálatát követelik.

Forrás

• Freud–Gyarmati: Számelmélet, Nemzeti Tankönyvkiadó, 2000