Bevezetés a számításelméletbe II.

2002. április 11.

1. Ha $6x \equiv 42 \pmod{21}$, akkor az alábbiak közül mi igaz biztosan?
(a) $6x \equiv 0 \pmod{21}$
(b) $6x+2 \equiv 2 \pmod{21}$
(c) $12x \equiv 84 \pmod{21}$
(d) $3x \equiv 21 \pmod{21}$
(e) $2x \equiv 14 \pmod{21}$
(f) $2x \equiv 14 \pmod{7}$

2. Milyen maradékot adhat 45-tel osztva az $x$ szám, ha $12x\equiv 42 \pmod {45}$?

3. ZH! Bizonyítsuk be, hogy $37^{16}-1$ osztható $5$-tel.

4. HF, ZH! Legyenek $n$ és $m$ olyan pozitív egészek, melyekre $m$ osztója $n$-nek. Bizonyítsuk be, hogy $\phi(m)$ osztója $\phi(n)$-nek.



5. Tudjuk, hogy az $a$ egész számra teljesül, hogy ${a^{100} \equiv 5 \pmod{31}}$ és ${a^{101} \equiv 19 \pmod{31}}.$ Milyen maradékot ad 31-gyel való osztáskor az $a$ egész szám?

6. (a) Melyik a nagyobb, $10^{10^{10}}$ vagy $(10^{10})^{10}$?
(b) ZH! Határozzuk meg a $37^{39^{42}}$ utolsó két számjegyét.

7. Mely $n$-ekre lesz $\phi(n)$ prímszám?

8. ZH! Oldjuk meg az $6x+1\equiv 10$ $(mod \;\;15)$ kongruenciát.

9. Határozzuk meg az összes olyan természetes $m$ számot és $p$ prímszámot, melyre $\phi(pm)=\phi(m)$.

10. ZH! Határozzuk meg $303^{404}$ utolsó két számjegyét!



11. ZH! Milyen maradékot adhat 45-tel osztva az $x$ szám, ha $102x\equiv 40$ $(mod \;\;45)$

12. ZH! Bizonyítsuk be, hogy $\phi(n^3)=n^2\cdot \phi(n)$.

13. ZH! Legyen $p$ és $q$ két prímszám és $p>q$. Adjuk meg az összes olyan $p,q$ számpárt, melyre $q^p\equiv 2$ $(mod \;\;p)$.

14. ZH! Relatív prím-e a $2^{100}-1$ és $3^{100}-1$?

15. Keressük meg 7 azon pozitív többszöröseit, melyek 13-mal osztva 11-et adnak maradékul!

16. Bizonyítsuk be, hogy ha $d$ osztója $n$-nek, akkor $d- \varphi(d) \le n - \varphi(n)$.

17. ZH! Legyen $a$ egy 2001-hez relatív prím szám. Bizonyítsuk be, hogy ekkor $(a^{28}-1)(a^{24}-a^{22}-a^2+1)$ osztható 2001-gyel. ( $2001=3\cdot 23\cdot 29$)

18. Milyen maradékot adhat 72-vel osztva az $x$ szám, ha $18x\equiv 12$ $(mod \;\;48)$

19. * Mely $x$-ekre teljesül mindhárom alábbi kongruencia?
$3x \equiv 2 \;\;(mod\;\; 5)$
$4x \equiv 1 \;\;(mod\;\; 7)$
$5x \equiv 1 \;\;(mod\;\; 8)$

20. * Bizonyítsuk be, hogy $n^{7}+41n$ osztható $42$-vel, ha $n$ tetszoleges egész szám.