Mat-tanári gyakorlat, első évfolyam, első félév Hetedik alkalom — gyakorló feladatok kongruenciákra

1. Oldjuk meg az alábbi kongruenciákat:

a) 7x ≡ 3 (17).

b) 152x ≡ 88 (66).

c) 555x ≡ 5555 (55555).

2. Határozzuk meg azt a két legkisebb pozitív egész számot, melynek 13-szorosa a hetes számrendszerben felírva 43-ra végződik.

3. Mely c egészekre teljesül, hogy c^{2} + 1 | c^{3} + 1?

4. Legyenek a és b egészek. Mutassuk meg, hogy 2a + 3b akkor és csak akkor osztható 17-tel, ha 9a + 5b osztható 17-tel.

5. Bizonyítsuk be, hogy a^{3} − b^{3} és a − b ugyanazt a maradékot adja 6-tal osztva.

6. Bizonyítsuk be, hogy 23 | 61^{k+1} + 11^{k}7^{2k}3^{3k}2^{5k+3}.

7. Adjuk meg 999^{777^{888}} utolsó három számjegyét a tizes számrendszerben.

8. Számítsuk ki 3^{279} utolsó két jegyét a tizes számrendszerben.

9. Legyen p páratlan prímszám. Milyen maradékot ad p-vel osztva \binom{2p}{p}?

10. Bizonyítsuk be, hogy ha p prím, akkor

\binom{n}{p} ≡ [\frac{n}{p}] (p)

(itt [x] az x egész része, azaz az x-nél nem nagyobb egészek legnagyobbika).

11. Legyen a, b, c, d, n, m ∈ ℤ, m, n > 0, n | m. Mely állítások igazak az alábbiak közül? a) a ≡ b (m) ⟹ a ≡ b (n). Igaz-e a megfordítás?

b) a ≡ b (m) és c ≢ d (m) ⟹ a + c ≢ b + d (m).

c) a ≡ b (m) és c ≢ d (m) ⟹ ac ≢ bd (m).

d) a ≢ b (m) és c ≢ d (m) ⟹ a + c ≢ b + d (m).

e) A ≢ (m) reláció tranzitív.

12. Legyen n pozitív egész. Mely k értékekre szabad „k-adik gyököt vonni” az a^{k} ≡ b^{k} (2^{n}) kongruenciából tetszőleges páratlan a, b esetén?

13. Igazoljuk, hogy ha k és n páratlan természetes számok, akkor 1^{k} + 2^{k} + ⋯ + (n − 1)^{k} osztható n-nel. Páros n-re milyen maradékot kapunk?

14^{∗}. Az úttörőtábor gyülekező terét m fa állja körbe, mindegyiken egy mókus ül. A mókusok össze akarnak gyűlni egy fán, de csak úgy változtathatják a helyüket, hogy mindig egyszerre két mókus ugrik át a szomszédos fára, ellenkező körüljárási irányban. Milyen m esetén tudnak összegyűlni a mókusok?