Kongruencia

Három dolognak kell teljesülnie ahhoz, hogy valami ekvivalencia reláció legyen. Reflexivitás, tranzitivitás és szimmetria.

Reflexivitás

\(\;\bold{a \equiv a \mod n}\;\)

\(\;n \mid a - a = 0\;\) (minden szám osztója a 0-nak kivéve önmaga)

Tranzitivitás

\(\;\bold{a \equiv b \mod n\;\; \text{és} \;\;b \equiv c \mod n\; \Longrightarrow \; a \equiv c \mod n}\)

\(\;n \mid a - b, \;\; n \mid b - c \;\Longrightarrow\; n \mid (a - b) + (b - c) = a - c\;\)

Szimmetria

\(\;\bold{a \equiv b \mod n \;\Longrightarrow\; b \equiv a \mod n}\;\)

\(\;n \mid a - b \;\Longrightarrow\; n \mid (-1) \cdot (a \cdot b) = b - a\;\)

\(a \equiv b \mod n \;\Longrightarrow\; n \mid a - b\)

\(c \equiv d \mod n \;\Longrightarrow\; n \mid c - d\)

Összeadás

\(n \mid (a - b) + (c - d)\)

\((a - b) + (c - d) = (a + c) - (d + d)\)

\(n \mid (a + c) - (b + d) \;\Longrightarrow\; a + c \equiv b + d \mod n\)

Szorzás

\(a \cdot c - b \cdot d = a \cdot c - \orange{b \cdot c} + \orange{b \cdot c} - b \cdot d = c \cdot (a - b) + b \cdot (c - d)\)

Mindkét tag osztható \(n\)-nel, ezért az összegük is.

A tétel formális matematikai jelölésekkel: \(\exist x, y \in \Z:\; x \cdot a + y \cdot b = c \Longleftrightarrow (a, b) \mid c\)

Szükséges feltétel (\(\Rightarrow\))

TFH. \(\;x \cdot a + y \cdot b = c\)

Ekkor \(\;(a, b) \mid a,\; (a, b) \mid b \Longrightarrow (a, b) \mid x \cdot a + y \cdot b = c\)

Elégséges feltétel (\(\Leftarrow\))

TFH. \(\;(a, b) \mid c\;\) teljesül.

Oldjuk meg a következő egyenletet:

\(x' \cdot a + y' \cdot b = (a, b)\)

\(\underbrace{\dfrac{c}{(a, b)} \cdot x'}_x \cdot a + \underbrace{\dfrac{c}{(a, b)} \cdot y'}_{y} \cdot b = (a, b) \cdot \dfrac{c}{(a, b)} \quad\) (beszorozzuk)

Ekkor \(\,x, y \in \Z\;\) megoldása lesz az egyetletnek.

\(x = \dfrac{c}{(a, b)} \cdot x'\;\) és \(\;y = \dfrac{c}{(a, b)} \cdot y'\)

A megoldáshoz hívjuk segítségül az euklideszi algoritmust.

\(x_{-1} = 1,\; x_0 = 0 \;\) és \(\; 1 \le i \le n \;\Longrightarrow\; x_i = x_{i-2} - q_i \cdot x_{i-1}\)

\(x_{-1} = 0,\; x_0 = 1 \;\) és \(\; 1 \le i \le n \;\Longrightarrow\; y_i = y_{i-2} - q_i \cdot y_{i-1}\)

• \(1 \le i \;\Longrightarrow\; x_i \cdot a + y_i \cdot b = r_i\)

• \(i = n \;\Longrightarrow\; x_n \cdot a + y_n \cdot b = r_n = (a, b)\)

• \(i \in \{-1; 0\}\) esetén

  • \(r_{-1} = a = 1 \cdot a + 0 \cdot b\)
  • \(r_0 = b = 0 \cdot a + 1 \cdot b\)

\(r_i = r_{i-2} - r_{i-1} \cdot q_i =\)

\(= r_i = \underbrace{(x_{i-2} \cdot a + y_{i-2} \cdot b)}_{r_{i-2}} - q_i \cdot \underbrace{(x_{i-1} \cdot a + y_{i-1} \cdot b)}_{r_{i-1}} =\)

\(= r_i = a \cdot \underbrace{(x_{i-2} + q_i \cdot x_{i-1})}_{x_i} + b \cdot \underbrace{(y_{i-2} + q_i \cdot y_{i-1})}_{y_i} =\)

\(= a \cdot x_i + b \cdot y_i\)

\(i = n \;\Longrightarrow\; x_n \cdot a + y_n \cdot b = r_n = (a, b)\)

Azaz \(\;x' = x_n\;\) és \(\;y' = y_n\)

• Legyen \(\;d = (a, n)\)
• TFH. \(\;n \mid a \cdot b - a \cdot c \;\Leftrightarrow\; n \mid a \cdot (b - c)\)

Ekkor \(\;\dfrac{n}{d} \cdot d \;\mid\; \dfrac{a}{d} \cdot d \cdot (b - c) \quad\) (bűnbánó matematikus trükköt csinálunk)

Azaz \(\;\exist \, \purple{k} \in \Z\), hogy \(\;\purple{k} \cdot \dfrac{n}{d} \cdot d = \dfrac{a}{d} \cdot d \cdot (b - c) \;\Longrightarrow\; \dfrac{n}{d} \;\mid\; \dfrac{a}{d} \cdot (b - c)\)

Azonban \(\dfrac{n}{d}\) és \(\dfrac{a}{d}\) relatív prímek, mert \(\;d = (a, n)\).

Így \(\;\dfrac{n}{d} \mid (b - c) \;\Leftrightarrow\; \dfrac{n}{(a, n)} \mid (b - c)\).

A másik irány triviális.