Kongruencia

A Wikipédiából, a szabad enciklopédiából.

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.

Tartalomjegyzék

1 Definíció
2 Története
3 Elemi tulajdonságai
4 A kongruenciaosztályok gyűrűje
5 Rend, primitív gyök, index (diszkrét logaritmus)
6 Lineáris kongruenciák
7 Magasabb fokú kongruenciák
8 Alkalmazások
9 Forrás

[szerkesztés] Definíció

Legyen $a, b$ tetszőleges, $m$ pozitív egész 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 \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.

[szerkesztés] 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.

[szerkesztés] Elemi tulajdonságai

A kongruencia ekvivalenciareláció, azaz reflexív, szimmetrikus és tranzitív: tetszőleges $a,b,c \in \Bbb Z$ , valamint $m \in \Bbb 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 \Bbb Z$ és $m,n \in \Bbb 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$ .

[szerkesztés] 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.

[szerkesztés] Euler–Fermat-tétel

Bővebben: 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ó, ami által azok bizonyítása és lényegeseb leegyszerűsödik.
A tétel állítása:

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

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

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:

a

egész szám,

p

prím, akkor $a^{p} \equiv a \pmod{p}$ .

[szerkesztés] 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.

[szerkesztés] Rend, primitív gyök, index (diszkrét logaritmus)

Néhány fogalom a témával kapcsolatban, részletesebben a megfelelő wiki-oldalakon (lásd lejjebb) és a Magasabbfokú kongruenciák oldalon.

[szerkesztés] Rend

Bővebben: multiplikatív rend

Legyen $\ (a,m)=1$ . A legkisebb olyan $k \in \Bbb 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.

[szerkesztés] 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).

[szerkesztés] 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ó.)

[szerkesztés] Lineáris kongruenciák

Bővebben: lineáris kongruenciák

$ax\equiv b \pmod{m} \qquad a,b \in \Bbb Z, m \in \Bbb 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, mindeö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.

[szerkesztés] Magasabb fokú kongruenciák

Bővebben: magasabb fokú kongruenciák

Legyen m>0 adott, $f(x)=a_0+a_1x+ \dots a_kx^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 magasabbfokú egyenletekhez. Ezek megoldása bizonyos esetekben nagyon leegyszerűsíthető, de nincsenek megoldóképletek, csak algoritmusok, amik elvezetnek a kívánt eredményhez.

[szerkesztés] 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 számban és bankkártyákban használt Luhn-formula egyszerű lineáris kongruenciaként számítható ki.
A lineáris kongruencia 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 és a Diffie-Hellman alapjául szolgál. Számos szimmetrikus kulcsú titkosítá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.

[szerkesztés] Forrás

Freud–Gyarmati: Számélmélet, Nemzeti Tankönyvkiadó, 2000

Ez a matematikai tárgyú lap még csak csonk (azaz erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle!

Kategória: Számelmélet

Rejtett kategóriák: Csonkok (matematika) | Csonkok 2007 áprilisából

See also ebooksgratis.com: no banners, no cookies, totally FREE.