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

2002. április 4.

1. (a) Határozzuk meg az 504 és a 372 prímtényezős felbontását!
(b) Mennyi $(504, 372)$? És $lkkt(504, 372)$?
(c) Az Euklideszi algoritmussal is határozzuk meg $(504, 372)$-t!
(d) Írjuk fel $(504, 372)$-t $504x+372y$ alakban!
(e) Mennyi $d(504)$ és $\sigma(504)$?

2. Legyen $a$ és $b$ páratlan. Mennyi $(a^2 + b^2 , 4)$?

3. Van-e olyan pozitív egész $a,b$ pár, hogy $(a,b) = 3$ és $a + b = 100$? És olyan, hogy $(a,b)=5$ és $a + b = 100$? Ahol igen, ott hányféle?

4. ZH! Egy XX. században született emberről azt tudjuk, hogy épp nagyapja 59. születésnapján született és hogy kettejük születési évszámai nem relatív prímek. Mikor született az ember?

5. ZH! Melyik az a legkisebb pozitív háromjegyű szám, amelyiknek ötször annyi páros osztója van, mint páratlan?

6. HF, ZH! Legyen $n$ pozitív egész szám, melynek ismerjük $n=\prod_{i=1}^k p_i^{\alpha_i}$ prímtényezos felbontását.
Mennyi a

$$\sum_{d_i\vert n} {\frac{1}{d_i}}$$

érték, vagyis hogyan számítható ki az $n$ szám osztói reciprokának az összege?

7. ZH! Legyen $a$ páratlan, $b$ pedig páros szám. Igazoljuk, hogy ha $a^2+b^2$ négyzetszám, akkor $b$ osztható néggyel.

8. HF Bizonyítsuk be, hogy $d(n+1)\geq 2d(n)$ végtelen sok $n$-re teljesül.

9. HF, ZH! Legyen $p$ 7-hatvány, $q$ pedig 5-hatvány. Bizonyítsuk be, hogy léteznek olyan $k$ és $l$ pozitív egészek, hogy ha egy $p$-fejű sárkány minden fejének $k$ darab és egy $q$ fejű sárkány minden fejének $l$ darab almát adunk, akkor valamelyik sárkánynak épp egy almával jut több!



10. Határozzuk meg az Euklideszi algoritmussal $(2394,1785)$-t, majd írjuk fel $2394x+1785y$ alakban.

11. ZH! Egy 2000-ben születo embernek 90 éves koráig hány olyan születésnapja lesz, amikor az életkora osztója az aktuális évszámnak?

12. Maximum hány szám választható ki $1$-tol $2n$-ig úgy, hogy közülük semelyik ketto se legyen relatív prím?

13. Melyek azok a $p$ prímszámok, amelyekre $p+10$ és $p+14$ is prímszám?

14. ZH! Hány olyan (pozitív) osztója van 3960-nak, amely 30 többszöröse?

15. ZH! Határozzuk meg az összes olyan $1< n\leq 100$ egész számot, amelyekre teljesül, hogy $n$ osztóinak száma háromhatvány.

16. * Egy perzsa sahnak száz felesége és száz rabja van, utóbbiak külön cellákban sínylődnek. A sah születésnapján a kedvenc feleség minden zárka zárján fordít egyet, a második kedvenc feleség minden másodikon kettőt, az $i$-edik minden $i$-ediken $i$-t. A zárak egy fordításra nyílnak, újabbra bezárulnak. Kérdés, hogy mely cellák lesznek nyitva a nap végén.

17. ZH, * Legyenek $k$ és $n$ olyan pozitív egészek, amelyekre $k<n$. Mi a legnagyobb közös osztója az $n!+k$ és az $(n+1)!+k$ számoknak?

18. *Bizonyítsuk be, hogy minden $a,b$ pozitív egészre $d(ab)\leq d(a)d(b)$ és egyenloség pontosan akkor teljesül, ha $a$ és $b$ relatív prímek!