„Kongruencia” változatai közötti eltérés

 

 

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

 

== Elemi tulajdonságai ==

 

* <math>a\equiv a \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{0} \Rightarrow a = b</math>.

 

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

 

Definíció alapján: <math>ac\equiv bc\pmod{m} \Leftrightarrow m \mid (a-b)c</math>, ami ekvivalens a <math>\frac{m}{d} \mid (a-b)\frac{c}{d}</math> oszthatósággal.<br />

 

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.

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

 

A modulo ''n'' nullával kongruens számok az [[egész számok]] egy [[Ideál (gyűrűelmélet)|ideálját]] alkotják, az <math>n\mathbb{Z}</math> a más számokkal kongruensek pedig ennek [[mellékosztály]]ait. Így definiálhatjuk a <math>\mathbb{Z}_n = \mathbb{Z}/n\mathbb{Z}</math> [[faktorcsoport]]ot, amelynek elemei az <math>\overline{a}_n = \left\{\ldots, a - 2n, a - n, a, a + n, a + 2n, \ldots \right\}</math> maradékosztályok. (Néha az <math>[a]</math> jelölést is használják.) A faktorcsoport a <math>\overline{0}_n, \overline{1}_n, \overline{2}_n,\ldots, \overline{n-1}_n</math> elemekből áll, műveletei egyszerűen visszavezethetőek az egész számok műveleteire:

 

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

* A kriptográfiában egyes [[nyílt kulcsú titkosítás]]ok, 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.