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

9. gyakorlat, 2005. április 15.

                             Koblinger Egmont <egmont@cs.bme.hu>

Számelmélet I.

81. Az x ≡ 2(3) és az x ≡ 5(6) állítások közül melyik következik a másikból? Ami nem következik, arra mutassunk ellenpéldát!

82. Melyek igazak az alábbi állítások közül?

(a) k | n, a ≡ b (mod n) ⇒ a ≡ b (mod k)

(b) k | n, a ≡ b (mod k) ⇒ a ≡ b (mod n)

(c) a ≡ b (mod k), a ≡ b (mod n) ⇔ a ≡ b (mod kn)

(d) a ≡ b (mod k), a ≡ b (mod n) ⇔ a ≡ b (mod [k, n])

(e) a ≡ b (mod n) ⇔ ka ≡ kb (mod kn)

(f) a ≡ b (mod n), c ≡ d (mod k) ⇒ ac ≡ bd (mod kn)

(g) a^{2} ≡ b^{2} (mod n) ⇔ a ≡ ±b (mod n)

(h) a^{2} ≡ b^{2} (mod 101) ⇔ a ≡ ±b (mod 101)

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

84. Mutassunk három olyan relatív prím számot, melyek közül semelyik kettő nem relatív prím.

85. Bizonyítsuk be, hogy nem létezik olyan 3 jegyű szám, melynek osztóinak száma osztható volna 11-gyel.

86. Bizonyítsuk be, hogy végtelen sok n-re teljesül, hogy d(n + 1) ≥ 2d(n).

87. Bizonyítsuk be, hogy minden a, b egészre d(ab) ≤ d(a)d(b) és egyenlőség pontosan akkor teljesül, ha a és b relatív prímek.

88. Bizonyítsuk be, hogy minden a egészre d(a) ≤ 2\sqrt{a}.

89. Két pozitív egész szám összege prím, az egyik a másik 30-szorosa. Mik lehetnek ezek?

90. Bizonyítsuk be, hogy ha 2^{n} − 1 prím, akkor n is prím.

91. Biz. tetszőleges n természetes számra n^{5} − 5n^{3} + 4n osztható 120-szal.

92. Oldjuk meg az 5x ≡ 8 (mod 17) kongruenciát.

93. Mely pozitív egész számoknak van ugyanannyi páros osztója, mint páratlan?

94. Biz. tetszőleges n természetes szám mellett n(n^{2} + 5) osztható 6-tal.

95. Legyen n páratlan egész szám, amely nem osztható egyetlen prímszám négyzetével sem. Bizonyítsuk be, hogy n osztóinak átlaga egész szám!

96. Igazoljuk, hogy ha az a szám osztóinak a száma páratlan, akkor minden n > 1 egészre a^{n} osztóinak a száma is páratlan.

HF

97. Oldjuk meg a kongruenciát: 170x ≡ 78 (mod 2006).

98. Melyik az a legkisebb szám, melynek 10 osztója van? (Csak a pozitív osztókat vesszük figyelembe.)