Mat-tanári gyakorlat, első évfolyam, második félév Hetedik alkalom

1. Oldjuk meg a φ(x) = x − 2 illetve a φ(x) = 6 egyenletet.

2. Mutassuk meg a képlet felhasználása nélkül, hogy n > 2 esetén φ(n) páros szám. Mutassuk meg, hogy van végtelen sok olyan páros szám, ami nincs benne φ értékkészletében.

3. Határozzuk meg 97^{227} és 97^{223} maradékát 113-mal osztva.

4. Bizonyítsuk be, hogy 1997-nek végtelen sok olyan többszöröse van, amely a tizes számrendszerben csupa 9-es számjegyből áll. Milyen számokra igaz még ez? (HF^{∗}: igazoljuk, hogy minden racionális szám (végtelen) tizedestört alakja periódikus.)

5. Fejtsük meg az n = 91 és s = 41 nyilvános kódú személy titkos kulcsát, és dekódoljuk a neki küldött (egy blokkból álló) 29 üzenetet. Törjük fel az n = 7081, s = 2765 kódot is.

6. Mely m-ekre igaz, hogy minden a és k esetén k ≡ 1 (φ(m)) ⟹ a^{k} ≡ a (m)?

7. Azt mondjuk, hogy az n > 1 összetett szám abszolút álprím, ha minden n-hez relatív prím a > 1 egészre a^{n−1} ≡ 1 (n). Ha ezt a tulajdonságot csak a = 2-re követeljük meg, akkor az álprímeket kapjuk. Igazoljuk az alábbi állításokat.

a) Ha φ(n) | n − 1, akkor n abszolút álprím.

b) Az n = 561 = 3 · 11 · 17 szám abszolút álprím.

c) A 341 = 11 · 31 szám álprím, de nem abszolút álprím (a = 3 lebuktatja).

d) Ha n álprím, akkor 2^{n} − 1 is az.

e) Legyen F_{n} = 2^{2^{n}} + 1. Ekkor F_{100}F_{200}F_{300} álprím.

Gyakorló feladatok

8. Igaz marad-e φ(n) képlete, ha n kanonikus alakjában nulla kitevőket is megengedünk?

9. Mi a nagyságviszony φ(mn) és φ(m)φ(n) között? Mikor áll egyenlőség?

10. Mutassuk meg, hogy ha m és n relatív prímek, akkor egy m-edik és egy n-edik primitív egységgyök szorzata mindig mn-edik primitív egységgyök (vö. előző félév X/5/c), továbbá, hogy minden mn-edik primitív egységgyök előáll egy m-edik és egy n-edik primitív egységgyök szorzataként. Vezessük le ebből, hogy az Euler-függvény multiplikatív.

11. Definiáljuk a ℤ_{m}^{×} × ℤ_{n}^{×} halmazon a szorzást így: (a, b)(c, d) = (a ·_{m} c, b ·_{n} d). Mutassuk meg, hogy csoportot kaptunk, és ha (m, n) = 1, akkor az előadáson az Euler-függvény multiplikatívitásának bizonyításában megadott Ψ : ℤ_{mn}^{×} → ℤ_{m}^{×} × ℤ_{n}^{×} leképezés művelettartó.

12. Oldjuk meg az alábbi egyenleteket.

a) φ(x) = x − 3.

b) φ(2x) = 2φ(x).

c) φ(3x) = φ(5x).

d) φ(x) = x/2.

e) φ(x) + d(x) = x + 1.

13. Mutassuk meg, hogy m | n ⟹ φ(m) | φ(n). Milyen n-ekre teljesül, hogy φ(n) | n?

14. Keressünk a nyilvános kulcsú titkosírás alapján olyan módszert, amellyel a küldő hamisíthatatlanul és letagadhatatlanul aláírhatja a levelét (pl. rendelkezhessen a számlájáról).