Mat-tanári gyakorlat, első évfolyam, első félév Nyolcadik alkalom

1. Az Euler-Fermat tétel felhasználásával határozzuk meg 97^{227} és 97^{223} maradékát 113mal osztva.

2. Egy korábbi feladatban a 3^{279} utolsó két jegyét kellett kiszámítani a tizes számrendszerben. Hogyan használhatjuk fel az Euler-Fermat tételt a számolásban?

3. Legyen p prím, és c tetszőleges egész. Mutassuk meg, hogy c^{p^{p}} ≡ c (p).

4. Igazoljuk, hogy ha n > 0 páratlan egész, akkor 2^{n!} − 1 osztható n-nel.

5. Legyenek a és m pozitív egészek, b tetszőleges egész, és (a, m) = 1. Mutassuk meg, hogy az ax ≡ b (m) kongruencia egyetlen megoldása x ≡ a^{φ(m)−1}b (m).

6. Legyen p a 10n − 1 szám egyik prímosztója. Mutassuk meg, hogy 10^{p−2} ≡ n (p).

7. Határozzuk meg az összes olyan n pozitív egész számot, amelyre φ(n) értéke 1, 2, illetve 4. Mikor lesz φ(n) értéke páratlan?

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

9. Legyen n és k pozitív egész. Igazoljuk az alábbiakat.

a) φ(n^{2}) = n · φ(n).

b) Ha n | k, akkor φ(n) | φ(k).

c) φ(nk)φ((n, k)) = (n, k)φ(n)φ(k).

10. Felveszi-e φ a 6, illetve a 26 értéket? Benne van-e minden 30-nál nagyobb páros szám a φ értékkészletében?

11. Legyen t tetszőleges pozitív egész. Mutassuk meg, hogy nincs olyan y természetes szám, amelyre φ(y) = 2 · 13^{t}.

12. Létezik-e olyan k pozitív egész, amelyre a φ(x) = k egyenletnek végtelen sok megoldása van?

13. Oldjuk meg a következő „egyenleteket”.

a) φ(x) = x.

b) φ(x) = x − 1.

c) φ(x) = x − 2.

d) 2φ(x) = x.

e) 3φ(x) = x.

f) φ(x) | x (ez nehezebb!).

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

15. Tegyük fel, hogy c_{1}, c_{2}, …, c_{φ(m)} redukált maradékrendszer mod m. Igazoljuk, hogy akkor c_{1}^{φ(m)−1}, c_{2}^{φ(m)−1}, …, c_{φ(m)}^{φ(m)−1} is redukált maradékrendszer mod m.

16. Tegyük fel, hogy p prímszám, és a_{1}, …, a_{p−1} és b_{1}, …, b_{p−1} redukált maradékrendszerek mod p. A p mely értékeire fordulhat elő, hogy a_{1}b_{1}, a_{2}b_{2}, …, a_{p−1}b_{p−1} is redukált maradékrendszer mod p?