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.

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

Definíció[szerkesztés | forrásszöveg szerkesztése]

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.

Története[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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.

Kongruencia osztása egész számmal[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 \Bbb Z, m>1, (a,m)=1 \Rightarrow a^{\varphi(m)} \equiv 1 \pmod{m}

A kis Fermat-tétel[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

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[szerkesztés | forrásszöveg szerkesztése]

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.

Primitív gyök[szerkesztés | forrásszöveg szerkesztése]

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)[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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, 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[szerkesztés | forrásszöveg szerkesztése]

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.

Alkalmazások[szerkesztés | forrásszöveg szerkesztése]

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

Forrás[szerkesztés | forrásszöveg szerkesztése]

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