BSz1 Jegyzet

2. Tétel:

Lineáris kongruenciák: a megoldhatóság szükséges és elégséges feltétele, megoldások száma. Euklideszi algoritmus, annak lépésszáma, alkalmazása lineáris kongruenciák megoldására is.

2.1. Lineáris kongruenciák (1.4.2. Tétel)

1.4.2. Tétel:

Az $a \cdot x \equiv b \pmod m$ lineáris kongruencia akkor és csak akkor megoldható, ha $(a, m) \mid b$. Ha pedig ez a feltétel teljesül, akkor $a \cdot x \equiv b \pmod m$ megoldásainak száma modulo $m$ pontosan $(a, m)$-val egyenlő.

Részletes Bizonyítás:

I. A feltétel szükségessége:

Legyen $d = (a, m)$. Tegyük fel, hogy az $a \cdot x \equiv b \pmod m$ kongruencia megoldható, és legyen $x_1$ egy megoldás. Ekkor $a \cdot x_1 \equiv b \pmod m$, így a definíció szerint $m \mid a \cdot x_1 - b$.

Mivel $d$ a legnagyobb közös osztó, tudjuk, hogy $d \mid m$, amiből következik, hogy $d \mid a \cdot x_1 - b$ is igaz. Mivel $d \mid a$, így $d \mid a \cdot x_1$ is teljesül. Mivel $d$ osztja a különbséget ($a \cdot x_1 - b$) és a különbség első tagját ($a \cdot x_1$) is, ezért osztania kell a kivonandót is: $d \mid b$.

II. Elégségesség és megoldásszám $(a, m) = 1$ esetén:

Helyettesítsük be $x$ helyére a $0, 1, \dots, m-1$ számokat. Ekkor az $a \cdot 0, a \cdot 1, \dots, a \cdot (m-1)$ értékeket kapjuk. Állítjuk, hogy ezek közül semelyik kettő nem azonos maradékot ad modulo $m$.

Indoklás: Ha $a \cdot x_1 \equiv a \cdot x_2 \pmod m$ lenne, akkor az 1.3.4. Tétel szerint (mivel $(a, m) = 1$) leoszthatnánk $a$-val, és $x_1 \equiv x_2 \pmod m$ adódna. Ez a vizsgált tartományban ($0 \le x < m$) csak akkor lehetséges, ha $x_1=x_2$.

Mivel az $m$ darab szám mind különböző maradékot ad, ezért ezek teljes maradékrendszert alkotnak. Emiatt pontosan egy olyan $x$ érték van, amelyre $a \cdot x$ maradéka éppen $b$ maradékával egyenlő. Tehát pontosan 1 megoldás van.

III. Elégségesség és megoldásszám $(a, m) = d > 1$ esetén:

Tegyük fel, hogy $d \mid b$. Vezessük be az $a' = \frac{a}{d}$, $m' = \frac{m}{d}$ és $b' = \frac{b}{d}$ jelöléseket. Az 1.3.4. Tétel szerint az $a \cdot x \equiv b \pmod m$ kongruencia ekvivalens az $a' \cdot x \equiv b' \pmod{m'}$ kongruenciával.

Mivel $(a', m') = 1$, az előző (II.) pont alapján ennek az új kongruenciának pontosan egy megoldása van modulo $m'$, jelöljük ezt $x_0$-val ($0 \le x_0 < m'$).

A kérdés, hogy ez hány megoldást jelent az eredeti modulus ($m$) szerint. Az összes egész megoldás $x = k \cdot m' + x_0$ alakú ($k \in \mathbb{Z}$). Két ilyen megoldás, $x_1 = k_1 m' + x_0$ és $x_2 = k_2 m' + x_0$ akkor kongruens modulo $m$, ha $m \mid (k_1 - k_2)m'$, ami ekvivalens azzal, hogy $d \mid k_1 - k_2$.

Ezért modulo $m$ pontosan $d$ darab különböző (inkongruens) megoldás létezik, amelyeket a $k = 0, 1, \dots, d-1$ értékek adnak meg:

$x \equiv x_0, x_0 + \frac{m}{d}, x_0 + 2\frac{m}{d}, \dots, x_0 + (d-1)\frac{m}{d} \pmod m$

■

Kidolgozott példa: Lineáris kongruencia több megoldással

Feladat:

Oldja meg a $6x \equiv 12 \pmod{15}$ lineáris kongruenciát, és határozza meg az összes megoldást modulo 15!

Megoldás menete az 1.4.2. Tétel alapján:

1. Ellenőrzés (d kiszámítása):

$a=6, m=15 \implies d=(6,15)=3$.
Mivel $3 \mid 12$, a kongruencia megoldható, és pontosan 3 megoldása van.

2. Egyszerűsítés (m' kiszámítása):

Osszuk el a kongruenciát $d=3$-mal:
$2x \equiv 4 \pmod{5}$
Itt már $(2,5)=1$, így egyetlen $x_0$ megoldást keresünk modulo 5.

3. Az alapmegoldás ($x_0$):

$2x \equiv 4 \pmod{5} \implies x \equiv 2 \pmod{5}$.
Tehát az első megoldásunk: $x_0 = 2$.

4. Az összes megoldás:

A megoldások távolsága $\frac{m}{d} = \frac{15}{3} = 5$.
$x_1 = 2 + 5 = 7$
$x_2 = 2 + 2 \cdot 5 = 12$

Végeredmény:

$x \equiv 2, 7, 12 \pmod{15}$

A megoldások száma megegyezik a legnagyobb közös osztóval ($d=3$).

2.2. A legnagyobb közös osztó kiszámítása (1.6.4.)

Két adott szám legnagyobb közös osztója kiszámítható a prímtényezős felbontásukból (az 1.1.5 Tétel alapján), de – amint azt már az 1.6.1. szakaszban említettük – a prímfaktorizációra nem ismert gyors (vagyis polinomiális futásidejű) algoritmus. Szerencsére létezik a legnagyobb közös osztó kiszámítására egy ennél sokkal hatékonyabb módszer is: az Euklideszi algoritmus.

Ez a matematikatörténet egyik első algoritmusa, szerepel már Euklidesznek az i. e. 300 körül megjelent Elemek című művében is. A következő feladatot vizsgáljuk tehát:

Bemenet: $a$ és $m$ egészek (amelyekre feltesszük, hogy $0 < a < m$);

Kimenet: $(a, m)$ (vagyis $a$ és $m$ legnagyobb közös osztója).

Az Euklideszi algoritmus ismételt maradékos osztásokon alapul: az első lépésben $m$-et osztjuk $a$-val, a másodikban $a$-t a kapott maradékkal, stb., az $i$-edik lépésben mindig az $(i - 2)$-edik lépésben kapott maradékot osztjuk az $(i - 1)$-edikben kapottal.

Példa az eljárásra: $(567, 1238)$ meghatározása

(1) $[1238/567] :$

(2) $[567/104] :$

(3) $[104/47] :$

(4) $[47/10] :$

(5) $[10/7] :$

(6) $[7/3] :$

(7) $[3/1] :$

$1238 = 2 \cdot 567 + 104$

$567 = 5 \cdot 104 + 47$

$104 = 2 \cdot 47 + 10$

$47 = 4 \cdot 10 + 7$

$10 = 1 \cdot 7 + 3$

$7 = 2 \cdot 3 + 1$

$3 = 3 \cdot 1 + 0$

Az Euklideszi algoritmus kimenete mindig az utolsó nemnulla maradék, a fenti példában tehát 1 (ami valóban egyenlő $(567, 1238)$ értékével).

Általános $a$ és $m$ esetén:

Az eljárás által végzett maradékos osztások sorozatát a következőképpen írhatjuk le:

(1) $[m/a] :$ $m = t_1 \cdot a + r_1$ $(0 \le r_1 < a)$
(2) $[a/r_1] :$ $a = t_2 \cdot r_1 + r_2$ $(0 \le r_2 < r_1)$
(3) $[r_1/r_2] :$ $r_1 = t_3 \cdot r_2 + r_3$ $(0 \le r_3 < r_2)$
(4) $[r_2/r_3] :$ $r_2 = t_4 \cdot r_3 + r_4$ $(0 \le r_4 < r_3)$
⋮
(k) $[r_{k-2}/r_{k-1}] :$ $r_{k-2} = t_k \cdot r_{k-1} + r_k$ $(0 \le r_k < r_{k-1})$
(k+1) $[r_{k-1}/r_k] :$ $r_{k-1} = t_{k+1} \cdot r_k + 0$

Itt az utolsó nemnulla maradék $r_k$, ez tehát az algoritmus kimenete; persze azt még be kell látnunk, hogy ez valóban megegyezik $a$ és $m$ legnagyobb közös osztójával.

Az eljárás általános matematikai leírása:

Tetszőleges $a$ és $m$ ($0 < a < m$) egészek esetén az eljárás által végzett maradékos osztások sorozatát a következőképpen írhatjuk le:

(1) [m / a] : $m = t_1 \cdot a + r_1$ ($0 \le r_1 < a$)
(2) [a / r₁] : $a = t_2 \cdot r_1 + r_2$ ($0 \le r_2 < r_1$)
(3) [r₁ / r₂] : $r_1 = t_3 \cdot r_2 + r_3$ ($0 \le r_3 < r_2$)
(4) [r₂ / r₃] : $r_2 = t_4 \cdot r_3 + r_4$ ($0 \le r_4 < r_3$)
⋮
(k) [rₖ₋₂/rₖ₋₁]: $r_{k-2} = t_k \cdot r_{k-1} + r_k$ ($0 \le r_k < r_{k-1}$)
(k+1) [rₖ₋₁/rₖ]: $r_{k-1} = t_{k+1} \cdot r_k + 0$

Itt az utolsó nemnulla maradék $r_k$, ez tehát az algoritmus kimenete; persze azt még be kell látnunk, hogy ez valóban megegyezik $a$ és $m$ legnagyobb közös osztójával.

Interaktív Megoldó: Euklideszi algoritmus

2.2.2. Az algoritmus helyessége (1.6.4. Állítás)

1.6.4. Állítás:

Az Euklideszi algoritmus fenti végrehajtásakor $r_k = (a, m)$.

Részletes Bizonyítás:

Az eljárás korábban leírt (1) lépéséből következik, hogy $m \equiv r_1 \pmod a$. Ebből az 1.5.1. Állítás szerint az adódik, hogy a legnagyobb közös osztó nem változik: $(m, a) = (a, r_1)$.

Hasonlóan, a (2) lépés miatt $a \equiv r_2 \pmod{r_1}$, amiből ugyanazon logika mentén következik, hogy $(a, r_1) = (r_1, r_2)$.

Folytatva a sort, az egymást követő maradékos osztások során a legnagyobb közös osztó értéke végig megőrződik:

$(m, a) = (a, r_1) = (r_1, r_2) = \dots = (r_{k-1}, r_k)$

Azonban az algoritmus legutolsó, (k + 1) lépése szerint $r_{k-1} = t_{k+1} \cdot r_k + 0$. Ez azt jelenti, hogy $r_k$ maradék nélkül osztja az előző maradékot ($r_k \mid r_{k-1}$).

Mivel egy szám és annak többszörösének legnagyobb közös osztója maga a kisebbik szám, így $(r_{k-1}, r_k) = r_k$.

Ezzel tehát az állítást beláttuk: az eredeti számok legnagyobb közös osztója valóban megegyezik az eljárás végén kapott utolsó nemnulla maradékkal. □

2.2.3. Az algoritmus hatékonysága (1.6.5. Állítás)

1.6.5. Állítás:

Az Euklideszi algoritmus legföljebb $2 \cdot \lceil \log_2 a \rceil$ maradékos osztás után megáll.

Részletes Bizonyítás:

Vizsgáljuk meg az eljárás egy tetszőleges lépését: $r_{i-2} = t_i \cdot r_{i-1} + r_i$, ahol a korábbiak szerint $r_{i-2} > r_{i-1} > r_i$.

1. Itt tehát $t_i \ge 1$ (mivel $r_{i-2} > r_{i-1}$), amiből $r_{i-2} \ge r_{i-1} + r_i$ következik.

2. Ebből viszont $r_{i-1} > r_i$ miatt $r_{i-2} > 2r_i$ adódik.

Így az eljárás páros sorszámú soraiból (minden második lépésben legalább feleződik a maradék) az alábbi becsléssort kapjuk:

$a = r_0 > 2r_2 > 4r_4 > \dots > 2^s \cdot r_{2s}$

Az $s = \lceil \log_2 a \rceil$ választással $2^s \ge a$.

Indirekt ellentmondás:

Tegyük fel indirekt, hogy az eljárás az $r_{2s}$ maradékkal még nem ért véget. Ekkor a fenti becslés alapján a $0 < r_{2s} < \frac{a}{2^s} \le 1$ ellentmondást kapnánk (mivel nincs 0 és 1 közötti egész szám).

A bizonyítás ezzel kész. □

Mit jelent ez a gyakorlatban?

Ez a tétel garantálja, hogy még hatalmas számok esetén is (pl. 100 jegyű számok az RSA titkosításnál) az algoritmus pár száz lépésben végez. Mivel a lépésszám a számjegyei számával arányos, ez egy polinomiális futásidejű algoritmus.

2.3. Lineáris kongruenciák megoldása (1.6.5.)

A lineáris kongruenciák megoldhatóságát már vizsgáltuk az 1.4.2. Tételben, ahol megállapítottuk, hogy az $a \cdot x \equiv b \pmod m$ egyenlet akkor oldható meg, ha $(a, m) \mid b$. Az Euklideszi algoritmus segítségével azonban egy olyan hatékony módszert kaphatunk, amellyel magát a megoldást is kiszámíthatjuk.

Bemenet: $a, b$ és $m$ pozitív egészek;

Kimenet: A megoldáshalmaz $x \equiv c \pmod{m'}$ alakban, vagy „nincs megoldás”.

A számítás során feltételezhetjük, hogy $(a, m) = 1$, hiszen ha ez nem teljesülne, a kongruenciát az 1.4.2. Tétel alapján $(a, m)$-mel való osztással egy olyan $a'x \equiv b' \pmod{m'}$ feladattá alakíthatnánk, amelyre már $(a', m') = 1$ teljesül.

A módszer lényege:

Az eljárás során felírjuk az $mx \equiv 0 \pmod m$ (jelölése: $*$) és az eredeti $ax \equiv b \pmod m$ (jelölése: $B$) kongruenciákat. Ezután az Euklideszi algoritmus lépéseit követve, a kettővel korábbi kongruenciából kivonjuk az eggyel korábbi alkalmas többszörösét. Célunk, hogy az $x$ együtthatója fokozatosan csökkenjen, amíg el nem érjük az $x \equiv c \pmod m$ alakot.

Példa: $567x \equiv 123 \pmod{1238}$ levezetése

(*) $1238x \equiv 0$ $\pmod{1238}$
(B) $567x \equiv 123$ $\pmod{1238}$
(*) - 2·(B) : (1) $104x \equiv -246 \equiv \mathbf{992}$
(B) - 5·(1) : (2) $47x \equiv -4837 \equiv \mathbf{115}$
(1) - 2·(2) : (3) $10x \equiv \mathbf{762}$
(2) - 4·(3) : (4) $7x \equiv -2933 \equiv \mathbf{781}$
(3) - 1·(4) : (5) $3x \equiv -19 \equiv \mathbf{1219}$
(4) - 2·(5) : (6) $x \equiv -1657 \equiv \mathbf{819}$

Euklideszi algoritmus lépései:

$1238 = \mathbf{2} \cdot 567 + 104$

$567 = \mathbf{5} \cdot 104 + 47$

$104 = \mathbf{2} \cdot 47 + 10$

$47 = \mathbf{4} \cdot 10 + 7$

$10 = \mathbf{1} \cdot 7 + 3$

$7 = \mathbf{2} \cdot 3 + 1$

$3 = 3 \cdot 1 + 0$

* A félkövér számok mutatják, hányszorosát vonjuk ki az előző sornak.

Végeredmény:

$x \equiv 819 \pmod{1238}$

Mivel $(567, 1238) = 1$, ez a feladat egyetlen megoldása.


Általános algoritmus séma

(*) $m \cdot x \equiv 0 \pmod m$
(B) $a \cdot x \equiv b \pmod m$
(*) - $t_1 \cdot (B) : (1)$ $r_1 \cdot x \equiv -t_1 \cdot b \equiv c_1 \pmod m$
(B) - $t_2 \cdot (1) : (2)$ $r_2 \cdot x \equiv b - t_2 \cdot c_1 \equiv c_2 \pmod m$
(1) - $t_3 \cdot (2) : (3)$ $r_3 \cdot x \equiv c_1 - t_3 \cdot c_2 \equiv c_3 \pmod m$
⋮
(k) $r_k \cdot x \equiv c_{k-2} - t_k \cdot c_{k-1} \equiv c_k \pmod m$

Az eljárás végén $r_k = 1$, hiszen feltettük, hogy $(a, m) = 1$. Ezért a $(k)$ lépésben kapott kongruencia a feladat megoldását adja: $x \equiv c_k \pmod m$.

Helyesség és Bonyolultság:

Helyesség: A kongruenciákon végzett alapműveletekre vonatkozó szabályok miatt (1.3.3. Tétel) minden lépésben olyan kongruenciát kapunk, amelyet a bemenetként kapott feladat minden $x$ megoldása kielégít. Mivel $(a, m) = 1$ miatt a feladatnak egyetlen megoldása van, az utolsóként kapott $x \equiv c_k \pmod m$ valóban ezt a megoldást szolgáltatja.

Futásidő: Mivel továbbra is legföljebb $2 \cdot \lceil \log_2 a \rceil$ maradékos osztást végzünk (1.6.5. Állítás), az eljárás polinomiális futásidejű.

Interaktív Kongruencia Megoldó

Adja meg az $ax \equiv b \pmod{m}$ egyenlet paramétereit!

$\equiv$