Kongruencia
5. Mondja ki és bizonyítsa a kongruencia mint egész számok közötti reláció tulajdonságára vonatkozó tételt
Tétel: Kongruencia, mint reláció
A kongruencia ekvivalencia reláció (azaz reflexív, tranzitív és szimmetrikus).
Bizonyítás: Kongruencia, mint reláció
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\;\)
6. Mondja ki és bizonyítsa az egész számok körében a kongruencia kompatibilitására vonatkozó tételt a műveletekkel
Tétel: A kongruencia kompatibilis (+; *)
Legyenek \(a, b, c, d, n \in \Z,\; n \ne 0\). Ekkor
(1) \(\;a \equiv b \mod n \;\;\text{és}\;\; c \equiv d \mod n \;\;\text{esetén}\;\; a + c \equiv b + d \mod n\;\).
(2) \(\;a \equiv b \mod n \;\;\text{és}\;\; c \equiv d \mod n \;\;\text{esetén}\;\; a \cdot c \equiv b \cdot d \mod n\;\).
Bizonyítás: A kongruencia kompatibilis (+; *)
\(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.
Lineáris kongruenciák - Tétel (bizonyítéssal)
8. Mondja ki és bizonyítsa a lineáris kongruenciák megoldására vonatkozó tétel!
9. Mondja ki és bizonyítsa a kongruenciák egyszerűsítésére vonatkozó tételt!
Tétel: Lineáris kongruenciák
Legyenek \(\;a, b, c, n \in \Z,\; n \ne 0\)
Ekkor \(\;\;\pink{a} \cdot \green{b} \equiv \pink{a} \cdot \orange{c} \mod n \Longleftrightarrow \green{b} \equiv \orange{c} \mod \dfrac{n}{(\pink{a}, n)}\)
Bizonyítás: Lineáris kongruenciák
- 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.