15. Maradékos osztás, Euklideszi algoritmus

Question 1

Maradékos osztás:

Answer 1

• Minden $a∈ \Z$ és $b>0$ egész számokhoz létezik olyan, egyértelműen meghatározott $q$ és $r$ a szám, amelyre
  $a = b · q + r$ és $0 ≤r<b$.

Question 2

Euklideszi algoritmus:

Answer 2

• Adott $a,b ∈ \Z$ számokra ismételten alkalmazzuk a maradékos osztás tételét: ha $|a| ≤|b|$ akkor osszuk el az $a$ számot $b$-vel, majd $b$-t a maradékkal, stb. mindig az osztót a maradékkal. Azaz legyen:

$a = b · q_1 + r_1, 0 < r1 < |b|,$

$b = r_1 · q_2 + r_2, 0 < r_2 < r_1,$

$r_1 = r_2 · q_3 + r_3, 0 < r_3 < r_2,$

$r_2 = r_3 · q_4 + r_4, 0 < r_4 < r_3,$

. . .

$r_{i−2} = r_{i−1} · q_i + r_i , 0 < r_i < r_{i−1},$

. . .

$r_{m−2} = r_{m−1} · q_m + r_m, 0 < r_m < r_{m−1},$

$r_{m−1} = r_m · q_{m+1}.$

Ez az algoritmus akkor áll meg amikor 0-t kapunk, azaz $r_{m+1} = 0$. Ekkor $lnko(a,b)=r_m$ Vagyis a “legutolsó nem nulla maradék”.

• Az euklideszi algoritmus legfeljebb annyi lépésig tart, mint amennyi b számjegyei számának összege, azaz $m<5·log_{10}|b|.$

Question 3

lineáris Diofantoszi egyenletek

Answer 3

• Legyenek adottak az a1, …, an ∈ Z számok, és keresendők olyan x1, …, xn ∈ Z egész számok, melyekre$a_1x_1 + … + a_nx_n = c.$A fenti egyenltete n-változós lineáris Diophantoszi (Diophantikus) egyenletnek hívjuk.
• szükséges feltétele: Az egyenlet akkor és csak akkor oldható meg, ha$lnko(a_1, …, a_n)|c.$Biz: A fenti állítás szükségességét egyszerűen beláthatjuk: d=lnko(a1, .., an) esetén nyilván$d|a_1x_1 + … + a_nx_n$hiszen $x_1, …, x_n ∈ \Z$ egész számok.
• $ax+by=c$ kétismeretlenes Diophantikus egyenletet oldjuk meg, ahol a,b,c ∈ Z adott számok, teljesül lnko(a, b)|c feltétel, és keresendő x,y∈ d|c kell hogy legyen, külön[1]ben nem teljesül hogy lnko(a,b)=d.$ax+by=c$$ax’+by’=d$ (beszorzunk c/d-vel)$a(x’· \frac c d )+b(y’· \frac c d )=c$(van egy feladat a könyv (Szalkai-Dósa könyv)40. oldalán hozzá)

Question 4

Kongruencia def:

Answer 4

• Tetszőleges a,b,m ∈ Z, m6=0 egész számokra jelölje$a≡_mb$ vagy $a≡b(mod$ $m)$(olvasd: “a konruens b-vel modulo m”) az “a és b ugyanazt a maradékot adják m-el osztva” relációt.
• Def: Tetsz $a,m∈ \Z$ a-nak osztási maradéka $r∈ \N(|r|<|m|)$$a=m·x+r$ valamely $x∈ \Z$ számra. Pl: $m=19$, $21 ≡ 2 ≡ −17$
• Tétel: Tetszőleges (rögzített) $m∈ \Z$, $m \neq 0$ számra, valamint bármely $a,b,c,d∈ \Z$ számokra

Ha $a≡_mb$ és $c≡_md$

Akkor $a ± c≡_m b ± d$ és $a·c ≡_m b·d$

Question 5

Elsőfokú kongruencia egyenletek:

Answer 5

• Az $ax≡b$ $(mod$ $m)$ kongruencia-egyenleteket (a,b,m adott, x keresett) elsőfokú vagy lineáris kongruenciának nevezzük. Ennek az egyenletnek pontosan akkor van megoldása, ha $ax=my+b$, azaz $ax-my=b$, vagyis visszavezettük Diaphontikus egyenletre, amit Euklidesz algoritmusával meg tudunk oldani: A kongruencia-egyenletnek pontosan akkor van megoldása, ha $lnko(a,m)|b$. Következmény: Ha a és m relatív prímek, akkor bármely $b∈ \Z$ esetén van megoldása a lineáris kongruenciá

Question 6

Kínai maradéktétel:

Answer 6

• Probléma: Adott $m_1, m_2, …, m_r, a_1, a_2, …, a_r ∈ \Z$ egész számok esetén van-e az$x≡ a_1 (mod$ $m_1)$$x≡ a_2 (mod$ $m_2)$$…$$x≡ a_r (mod$ $m_r)$ú.n. szimultán kongruenciarendszernek $x∈ \Z$ gyöke?
• Tétel: Ha az mi modulusok páronként relatív prímek, akkor a kongruenciarendszernek bármilyen $a_1, a_2, …, a_r ∈ \Z$ egész számok esetén pontosan egy $x$ gyöke van$(mod$ $M)$ ahol $M=lkkt(m_1, m_2, …, m_r)$.