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

8. gyakorlat, 2007. április 4.

                                     Koblinger Egmont <egmont@cs.bme.hu>

Számelmélet

74. 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!

75. 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)

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

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

78. Mely k számokra igaz, hogy tetszőleges k darab pozitív egész szorzata megegyezik legnagyobb közös osztójuk és legkisebb közös többszörösük szorzatával?

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

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

81. 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.

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

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

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

85. Maximum hány szám adható meg az {1, 2, …, 2n} halmazból úgy, hogy egyik se legyen osztója semelyik másiknak?

86. Bizonyítsuk be, hogy ha (a, m) = 1, (b, m) = 1 és ax ≡ b (mod m) valamint by ≡ a (mod m), akkor xy ≡ 1 (mod m) is igaz.

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

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

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

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

91. 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!

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

93. Legyen p prímszám. \binom{2p}{p} ≡ ? (mod p)

94. Oldjuk meg: 15x ≡ 2 (mod 5) és 7x ≡ 1 (mod 13)

95. Oldjuk meg: 4x ≡ 2 (mod 6) és 2x ≡ 1 (mod 5)

96. Keressük meg az alábbi két számtani sorozat első közös elemét: 30, 50, 70, …; illetve 12, 25, 38, …