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

10. gyakorlat, 2005. április 22.

                                           Koblinger Egmont <egmont@cs.bme.hu>

Számelmélet II.

99. Milyen maradékot ad a 2 · 4 · 6 · . . . · 200 szorzat 101-gyel osztva?

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

101. Legyen m ≥ 3. Bizonyítsuk be, hogy m akkor és csak akkor prím, ha (m − 2)! ≡ 1 (mod m).

102. Teljes maradékrendszer-e modulo 77 az { 1, 11, 21, …, 761 } számhalmaz?

103. Redukált maradékrendszer-e modulo 32 az { 5, 15, 25, …, 155 } számhalmaz?

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

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

106. Milyen maradékot ad 37-tel osztva az a szám, melynek 10-es számrendszerbeli alakja 37 db egyesből áll?

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

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

109. Mennyi lehet az a, ha a^{1997} ≡ 4 (mod 81) ?

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

111. Biz. be, hogy ha n egész szám, a és b pedig nemnegatív egész számok, és n^{6a} + n^{6b} osztható 7-tel, akkor n is osztható 7-tel.

112. Mi 1997^{7^{2000}} utolsó két számjegye?

113. Biz. 7 osztja (5555^{2222} − 2)-t.

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

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

116. Legyen a p prím esetén a_{1}, a_{2}, …, a_{p−1} RMR (mod p). Biz: a_{1}^{p−2}, a_{2}^{p−2}, …, a_{p−1}^{p−2} szintén RMR (mod p).

117. Biz. minden n-re φ(n^{3}) = n^{2}φ(n).

118. Milyen n-ekre teljesül, hogy 2φ(n) = n?

119. Milyen n-ekre teljesül, hogy φ(7n) = 7φ(n)?

HF

120. Mennyi az 1993^{1993} szám 2004-gyel való osztáskor keletkező maradéka?

121. Az Euler–Fermat-tétel szerint az a és m pozitív egészekre, amennyiben azok relatív prímek, a^{φ(m)} ≡ 1 mod m. Keressünk olyan a és m számokat, melyek nem relatív prímek, de szintén fennáll rájuk a kongruencia.