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

10. gyakorlat, 2007. április 18.

                                      Koblinger Egmont <egmont@cs.bme.hu>

Számelmélet III. – Csoportelmélet

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

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

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

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

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

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

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

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

111. Adjuk meg az összes 1, 2, 3, illetve 4 elemű nem izomorf csoport művelettábáját.

112. Értelmezzük az egész számok halmazán az a ⋆ b = a + b + 1 képlettel megadott műveletet. Mutasd meg, hogy (ℤ, ⋆) csoport. Milyen korábbról ismert csoporttal izomorf (ℤ, ⋆)?

113. Határozzuk meg az alábbi alakzatok szimmetriacsoportját.

(a) szabályos háromszög;  (c) téglalap;  (e) kocka;
(b) paralelogramma;  (d) deltoid;  (f) tetraéder.

114. A G csoport e egységére és x, y elemeire x^{2} = e és xyx^{−1} = y^{3}. Bizonyítsuk be, hogy y^{8} = e.

115. Az alábbi következtetések közül melyek teljesülnek minden csoportban?

(a) ax = ay ⇒ x = y;  (d) abx = aby ⇒ x = y;  (g) ax = 1 ⇒ x = a^{−1};
(b) xa = ya ⇒ x = y;  (e) axb = ayb ⇒ x = y;  (h) abx = 1 ⇒ x = a^{−1}b^{−1};
(c) xa = ay ⇒ x = y;  (f) bxa = ayb ⇒ x = y;  (i) abx = 1 ⇒ x = b^{−1}a^{−1}.

116. Legyen a_{1}, … a_{φ(m)} az m-nél kisebb, m-hez relatív prím pozitív egészek halmaza. Hasonlóan legyen b_{1}, … b_{φ(n)} az n-nél kisebb, n-hez relatív prím pozitívak halmaza.

(a) Mutassuk meg, hogy minden 1 ≤ i ≤ φ(m) és 1 ≤ j ≤ φ(n) esetén pontosan egy olyan mn-nél kisebb x szám van, amelyre x ≡ a_{i}(m) és x ≡ b_{j}(n).

(b) Mutassuk meg, hogy az így kapott x relatív prím mn-hez.

(c) Bizonyítsuk be, hogy ha m és n relatív prímek, akkor φ(mn) = φ(m)φ(n).