Lineáris kongruenciák

Lineáris kongruenciának nevezzük az ${\displaystyle ax\equiv b{\pmod {m}}}$ formájú kongruenciákat, ahol ${\displaystyle a}$ és ${\displaystyle b}$ egész, ${\displaystyle m}$ pedig pozitív egész szám.

Ezen kongruencia megoldásai azon ${\displaystyle c\in \mathbb {Z} }$ számok, melyre ${\displaystyle ac\equiv b{\pmod {m}}}$. Ha egy ${\displaystyle c}$ szám megoldás, akkor ${\displaystyle c+km}$ is az, ahol ${\displaystyle k\in \mathbb {Z} }$, hiszen ${\displaystyle 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 végtelen sok lenne, amennyiben 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. Az ${\displaystyle ax\equiv b{\pmod {m}}}$ kongruenciának megfelelő diofantoszi egyenlet a definícióból eredően: ${\displaystyle ax+my=b}$.

Tétel (megoldhatóság)

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:

${\displaystyle ax\equiv b{\pmod {m}}}$ megoldható ${\displaystyle \Leftrightarrow (a,m)\mid b}$ (azaz ${\displaystyle a}$ és ${\displaystyle m}$ legnagyobb közös osztója osztja ${\displaystyle b}$-t.)

Bizonyítás

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

Tétel (megoldások száma)

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

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

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

Bizonyítás

Tegyük fel, hogy ${\displaystyle s,t\in \mathbb {Z} }$ megoldásai a kongruenciának. Ekkor ${\displaystyle as\equiv b{\pmod {m}}}$ és ${\displaystyle at\equiv b{\pmod {m}}}$. Ez azzal ekvivalens, hogy ${\displaystyle as\equiv at{\pmod {m}}}$. Ez tovább ekvivalens ${\displaystyle t\equiv s{\pmod {m_{1}}}}$ kongruenciával. Mivel ${\displaystyle t}$ egy másik megoldás, ezért minden megoldás ${\displaystyle t=s+km_{1},k\in \mathbb {Z} }$ alakú, és ezek ki is elégítik a kongruenciát.

Tekintsünk két megoldást: ${\displaystyle t_{1}=s+jm_{1}}$, ${\displaystyle t_{2}=s+j'm_{1}}$. Megnézzük, mikor esik két megoldás ugyanabba a maradékosztályba: ${\displaystyle 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 ${\displaystyle (\operatorname {mod} m)}$, ha a két ${\displaystyle j}$ kongruens ${\displaystyle (\operatorname {mod} d)}$. Mivel a ${\displaystyle 0,1,\dots ,(d-1)}$ inkongruensek ${\displaystyle (\operatorname {mod} d)}$, és ki is adják az összes ${\displaystyle (\operatorname {mod} d)}$ maradékosztályt, így ezen ${\displaystyle d}$ értéket behelyettesítve ${\displaystyle k}$ helyére megkapjuk az összes megoldó maradékosztályt.

Kongruenciarendszerek

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

Wilson-tétel

A Wilson-tétel azt mondja ki, hogy ha ${\displaystyle p}$ prímszám, akkor ${\displaystyle (p-1)!\equiv -1{\pmod {p}}}$.

További információk

• Alice és Bob - 20. rész: Alice, Bob, Euler és Fermat
• Alice és Bob - 21. rész: Alice és Bob titkosít

Források

• Freud Róbert – Gyarmati Edit: Számelmélet. Budapest: Nemzeti Tankönyvkiadó. 2000. ISBN 963-19-0784-8