Lineáris kongruenciák

A Wikipédiából, a szabad enciklopédiából
ax\equiv b \pmod{m} \qquad a,b \in \Bbb Z, m \in \Bbb Z^+

Ezen kongruencia megoldásai azon c \in \Bbb Z számok, melyre ac \equiv b \pmod{m}. Ha egy \ c szám megoldás, akkor \ c+km is az, ahol k \in \Bbb Z, hiszen a(c+km) = ac+akm\equiv b+0\equiv b \pmod{m}. Ezek a megoldások maradékosztályokat alkotnak, a megoldó maradékosztályok számát tekintjük a megoldások számának (ha a konkrét egészeket tekintenénk, akkor \infty sok lenne ha létezik megoldás).

Amikor ilyen kongruenciákat oldunk meg, akkor azokat az egészeket keressük, ami egy bizonyos számmal (modulus) osztva meghatározott maradékot ad. Ezek hasonlóak mint az egyenletek, csupán itt a maradékra teszünk csak kikötést, így megoldó maradékosztályokról beszélhetünk. Minden egyes lineáris kongruencia egyben egy diofantoszi egyenlet is. A következőképp feleltetjük meg őket egymásnak:

ax \equiv b \pmod{m} kongruenciának megfelelő diofantoszi egyenlet a definícióból eredően: \ ax+my=b.

Tétel (Megoldhatóság)[szerkesztés | forrásszöveg szerkesztése]

A kongruenciák és a diofantoszi egyenletek közti megfeleltetésnek köszönhetően az ott ismert megoldhatóságra vonatkozó szükséges és elégséges feltételre visszavezethetjük a kongruenciák megoldhatóságát:
ax\equiv b \pmod{m} megoldható \Leftrightarrow (a,m) \mid b (azaz ha a és m legnagyobb közös osztója osztja b-t.)

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

m \mid (ax-b) \Leftrightarrow \exists c,k, hogy mk=ac-b \Leftrightarrow b=ax+my diofantoszi egyenlet megoldható \Leftrightarrow (a,m) \mid b.

Tétel (Megoldások száma)[szerkesztés | forrásszöveg szerkesztése]

Ha az ax\equiv b \pmod{m} kongruencia megoldható, akkor a megoldások száma \ (a,m). Legyen \ (a,m)=d, m=m_1d és \ s az egyik megoldása a kongruenciának.

Ekkor az összes (páronként inkongruens) megoldást képező maradékosztályok (mod\ m): s, s+\frac{m}{d}, s+2\frac{m}{d}, \dots , s+(d-1)\frac{m}{d}.

Megjegyzés: Ha \ (a,m)=1, akkor a kongruencia \forall b \in \Bbb Z esetén megoldható és egyetlen maradékosztály a megoldása.

Bizonyítás[szerkesztés | forrásszöveg szerkesztése]

Tegyük fel, hogy s,t\in \Bbb Z megoldásai a kongruenciának. Ekkor as \equiv b \pmod{m} és at \equiv b \pmod{m}. Ez azzal ekvivalens, hogy as\equiv at \pmod{m}. A fentebb lévő (5) tétel alapján ez tovább ekvivalens t \equiv s \pmod{m_1} kongruenciával.
Mivel \ t egy másik megoldás, ezért minden megoldás t=s+km_1, k \in \Bbb Z alakú, és ezek ki is elégítik a kongruenciát.

Tekintsünk két megoldást: \ t_1=s+jm_1, t_2=s+j'm_1. Megnézzük, mikor esik két megoldás ugyanabba a maradékosztályba: t_1 \equiv t_2 \pmod{m} \Leftrightarrow jm_1 \equiv j'm_1 \pmod{m} \Leftrightarrow j \equiv j' \pmod{d}.
Azaz két megoldás akkor esik ugyanabba a maradékosztályba (mod\ m) ha a két \ j kongruens (mod\ d). Mivel a 0,1, \dots, (d-1) inkongruensek (mod\ d), és ki is adják az összes (mod\ d) maradékosztályt, így ezen d értéket behelyettesítve k helyére megkapjuk az összes megoldó maradékosztályt.

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

Akárcsak az egyenleteknél, itt is beszélhetünk több kongruenciából álló kongruenciarendszerről. Ekkor egy olyan maradékosztályt keresünk, ami minden kongruenciát kielégít. A páronként relatív prím modulusú kongruenciarendszerek megoldásáról szól a kínai maradéktétel, mely kimondja hogy a megoldás létezik és egyértelmű. Bővebben a megfelelő wiki oldalon, bizonyítással.

Wilson-tétel[szerkesztés | forrásszöveg szerkesztése]

A tétel a következőt mondja ki:
Ha p prímszám, akkor

(p-1)! \equiv -1 \pmod{p}.

A tétel a bizonyítása megtalálható a Wilson-tétel oldalon.

Lásd még[szerkesztés | forrásszöveg szerkesztése]

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

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