„Kongruencia” változatai közötti eltérés
[ellenőrzött változat] | [ellenőrzött változat] |
a Egy szó német maradt |
|||
(32 közbenső módosítás, amit 11 másik szerkesztő végzett, nincs mutatva) | |||
1. sor: | 1. sor: | ||
A '''kongruencia''' a [[számelmélet]]ben 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''' a [[számelmélet]]ben 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étel]]e. |
A kongruencia egy [[reláció]], amelyet az [[egész számok]] [[Halmaz (matematika)|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étel|Chevalley tétel]]e. |
||
Ha két egész szám nem kongruens, akkor inkongruensnek nevezik őket. |
Ha két egész szám nem kongruens, akkor inkongruensnek nevezik őket. |
||
14. sor: | 14. sor: | ||
:<math>\exists k \in \Z: a = km + b </math> |
:<math>\exists k \in \Z: a = km + b </math> |
||
Jelölése: <math>a \equiv b \pmod m</math> vagy <math> a \equiv b\quad (m)</math>. |
Jelölése: <math>a \equiv b \pmod m</math> vagy <math> a \equiv b\quad (m)</math>. |
||
Lehet találkozni a következő jelölésekkel is: |
|||
* <math>a \equiv b \mod m</math> |
|||
* <math>a \equiv b \mod m\Z</math> |
|||
* <math>a \equiv_m b</math> |
|||
Ha ''a'' nem kongruens ''b''-vel modulo ''m'', azt mondjuk, '''inkongruens''' vele, és <math>a \not \equiv b \pmod m</math> vagy <math> a \not\equiv b\quad (m)</math> alakban jelöljük. |
Ha ''a'' nem kongruens ''b''-vel modulo ''m'', azt mondjuk, '''inkongruens''' vele, és <math>a \not \equiv b \pmod m</math> vagy <math> a \not\equiv b\quad (m)</math> alakban jelöljük. |
||
Az itt szereplő <math>\operatorname{mod}</math> 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 <math>5 : 3 = 1 \text{ maradék } 2</math>, és <math>11 : 3 = 3 \text{ maradék } 2</math>. A két maradék megegyezik, mivel <math>11 - 5 = 6 = 2 \cdot 3</math>. |
|||
Az 5 inkongruens 11-gyel modulo 4, mivel <math>5 : 4 = 1 \text{ maradéka } 1</math> és <math>11 : 4 = 2 \text{ maradék } 3</math>; 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, <math>-8= (-2)\cdot 6+ 4</math>. |
|||
== Története == |
== 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 <math>\equiv</math> szimbólum helyett a <math>\mp</math> jelet használta. |
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 <math>\equiv</math> szimbólum helyett a <math>\mp</math> jelet használta.<ref name="BUND">[[Peter Bundschuh]]: ''Einführung in die Zahlentheorie.'' 5. Auflage. Springer, Berlin 2002, {{ISBN|3-540-43579-4}}</ref> |
||
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. |
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.<ref name="YAN">Song Y. Yan: ''Number theory for computing.'' 2. Auflage. Springer, 2002, {{ISBN|3-540-43072-5}}, S. 111–117</ref> |
||
== Elemi tulajdonságai == |
== Elemi tulajdonságai == |
||
35. sor: | 49. sor: | ||
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 <math>a,b,c,d \in \mathbb Z</math> és <math>m,n \in \mathbb Z^+</math>. Ekkor |
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 <math>a,b,c,d \in \mathbb Z</math> és <math>m,n \in \mathbb Z^+</math>. Ekkor |
||
* <math>a\equiv b \pmod{m},\ c\equiv d \pmod{m} \Rightarrow a+c\equiv b+d \pmod{m}</math> |
* <math>a\equiv b \pmod{m},\ c\equiv d \pmod{m} \Rightarrow a+c\equiv b+d \pmod{m}</math> |
||
* <math>a\equiv b \pmod{m},\ c\equiv d \pmod{m} \Rightarrow a-c\equiv b-d \pmod{m}</math> |
|||
* <math>a\equiv b \pmod{m},\ c\equiv d \pmod{m} \Rightarrow ac\equiv bd \pmod{m}</math> |
* <math>a\equiv b \pmod{m},\ c\equiv d \pmod{m} \Rightarrow ac\equiv bd \pmod{m}</math> |
||
40. sor: | 55. sor: | ||
:<math>a \equiv b \pmod{0} \Rightarrow a = b</math>. |
:<math>a \equiv b \pmod{0} \Rightarrow a = b</math>. |
||
Ha <math>f \in \mathbb{Z}[X]</math> polinom az egész számok fölött, akkor |
|||
:<math>f(a) \equiv f(a') \pmod{m}</math> |
|||
=== Kongruencia osztása egész számmal === |
=== 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.<br /> |
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.<br /> |
||
Legyen <math>\ d=(c,m)</math>. Ekkor <math>ac\equiv bc\pmod{m} \Leftrightarrow a\equiv b \pmod{\frac{m}{d}}</math>.<br /> |
Legyen <math>\ d=(c,m)</math> a ''c'' és ''m'' egészek [[legnagyobb közös osztó]]ja. Ekkor <math>ac\equiv bc\pmod{m} \Leftrightarrow a\equiv b \pmod{\frac{m}{d}}</math>.<br /> |
||
Megjegyzés: a tétel következménye, hogy <math>ac\equiv bc \pmod{m}, (c,m)=1 \Rightarrow a \equiv b \pmod{m}</math>. |
Megjegyzés: a tétel következménye, hogy <math>ac\equiv bc \pmod{m}, (c,m)=1 \Rightarrow a \equiv b \pmod{m}</math>. |
||
Ez azt is jelenti, hogy, ha <math>d</math> osztója <math>m</math>-nek, akkor <math>a\equiv b \pmod m</math> esetén <math>a\equiv b \pmod d</math>. |
|||
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. |
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. |
||
54. sor: | 73. sor: | ||
=== Euler–Fermat-tétel === |
=== Euler–Fermat-tétel === |
||
{{Bővebben|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ó, és ami által azok bizonyítása is lényegesen leegyszerűsödik.<br /> |
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.<br /> |
||
A tétel állítása: |
A tétel állítása: |
||
:<math>a,m \in \mathbb Z, m>1, (a,m)=1 \Rightarrow a^{\varphi(m)} \equiv 1 \pmod{m}</math> |
:<math>a,m \in \mathbb Z, m>1, (a,m)=1 \Rightarrow a^{\varphi(m)} \equiv 1 \pmod{m}</math> |
||
64. sor: | 83. sor: | ||
A tétel egy másik, gyakori alakja: |
A tétel egy másik, gyakori alakja: |
||
:Ha <math>a</math> egész szám, <math>p</math> [[prímszámok|prím]], akkor <math>a^{p} \equiv a \pmod{p} </math>. |
:Ha <math>a</math> egész szám, <math>p</math> [[prímszámok|prím]], akkor <math>a^{p} \equiv a \pmod{p} </math>. |
||
===Kínai maradéktétel=== |
|||
A [[kínai maradéktétel]] szerint: |
|||
Ha <math>m_1, m_2, \dotsc, m_k</math> nullától különböző egész számok, és <math>m</math> a [[legkisebb közös többszörös]]ük, akkor: |
|||
:<math>a \equiv a' \pmod{m_\kappa}</math> minden <math>\kappa = 1, 2, \dotsc, k \quad \Leftrightarrow \quad a \equiv a' \pmod{m}</math> |
|||
===Hatványozás=== |
|||
Ha <math>n \in \N_0</math> [[természetes szám]], akkor |
|||
:<math>a^n \equiv (a')^n \pmod{m}</math> |
|||
[[Relatív prím]] <math>a</math> és <math>m</math> esetén teljesül az [[Euler-tétel]]: |
|||
:<math>a^{\varphi(m)} \equiv 1 \pmod m</math>, |
|||
ahol <math>\varphi(m)</math> az [[Euler-függvény|Euler-féle φ-függvény]]. |
|||
Ebből következik <math>a^n \equiv a^{n'} \pmod{m}</math>, hogyha <math>n \equiv n' \pmod{\varphi(m)}</math>. Ennek speciális esete a kis Fermat-tétel. |
|||
===Példák=== |
|||
* Ha <math>t \ne 0</math>, akkor <math>t \cdot a \equiv t \cdot b \pmod {|t| \cdot m}</math>. |
|||
* Ha <math>a</math> páratlan, akkor <math>a^2 \equiv 1 \pmod 8</math>. |
|||
* Minden egész számra teljesül a következők valamelyike: |
|||
<math>a^3 \equiv 0 \pmod 9</math> vagy <math>a^3 \equiv 1 \pmod 9</math> vagy <math>a^3 \equiv 8 \pmod 9</math>. |
|||
* Ha <math>a</math>, akkor <math>a^3 \equiv a \pmod 6</math>. |
|||
* Minden egész számra teljesül a következők valamelyike: |
|||
:<math>a^3 \equiv 0 \pmod 7</math> vagy <math>a^3 \equiv 1 \pmod 7</math> vagy <math>a^3 \equiv 6 \pmod 7</math>. |
|||
* Minden egész számra teljesül a következők valamelyike: |
|||
:<math>a^4 \equiv 0 \pmod 5</math> vagy <math>a^4 \equiv 1 \pmod 5</math>. |
|||
* Hogyha <math>a</math> teljes hatodik hatvány, azaz négyzet- és köbszám is, akkor <math>a \equiv 0 \pmod {36}</math> vagy <math>a \equiv 1 \pmod {36}</math> vagy <math>a \equiv 9 \pmod {36}</math> vagy <math>a \equiv 28 \pmod {36}</math>. |
|||
* Legyen <math>p</math> prímszám úgy, hogy <math>n < p < 2n</math>. Ekkor <math>{2n \choose n} \equiv 0 \pmod{p}</math>. |
|||
* Legyen <math>a</math> páratlan, <math>n > 0</math> pozitív egész szám. Ekkor <math>a^{2^n} \equiv 1 \pmod {2^{n+2}}</math>. |
|||
* Legyen <math>p > 3</math>, illetve <math>p</math> és <math>q = p + 2</math> [[ikerprímek]]. Ekkor <math>p \cdot q \equiv -1 \pmod 9</math>. |
|||
== A kongruenciaosztályok gyűrűje == |
== A kongruenciaosztályok gyűrűje == |
||
102. sor: | 146. sor: | ||
:<math>ax\equiv b \pmod{m} \qquad a,b \in \mathbb Z, m \in \mathbb Z^+</math> |
:<math>ax\equiv b \pmod{m} \qquad a,b \in \mathbb Z, m \in \mathbb Z^+</math> |
||
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. |
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 <math>g = \operatorname{lnko}(a, m)</math> a <math>b</math> számnak is osztója. Ekkor <math>g</math>-vel lehet egyszerűsíteni, és modulo <math>\tfrac{m}{g}</math> megoldani a kongruenciát. Visszahelyettesítve a megoldást az eredeti kongruenciába, <math>g</math> megoldást találunk. |
||
A megoldást kibővített euklideszi algoritmussal megtalálhatjuk, ahonnan kapjuk az <math>s</math>, <math>t</math> egészeket úgy, hogy: |
|||
: <math> g = \operatorname{lnko}(a, m) = s \cdot a + t \cdot m </math> |
|||
Innen egy megoldás kapható, mint: |
|||
:<math>\textstyle x_1 = \frac{s \cdot c}{g}</math>, |
|||
a többi pedig ettől <math>\tfrac{m}{g}</math>-szeresben különbözik. |
|||
Például <math>4x \equiv 10 \pmod {18}</math> megoldható, hiszen <math>\operatorname{lnko}(4,18) = 2</math> osztója a <math>10</math>-nek is, és a megoldásszám <math>2</math>. A kibővített euklideszi algoritmus eredménye <math> 2 = -4 \cdot 4 + 1 \cdot 18</math>, amiből adódik az <math>\textstyle x_1 = \frac{-4 \cdot 10}{2} = -20</math> megoldás. A megoldások egy maradékosztályt alkotnak modulo <math>\textstyle \frac{18}{2} = 9</math>, így a megoldáshalmaz <math>\{ \cdots, -20, -11, -2, 7, 16, 25, \cdots \}</math>. |
|||
== Magasabb fokú kongruenciák == |
== Magasabb fokú kongruenciák == |
||
{{Bővebben|Magasabb fokú kongruenciák}} |
{{Bővebben|Magasabb fokú kongruenciák}} |
||
Legyen ''m''>0 adott, <math>f(x)=a_0+a_1x+ \dots a_kx^ |
Legyen ''m''>0 adott, <math>f(x)=a_0+a_1x+ \dots a_kx^k</math> egész együtthatós polinom. Ekkor tekinthetjük az <math>f(x) \equiv 0 \pmod{m}</math> 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. |
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 |
|||
: <math>\qquad a_1x \equiv c_1 \pmod {m_1}</math> |
|||
: <math>\qquad a_2x \equiv c_2 \pmod {m_2}</math> |
|||
: <math>\qquad a_3x \equiv c_3 \pmod {m_3}</math> |
|||
alakú szimultán kongruencia megoldható, ha: |
|||
* minden <math>i</math>-re <math>c_i</math> osztható <math>g_i = \operatorname{lnko}(a_i, m_i)</math>-vel, azaz minden kongruencia egyenként megoldható, |
|||
* és minden <math>\tfrac{m_i}{g_i}</math> 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 <math>a, b, m \in \Z</math>, <math>m \neq 0</math>, akkor: |
|||
:<math>a \equiv b \pmod m \quad \Leftrightarrow \quad (a \bmod m) = (b \bmod m) \quad \Leftrightarrow \quad (a - b) \bmod m = 0</math> |
|||
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 |
|||
:<math>(a \bmod m) := a - \left \lfloor \frac{a}{m} \right \rfloor \cdot m</math> |
|||
matematikai modulo függvényt kell alkalmazni, melynek előjele <math>m</math> előjelétől függ. Ezzel a definícióval <math>(-1) \bmod 7 = 6</math>, és az azonos maradékosztályba tartozó számok ugyanazt a maradékot adják ugyanarra a modulusra. |
|||
== Alkalmazások == |
== Alkalmazások == |
||
116. sor: | 184. sor: | ||
* A [[lineáriskongruencia-generátor]] az egyik széles körben elterjedt [[pszeudorandom generátor]]. |
* A [[lineáriskongruencia-generátor]] az egyik széles körben elterjedt [[pszeudorandom generátor]]. |
||
* A kriptográfiában egyes [[Nyilvános kulcsú rejtjelezés|nyílt kulcsú titkosítás]]ok, 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 [[Advanced Encryption Standard|AES]], az [[IDEA]] vagy az [[RC4]]. |
* A kriptográfiában egyes [[Nyilvános kulcsú rejtjelezés|nyílt kulcsú titkosítás]]ok, 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 [[Advanced Encryption Standard|AES]], az [[IDEA]] vagy az [[RC4]]. |
||
* A prímtesztelések ([[Pepin-teszt]], [[Rabin–Miller-teszt]]) bizonyos kongruenciák vizsgálatát követelik. |
* A prímtesztelések ([[Pepin-teszt]], [[Rabin–Miller-teszt]], [[Fermat-teszt]]) bizonyos kongruenciák vizsgálatát követelik. |
||
== További információk == |
|||
* [https://youproof.hu/kriptografia/18-modularis-aritmetika-homomorfizmus-kongruencia-reszgyuru-ideal-maradekosztalygyuru Alice és Bob - 18. rész: Alice és Bob felcsavarja a számegyenest] |
|||
* [https://youproof.hu/kriptografia/20-kongruencia-redukalt-maradekosztaly-euler-fuggveny-linearis-kongruencia-maradekrendszer-euler-fermat-tetel Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat] |
|||
* [https://youproof.hu/kriptografia/21-rsa-algoritmus-kibovitett-euklideszi-algoritmus-euler-fuggveny-kulcsgeneralas-ismetelt-negyzetreemeles-modszere Alice és Bob - 21. rész: Alice és Bob titkosít] |
|||
* [https://youproof.hu/kriptografia/22-kinai-maradektetel-konguenciarendszerek-kis-fermat-tetel-rsa-bizonyitas-gyuruk-direkt-szorzata-rsa-dekodolas Alice és Bob - 22. rész: Alice, Bob és a kínaiak] |
|||
* [https://youproof.hu/kriptografia/23-primteszteles-fermat-primteszt-miller-rabin-primteszt-carmichael-szam-univerzalis-alprim-fermat-faktorizacio Alice és Bob - 23. rész: Alice és Bob prímszámok után nyomoz] |
|||
== Források == |
== Források == |
||
* Freud–Gyarmati: ''Számelmélet'', Nemzeti Tankönyvkiadó, 2000 |
* Freud–Gyarmati: ''Számelmélet'', Nemzeti Tankönyvkiadó, 2000 |
||
* [[Christian Spannagel]]: [https://av.tib.eu/series/239 Kongruenzen und Restklassen]. Vorlesungsreihe, 2012. |
|||
==Fordítás== |
|||
{{fordítás|de|Kongruenz (Zahlentheorie)}} |
|||
==Jegyzetek== |
|||
{{jegyzetek}} |
|||
{{csonk-dátum|csonk-mat|2007 áprilisából}} |
{{csonk-dátum|csonk-mat|2007 áprilisából}} |
A lap jelenlegi, 2023. május 14., 14:04-kori változata
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.
Példák
[szerkesztés]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.
Példák
[szerkesztés]- 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.
Algebra
[szerkesztés]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.
Rend
[szerkesztés]Legyen . A legkisebb olyan számot, melyre , az a (multiplikatív) rendjének nevezzük modulo m.
Jelölése: .
Megjegyzés: Az EulerFermat-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.
- 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
[szerkesztés]- Freud–Gyarmati: Számelmélet, Nemzeti Tankönyvkiadó, 2000
- Christian Spannagel: Kongruenzen und Restklassen. Vorlesungsreihe, 2012.
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.
Jegyzetek
[szerkesztés]- ↑ Peter Bundschuh: Einführung in die Zahlentheorie. 5. Auflage. Springer, Berlin 2002, ISBN 3-540-43579-4
- ↑ Song Y. Yan: Number theory for computing. 2. Auflage. Springer, 2002, ISBN 3-540-43072-5, S. 111–117