1. cvičení z MB154, podzim 2021
Příklad 1. Dokažte, že pro všechna celá čísla n platí:
• n2 dává zbytek 0 nebo 1 po dělení 4;
• n2 dává zbytek 0, 1 nebo 4 po dělení 8. (Buď je n = 2k nebo n = 2k + 1.)
Příklad 2. Spočtěte největší společné dělitele (89, 55), (157, 58), poté u prvního ukažte, jak lze výpočet zkrátit s použitím záporných zbytků.
Příklad 3. Spočtěte Bezoutovy koeficienty pro (157, 58) z minulého příkladu zpětným dosazováním a pak úpravou tabulky (matice)
1  0 157 0   1 58
Dále spočtěte Bezoutovy koeficienty pro (123, 91), stačí už pouze druhou metodou.
Příklad 4. Zjistěte, pro která přirozená čísla n je číslo n3 — n2 + 2n + 1 dělitelné číslem n — 2. (Dělení polynomů se zbytkem - není tak dobré jako dělení čísel se zbytkem, ale tady k výsledku dospěje.)
Příklad 5. Zjistěte, pro která přirozená čísla n je číslo 7n + l dělitelné číslem 3n + 4. (Bude to právě tehdy, když bude dělitelné 3(7n + 1), po pravdě stačí snazší implikace.)
Příklad 6. Nalezněte nej většího společného dělitele (263 — 1, 228 — 1). (Ve skutečnosti základ 2 není podstatný, lze přejmenovat na n a použít metodu dělení polynomů se zbytkem.)
Označme n-té Fibonacciho číslo Fn, tj. F0 = 0, F\ = 1, Fn = Fn_i + Fn_2-
Příklad 7. Najděte největší společné dělitele (Fn, Fn_i), (Fn, Fn_2), (Fn, Fn_3), (Fn, Fn_4); kdybyste se nudili, tak (F2n, Fn).
i