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

7. gyakorlat, 2006. április 5.

                                     Koblinger Egmont <egmont@cs.bme.hu>

Számelmélet

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

84. Legyen n osztható k-val. Bizonyítsuk be, hogy φ(n) is osztható φ(k)-val.

85. Teljes maradékrendszer-e (modulo 77) az 1, 11, 21, … 761 számhalmaz?

86. Redukált maradékrendszer-e (modulo 32) az 5, 15, 25, …, 155 számhalmaz?

87. Keressük meg az alábbi két számtani sorozat első közös elemét: 30, 50, 70, …; illetve 12, 25, 38, … 88. Biz. minden n-re φ(n^{3}) = n^{2}φ(n).

89. Mivel kongruens mod 77 az 1998^{1979} szám?

90. Mi 7^{6^{5^{4^{3^{2}}}}} utolsó számjegye a 10-es számrendszerben?

91. Kiszámítandó (((43^{43})^{43})^{43})^{43} modulo 49.

92. Biz. be, hogy a 10^{n} + 3 alakú számok között végtelen sok osztható 13-mal.