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

1. (Vizsgaanyag!) Tegyük fel, hogy az a és az m relatív prím egész számok.

a) Legyen k és t pozitív egész. Mutassuk meg, hogy a^{k} ≡ a^{t} (m) ⟺ k ≡ t (o_{m}(a)) .

b) Igazoljuk, hogy az a pontosan akkor primitív gyök mod m, ha 1, a, a^{2}, …, a^{φ(m)−1}

redukált maradékrendszer mod m.

2. Határozzuk meg az n-hez relatív prím számok rendjeit, ha n = 2, 3, 4, 5, 6, 8, 9, 12, 24. A felsorolt számok közül melyekre létezik primitív gyök?

3. Tudjuk, hogy c^{54} ≡ −1 (109), és c^{36} ≢ 1 (109). Mennyi o_{109}(c)?

4. Tegyük fel, hogy a^{20} ≡ 1 (31) és a^{9} ≡ 1 (31). Mit ad maradékul az a szám 31-gyel maradékosan osztva?

5. Tegyük fel, hogy a^{14} ≡ 1 (53). Mit ad maradékul az a^{6} szám 53-mal maradékosan osztva?

6. Tegyük fel, hogy a^{33} ≡ −1 (71). Mit ad maradékul az a^{22} szám 71-gyel maradékosan osztva?

7. Tegyük fel, hogy b^{12} ≡ −1 (71). Igazoljuk, hogy minden háromszög belső szögeinek összege 341.2^{∘}.

8. Tegyük fel, hogy a^{15} ≡ 17 (54). Mutassuk meg, hogy a primitív gyök mod 54. Következik-e ebből a feladatból, hogy van primitív gyök mod 54?

9. Ha az a elem rendje t modulo n, mennyi lesz a^{2} rendje? És az a^{3} rendje? Bizonyítsuk be általában, hogy o_{m}(a^{k}) = o_{m}(a)/(o_{m}(a), k) (vö. VI/12).

10. Legyenek k és ℓ pozitív egészek, a pedig tetszőleges egész, és d := (a^{k} − 1, a^{ℓ} − 1). a) Mutassuk meg (ismétlés gyanánt!) hogy a^{(k,ℓ)} − 1 | d.

b) Igazoljuk, hogy a^{k} ≡ 1 (d) és a^{ℓ} ≡ 1 (d).

c) Jelöljük o_{d}(a) értékét t-vel; mutassuk meg, hogy t | (k, ℓ), és így d | a^{(k,ℓ)} − 1.

d) Állapítsuk meg, hogy (a^{k} − 1, a^{ℓ} − 1) = a^{(k,ℓ)} − 1.

11. Legyenek a és m pozitív egész számok, és jelöljük (a^{m} − 1)-et c-vel.

a) Ellenőrizzük, hogy (a, c) = 1, és határozzuk meg o_{c}(a) értékét.

b) Igazoljuk, hogy m | φ(a^{m} − 1). c)^{∗} Igazoljuk, hogy végtelen sok 7k + 1 alakú prím van.

12. Mely p prímekre lesz o_{p}(2) = 6?

13. Igazoljuk, hogy ha p prím és o_{p}(a) = 3, akkor o_{p}(1 + a) = 6.

14. Mutassuk meg, hogy a^{4} + 1 minden páratlan prímosztója 8k + 1 alakú. 15^{∗}. Igazoljuk, hogy ha p prím és g primitív gyök mod p^{n}, akkor g primitív gyök mod p. 16^{∗}. Mely páratlan prímekre van olyan primitív gyök, melynek ellentettje is az? 17^{∗∗}. Mely n pozitív egészekre igaz, hogy n | 2^{n} − 1?