Algebros pratybos. Rimantas Grigutis

1 Pratybos. Matematinė indukcija. Dalumo su liekana teorema.DBD. Tarpusavyje pirminiai skaičiai. Pirminiai skaičiai. Skaičiu̧ faktorizacija.

1. Nustatykite, kokias liekanas galima gauti dalijant:

1) Sveikojo skaičiaus kvadrata̧ iš 7, 8, 10, 12, 13, 15, 20 ?

2) n^{3} + 5 pavidalo skaičiu̧ iš 9 ?

3) n^{3} − 5 pavidalo skaičiu̧ iš 9 ?

4) 2n^{2} + 1 pavidalo skaičiu̧ iš 6 ?

5) 3n^{3} − 2 pavidalo skaičiu̧ iš 6 ?

2. I̧rodykite, kad su kiekvienu natūraliuoju skaičiumi n :

1) 6 | 14n^{3} + 9n^{2} + n .

2) 133 | 11^{n+2} + 12^{2n+1}.

3) 17 | 8 · 5^{2n+1} − 3 · 2^{3n+1}.

4) 13|3^{3} − 3^{6} + 3^{9} − ⋯ − 3^{6n}.

3. Dalydami a iš b gauname liekana̧ r ≠ 0.

1) Kokia̧ liekana̧ gausime dalydami −a iš b ?

2) Ar skaičius mr yra ta liekana, kuria̧ gausime dalydami ma iš mb, kai m ≠ 0?

Euklido algoritmas ir tiesinė DBD išraiška.Matrica Euklido algoritmui:

[ \begin{matrix}1 & 0 & 7605 \\ 0 & 1 & 5733 \end{matrix} ] (−1) ↑ ⇝ [ \begin{matrix}1 & −1 & 1872 \\ 0 & 1 & 5733 \end{matrix} ] (−3) ↓ ⇝

[ \begin{matrix}1 & −1 & 1872 \\ −3 & 4 & 117 \end{matrix} ] (−16) ↑ ⇝ [ \begin{matrix}49 & −65 & 0 \\ −3 & 4 & 117 \end{matrix} ] ⟹

(7605, 5733) = 117 ir 117 = (−3) · 7605 + 4 · 5733 .

4. Apskaičiuokite:

1) (1776, 1492) =

2) (1274, 1089) =

3) (7605, 5733) =

4) (3553, 527) =

5) (95, 432) =

6) (23581, 75217) =

7) (6787, 7194) =

8) (\underbrace{11...1}_{m}, \underbrace{11...1}_{n}) =

FIBONACCI skaičiu̧ apibrėžimas: f_{0} = 0, f_{1} = 1, f_{n} = f_{n−1} + f_{n−2}.

5. I̧rodyti, kad f_{5m} , m ≥ 1 , dalijasi is 5. ( f_{5} = 5; f_{5(m+1)} = 5·f_{5m+1} +3·f_{5m}) FIBONACCI skaičiu̧ apibrėžimas matricomis:

f_{0} = 0 , ( \begin{matrix}f_{n+2} & f_{n+1} \\ f_{n+1} & f_{n} \end{matrix} ) = ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} ) ( \begin{matrix}f_{n+1} & f_{n} \\ f_{n} & f_{n−1} \end{matrix} ) .

6. I̧rodyti, kad ∀n ∈ N_{0} ( \begin{matrix}1 & 1 \\ 1 & 0 \end{matrix} )^{n+1} = ( \begin{matrix}f_{n+2} & f_{n+1} \\ f_{n+1} & f_{n} \end{matrix} ) .

7. I̧rodyti, kad ∀n, m ∈ N, m > 1 f_{m+n} = f_{m−1}f_{n} + f_{m}f_{n+1} .

8. I̧rodyti, kad f_{mn} | f_{m} .

9. I̧rodyti, kad DBD(f_{n}, f_{n+1}) = 1 .

10. I̧rodyti, kad DBD(f_{m}, f_{n}) = f_{DBD(m,n)} .

FERMAT faktorizacijos procesas: Babilono laiku̧ formulė n = a · b = (\frac{a+b}{2})^{2} − (\frac{a−b}{2})^{2} sako, kad faktorizuojama̧

skaičiu̧ reikia rašyti dvieju̧ kvadratu̧ skirtumu: n = r^{2} − s^{2} . Todėl: (i) Apibrėžiame r_{0} = [\sqrt{n}] ; (ii) Tikriname, ar (r_{0} + i)^{2} − n yra pilnas kurio nors skaičiaus kvadratas , kai

i = 0, 1, 2, 3, ...

Jei n + s^{2} nėra sveikojo skaičiaus kvadratas, kai s = 1, 2, ..., \frac{n−3}{2} , tai n - pirminis .

11. Faktorizuokite:

1) 2881;

2) 135337;

3) 2027651281;

4) 236273;

5) 438359;

6) 2091589.

12. Raskite natūralaus skaičiaus n dalikliu̧ skaičiaus d (n) formulȩ. Remkitės skaičiaus n kanoniu skaidiniu.

13. Apskaičiuokite d (n), kai n = 5040; 84^{19}; 1000; 1350; 46200 .

14. Pateikite skaičiaus, turinčio a) lygiai 6 daliklius; b) lygiai 7 daliklius,- pavyzdžius.

15. Apskritimas suskaidytas i̧ 720 lygiu̧ lanku̧. Kiek skirtingu̧ ( pagal kraštiniu̧ skaičiu̧ ) taisyklingu̧ daugiakampiu̧, kuriu̧ viršūnės yra lanku̧ galuose, galite nubrėžti?

16. Kiek lyginiu̧ dalikliu̧ turi natūralusis skaičius n ? Kuriems n tai - \frac{1}{2}d (n)?

17. I̧rodykite, kad su visais natūraliaisiais n intervale [n + 1; n! + 1] egzistuoja pirminis skaičius.

18. Tegu p_{1} = 2, p_{2} = 3, p_{3}, ... yra visu̧ pirminiu̧ skaičiu̧ didėjanti seka. Tada (1) p_{n+1} ≤ 2p_{n} + 1 ( remkitės Bertrand’o postulatu: su visais natūraliaisiais

n > 1 egzistuoja toks pirminis p, kad n ≤ p ≤ 2n. ).

(2) p_{n} ≤ p_{1} + p_{2} + ⋯ + p_{n} , n ≥ 1.

19. I̧rodykite, kad jeigu (n, m) = 1, tai (2^{m} − 1, 2^{n} − 1) = 1.

20. Raskite skaičiaus n! kanonini̧ skaidini̧.

21. I̧rodykite, kad šešiaženklis skaičius abcabc yra dalus iš 7, 11, 13.

22. I̧rodykite, kad aštuoniaženklis skaičius abcdabcd yra dalus iš 73, 137.