Beugró - Számelmélet
1. Mondja ki a maradékos osztás tételét
Tétel: Maradékos osztás tétele
Tetszőleges \(a, b \in \Z\) és \(a, b \ne 0\) egyértelműen létezik \(q, r \in \Z\), hogy
\(a = b \cdot q + r\) és \(0 \le r < |b|\).
- q: kvóciens
- r: maradék
Maradékos osztás tétele - Példa feladatok
Példa feladat
Ossza el maradékosan a 18-at a 7-tel!
\(\underbrace{18}_{a} = \underbrace{7}_{b} \cdot 2 + 4\)
Bónusz példa feladatok by Katie
Maradékos osztás tétele - 1. bónusz példa
\(a = 123 \;\) és \(\; b = 10\)
\(q = \left\lfloor\dfrac{123}{10}\right\rfloor = \left\lfloor12,3\right\rfloor = 12\)
\(r = 123 \mod 10 = 3\)
\(123 = 10 \cdot \underbrace{12}_{q} + \underbrace{3}_{r}\)
Maradékos osztás tétele - 2. bónusz példa
\(a = 123 \;\) és \(\; b = -10\)
\(q = \left\lceil\dfrac{123}{(-10)}\right\rceil = \left\lceil-12,3\right\rceil = -12\)
\(r = 123 \mod (-10) = 3\)
\(123 = (-10) \cdot \underbrace{(-12)}_{q} + \underbrace{3}_{r}\)
Maradékos osztás tétele - 3. bónusz példa
\(a = -123 \;\) és \(\; b = 10\)
\(q = \left\lfloor\dfrac{(-123)}{10}\right\rfloor = \left\lfloor-12,3\right\rfloor = -13\)
\(r = (-123) \mod 10 = 7\)
\(-123 = 10 \cdot \underbrace{(-13)}_{q} + \underbrace{7}_{r}\)
Maradékos osztás tétele - 4. bónusz példa
\(a = -123 \;\) és \(\; b = -10\)
\(q = \left\lceil\dfrac{(-123)}{(-10)}\right\rceil = \left\lceil12,3\right\rceil = 13\)
\(r = (-123) \mod (-10) = 7\)
\(-123 = (-10) \cdot \underbrace{13}_{q} + \underbrace{7}_{r}\)
2. Definiálja a legnagyobb közös osztót
Definíció: Legnagyobb közös osztó
Legyenek \(a, b \in \Z\). A \(d \in Z\) nemnegatív szám az \(a\) és \(b\) legnagyobb közös osztója, ha
-
\(d \mid a\) és \(d \mid b\,\);
-
\(\forall \; k \in \Z\;\) esetén, ha \(k \mid a\), \(\;k \mid b\), akkor\(\;k \mid d\).
Jelölése: \(d = (a, b) = lnko(a, b) = gcd(a, b)\)
Definíció szerint \((0, 0) = 0\).
LNKO - Példa feladatok
Példa feladat
Mi lesz \(12\) és \(18\) legnagyobb közös osztója?
Jelöléssel: \((12, 18) =\, ?\)
A példát euklidészi algoritmussal oldom meg.
\(12 = 18 \cdot 0 + 12\)
\(18 = 12 \cdot 1 + 6\)
\(12 = 6 \cdot 2 + 0\)
Tehát \((12, 18) = 6\)
Bónusz példa feladatok by Katie
\((3, 12) = 3\)
Levezetve:
\(3 = 12 \cdot 0 + 3\)
\(12 = 3 \cdot 4 + 0\)
\((25, 45) = 5\)
Levezetve:
\(25 = 45 \cdot 0 + 25\)
\(45 = 25 \cdot 1 + 20\)
\(25 = 20 \cdot 1 + 5\)
\(20 = 5 \cdot 4 + 0\)
\((0, 5) = 5\)
Levezetve:
\(5 = 0 \cdot 0 + 5\)
\(0 = 5 \cdot 0 + 0\)
3. Mondja ki a lineáris diofantikus egyenletek megoldhatóságáról szóló tételt
Tétel: Lineáris diofantikus egyenletek megoldhatósága avagy bővített euklideszi algoritmus
Minden \(a, b, c \in \Z\) számok esetén pontosan akkor léteznek \(x, y \in \Z\), hogy \(x \cdot a + y \cdot b = c\), ha \((a, b) \mid c\).
Diofantosz - Példa feladatok
\(x_i = x_{i-2} - q_i \cdot x_{i-1}\)
\(y_i = y_{i-2} - q_i \cdot y_{i-1}\)
\(x' = x + k \cdot b\)
\(y' = y - k \cdot a\)
Példa feladat
Megoldható-e a \(12 \cdot x + 18 \cdot y = 5\) egyenlet? Ha igen, adjon megoldást, ha nem, indokoljon!
\((12, 18) = 6\;\) és \(\;6 \nmid 5\)
Az egyenlet megoldhatóságához teljesülnie kell annak, hogy \((a, b) \mid c\), azonban itt nem teljesül, ezért nem megoldható.
Bónusz példa feladat by Katie
Megoldható-e a \(351 \cdot x + 123 \cdot y = 3\) egyenlet? Ha igen, adjon megoldást, ha nem, indokoljon!
\(a = 351,\; b = 123,\; c = 3\)
A feladat megoldható, mert \(\;(351, 123) = 3\;\) és \(\;3 \mid 3\)
| \(i\) | \(r_i\) | \(q_i\) | \(x_i\) | \(y_i\) | \(x_i \cdot a + y_i \cdot b = r_i\) | Euklideszi |
|---|---|---|---|---|---|---|
| \(-1\) | \(351\) | - | \(1\) | \(0\) | \(1 \cdot 351 + 0 \cdot 123 = 351\) | - |
| \(0\) | \(123\) | - | \(0\) | \(1\) | \(0 \cdot 351 + 1 \cdot 123 = 123\) | - |
| \(2\) | \(\purple{105}\) | \(\pink{2}\) | \(1\) | \(-2\) | \(1 \cdot 351 - 2 \cdot 123 = 105\) | \(351 = 123 \cdot \pink{2} + \purple{105}\) |
| \(3\) | \(\purple{18}\) | \(\pink{1}\) | \(-1\) | \(3\) | \(-1 \cdot351 + 3 \cdot 123 = 18\) | \(123 = 105 \cdot \pink{1} + \purple{18}\) |
| \(4\) | \(\purple{15}\) | \(\pink{5}\) | \(6\) | \(-17\) | \(6 \cdot 351 - 17 \cdot 123 = 15\) | \(105 = 18 \cdot \pink{5} + \purple{15}\) |
| \(5\) | \(\purple{3}\) | \(\pink{1}\) | \(\bold{-7}\) | \(\bold{20}\) | \(-7 \cdot 351 + 20 \cdot 123 = 3\) | \(18 = 15 \cdot \pink{1} + \purple{3}\) |
| - | - | - | - | - | - | \(15 = 3 \cdot 5 + 0\) |
\(x = -7\;\) és \(\;x' = -7 + k \cdot 123\)
\(x = 20\;\) és \(\;x' = 20 - k \cdot 351\)
4. Definiálja a kongruencia relációt
Két számot azonosnak tekintünk, ha osztási maradékuk megegyezik.
Definíció: Kongruencia
Adott \(\; a, b, n \in \Z \;\) és \(\; n \ne 0 \;\) esetén
\(\; a \equiv b \mod n \;\) ha \(\; n \mid a - b \;\).
Szóval: \(a\) kongruens \(b\)-vel modulo \(n\)
Példa feladat
Mondjon példát két különböző \(x \in \Z\)-re, mely teljesíti az \(\;x \equiv 3 \mod 4\) relációt!
\(x \equiv 3 \mod 4\)
\(a = x,\; b = 3,\; n = 4\)
\(x \equiv 3 \mod 4 \Longleftrightarrow 4 \mid x - 3 \Longleftarrow x = 3 \lor x = 7\)