Mat-tanári gyakorlat, első évfolyam, első félév Harmadik alkalom

1. Végezzük el az euklideszi algoritmust a 220 és 184 számokra, majd a kapott eredményt a tanult visszahelyettesítési eljárással állítsuk elő 220x + 184y alakban (ahol x, y ∈ ℤ). Tegyük meg ugyanezt a 9991 és 3589, illetve a 12543 és a 29447 számokkal is.

2. Rendelkezésünkre áll egy 17 literes és egy 21 literes kanna. Ezeket akárhányszor megtölthetjük a csapnál, és a tartalmukat (teljes egészében) beönthetjük egy tartályba. Kimérhető-e ezzel a módszerrel 50 liter, illetve 400 liter víz? Ha azt is megengedjük, hogy a tartályból kimerjünk vizet (21 illetve 17 literes egységenként), betölthető-e 50 liter víz?

3. Legyenek a, b pozitív egészek, (a, b) = 7. Milyen értékeket vehet fel (a + b, a − b)?

4. Igazoljuk, hogy ha a és b egészek, akkor (a, b) = (11a + 5b, 9a + 4b).

5. Legyen n egész szám. Határozzuk meg (n^{2} + 1, 2n^{2} + 9) lehetséges értékeit.

6. Legyen d = (a, b), és tegyük fel, hogy u és v olyan egészek, amelyekre ua + vb = d. Mi lehet ekkor u és v legnagyobb közös osztójának az értéke?

7. Legyenek a és b pozitív egészek, (a, b) = 1. Igazoljuk, hogy létezik olyan pozitív x és y egész, hogy ax − by = 1.

8^{∗}. Határozzuk meg 2^{2^{k}} + 1 és 2^{2^{m}} + 1 legnagyobb közös osztóját, ha k ≠ m nemnegatív egészek. Mutassuk meg az eredmény felhasználásával, hogy végtelen sok prímszám van.

9^{∗}. Mutassuk meg, hogy bárhogy is veszünk egymás utáni négy, hat, sőt 16 pozitív egész számot, van közöttük olyan, ami az összes többihez relatív prím.

10^{∗}. Legyenek a ≥ b > 0 egészek. Mutassuk meg, hogy az (a, b) kiszámítására szolgáló euklideszi algoritmus során

a) ha mindegyik maradékos osztásnál a legkisebb abszolút értékű maradékot vesszük figyelembe, akkor az eljárás legfeljebb 1 + log_{2} b lépésben véget ér;

b) az eljárás akkor is véget ér legfeljebb 1 + 2 log_{2} b lépésben, ha végig nemnegatív maradékokkal számolunk.

11^{∗}. Az asztalon sorba raktunk kétfilléreseket. Ketten a következő játékot játsszák: felváltva kiválasztanak egy, a fej oldalával felfelé álló érmét, és ezt, valamint az összes tőle jobbra lévő pénzdarabot az ellenkező oldalára fordítják. Az veszít, aki már nem tud lépni. Bizonyítsuk be, hogy a játék véges sok lépésben véget ér. A kezdeti állapotról hogyan dönthető el, melyik játékosnak van nyerő stratégiája?

Gyakorló feladatok

12. Egy királyfi hét- és tízfejű sárkányokkal csatázott, és levágta mind a 116 fejüket. Hány sárkányt ölt meg?

13. Legyenek a és b olyan egészek, amelyeknek a legnagyobb közös osztója 14. Mi lehet ekkor (3a + 2b, 4a + 3b), illetve (a + b, 5a + 3b) értéke?

14. Bizonyítsuk be az (a, b) = (a − kb, b) azonosságot (a, b, k ∈ ℤ).

15. Mutassuk meg, hogy tetszőleges a, b, c egészekre (ab, ac) = a(b, c) és (a^{2}, b^{2}) = (a, b)^{2}.