Kategória:	Bizonyítás	Évfolyam:	9.
Kulcsszó:	Lineáris kongruenciák	Lektorálás:	Nem lektorált

A lineáris kongruencia

Általános levezetés

$ax \equiv b \mod c$

A bal oldal osztható $(a; c)$ -val, mert $(a; c)|a$ . A jobb oldalon $c$ is osztható $(a; c)$ -val. Így akkor és csak akkor lehet megoldása a kongruenciának, hogyha $(a; c)|b$ (később belátjuk, hogy ilyenkor mindig van megoldás). Ha ez fennáll, akkor $(a; c)$ -val leosztjuk a kongruenciát.

$a'x \equiv b' \mod c'$

$a'= \frac{a}{(a; c)} \qquad b'= \frac{b}{(a; c)} \qquad c'= \frac{c}{(a; c)}$

Ekkor nyilvánvalóan $(a'; c')=1$ , tehát pontosan egy megoldás létezik $\mod c'$ , mivel ez egy teljes maradékrendszer. Így $(a; c)$ darab megoldás van $\mod c$ . Az $a'x \equiv b' \mod c'$ alak egyenértékű az $a'x+c'y=b'$ alakkal.

Innentől a levezetés részletesen megtalálható "Az elsőfokú diofantoszi egyenlet" című bizonyításnál, így a következőkben csak nagyvonalakban vázolom föl a bizonyítás további részét.

Az euklideszi algoritmus segítségével megkeressük az $a'k+c'l=1$ egyenlet $k_0$ és $l_0$ megoldását. Ebből $x_0=b'k_0$ és $y_0=b'l_0$ . Ezek az $a'x_0+c'y_0=b'$ egyenlet megoldásai. Ezt kongruenciaalakba átírva: $x \equiv x_0 \mod c'$ .

Az eredeti kongruenciára így a (legnagyobb közös osztóval történő beszorzás után) $(a; c)$ számú megoldás van:

$x \equiv \begin{cases} x_0 \\ x_0+c' \\ x_0+2c' \\ \vdots & \mod c\\ x_0+\big[ (a; c)-3 \big]c' \\ x_0+\big[ (a; c)-2 \big]c' \\ x_0+\big[ (a; c)-1 \big]c' \end{cases}$

Kezdés

Cikkek

Extrák

Egyéb

Keresés

Legújabb cikkek

Támogató

Szabványok

A lineáris kongruencia

Általános levezetés