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

9. gyakorlat, 2007. április 11.

                                 Koblinger Egmont <egmont@cs.bme.hu>

Számelmélet II.

97. Oldjuk meg a 400x ≡ 14 (mod 18) kongruenciát, vagyis adjuk meg az azt kielégítő x(-ek) 18-cal adott maradékát.

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

98. Biz. tetszőleges a természetes számra (a^{2} + 3a + 1)^{2} − 1 osztható 24-gyel.

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

100. A perzsa sahnak van 100 titkos cellája, és 100 kíváncsi felesége. Az ajtók zárva vannak, és a kulcsok egyszeri elfordításával nyílnak, a következőre záródnak, és így tovább. A feleségek természetesen megpróbálják kinyitni a cellákat, mégpedig a következő módon: az i-edik feleség minden i-edik ajtó kulcsán fordít egyet. Melyik cellák fognak kinyílni végül? És ha az i-edik feleség minden i-edik kulcson i-t fordít?

101. Számítsuk ki az euklideszi algoritmus segítségével 504 és 372 legnagyobb közös osztóját.

102. Mennyire hatékony az euklideszi algoritmus? És a „módosított” euklideszi algoritmus, amelyik mindig kivonja a nagyobb számból a kisebbet?