Kongruencia

(Kongruencia (matematika) szócikkből átirányítva)
Ez a közzétett változat, ellenőrizve: 2023. május 14.

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

Legyen   tetszőleges egész szá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

 

azaz

 

Jelölése:   vagy  .

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

  •  
  •  
  •  

Ha a nem kongruens b-vel modulo m, azt mondjuk, inkongruens vele, és   vagy   alakban jelöljük.

Az itt szereplő   a matematikai maradékképző függvény, ami a maradékos osztás maradékát rendeli a számhoz.

Az 5 kongruens 11-gyel modulo 3, mert  , és  . A két maradék megegyezik, mivel  .

Az 5 inkongruens 11-gyel modulo 4, mivel   és  ; 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,  .

Története

szerkesztés

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   szimbólum helyett a   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

szerkesztés

A kongruencia ekvivalenciareláció, azaz reflexív, szimmetrikus és tranzitív: tetszőleges  , valamint   esetén

  •  
  •  
  •  

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   és  . Ekkor

  •  
  •  
  •  

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

 .

Ha   polinom az egész számok fölött, akkor

 

Kongruencia osztása egész számmal

szerkesztés

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   a c és m egészek legnagyobb közös osztója. Ekkor  .
Megjegyzés: a tétel következménye, hogy  .

Ez azt is jelenti, hogy, ha   osztója  -nek, akkor   esetén  .

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:  , ami ekvivalens a   oszthatósággal.
Mivel  , ezért a fenti oszthatóság pontosan akkor teljesül, ha  , 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

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:

 

A kis Fermat-tétel

szerkesztés

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   miatt a következő állítást kapjuk:

Ha   egész szám,   olyan prím, ami nem osztja  -t, akkor  .

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

Ha   egész szám,   prím, akkor  .

Kínai maradéktétel

szerkesztés

A kínai maradéktétel szerint: Ha   nullától különböző egész számok, és   a legkisebb közös többszörösük, akkor:

  minden  

Hatványozás

szerkesztés

Ha   természetes szám, akkor

 

Relatív prím   és   esetén teljesül az Euler-tétel:

 ,

ahol   az Euler-féle φ-függvény. Ebből következik  , hogyha  . Ennek speciális esete a kis Fermat-tétel.

  • Ha  , akkor  .
  • Ha   páratlan, akkor  .
  • Minden egész számra teljesül a következők valamelyike:

  vagy   vagy  .

  • Ha  , akkor  .
  • Minden egész számra teljesül a következők valamelyike:
  vagy   vagy  .
  • Minden egész számra teljesül a következők valamelyike:
  vagy  .
  • Hogyha   teljes hatodik hatvány, azaz négyzet- és köbszám is, akkor   vagy   vagy   vagy  .
  • Legyen   prímszám úgy, hogy  . Ekkor  .
  • Legyen   páratlan,   pozitív egész szám. Ekkor  .
  • Legyen  , illetve   és   ikerprímek. Ekkor  .

A kongruenciaosztályok gyűrűje

szerkesztés

A modulo n nullával kongruens számok az egész számok egy ideálját alkotják, az   a más számokkal kongruensek pedig ennek mellékosztályait. Így definiálhatjuk a   faktorcsoportot, amelynek elemei az   maradékosztályok. (Néha az   jelölést is használják.) A faktorcsoport a   elemekből áll, műveletei egyszerűen visszavezethetőek az egész számok műveleteire:

  •  
  •  
  •  

  ezekkel a műveletekkel egy kommutatív gyűrű; ha n prím, akkor (és csak akkor) test.

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

Legyen  . A legkisebb olyan   számot, melyre  , az a (multiplikatív) rendjének nevezzük modulo m.
Jelölése:  .

Megjegyzés: Az Euler Fermat-tételből következik, hogy minden   esetén létezik az a-nak rendje és  . Ha  , akkor a-nak nem létezik ilyen szám.

Primitív gyök

szerkesztés

Egy g számot primitív gyöknek nevezünk modulo m, ha  , azaz ha a g rendje a nála kisebb, m-hez relatív prímek száma (Euler-féle   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

Legyen p prím, g primitív gyök modulo p és  . Ekkor az a-nak a g alapú indexén azt a   számot értjük, melyre  .
Jelölés:   (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
 

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   a   számnak is osztója. Ekkor  -vel lehet egyszerűsíteni, és modulo   megoldani a kongruenciát. Visszahelyettesítve a megoldást az eredeti kongruenciába,   megoldást találunk.

A megoldást kibővített euklideszi algoritmussal megtalálhatjuk, ahonnan kapjuk az  ,   egészeket úgy, hogy:

 

Innen egy megoldás kapható, mint:

 ,

a többi pedig ettől  -szeresben különbözik.

Például   megoldható, hiszen   osztója a  -nek is, és a megoldásszám  . A kibővített euklideszi algoritmus eredménye  , amiből adódik az   megoldás. A megoldások egy maradékosztályt alkotnak modulo  , így a megoldáshalmaz  .

Magasabb fokú kongruenciák

szerkesztés

Legyen m>0 adott,   egész együtthatós polinom. Ekkor tekinthetjük az   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

szerkesztés

Egy

 
 
 

alakú szimultán kongruencia megoldható, ha:

  • minden  -re   osztható  -vel, azaz minden kongruencia egyenként megoldható,
  • és minden   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

szerkesztés

Ha  ,  , akkor:

 

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

 

matematikai modulo függvényt kell alkalmazni, melynek előjele   előjelétől függ. Ezzel a definícióval  , és az azonos maradékosztályba tartozó számok ugyanazt a maradékot adják ugyanarra a modulusra.

Alkalmazások

szerkesztés

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

Fordítás

szerkeszté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.

  1. Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer, Berlin 2002, ISBN 3-540-43579-4
  2. Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, ISBN 3-540-43072-5, S. 111–117