1. DBD. Tarpusavyje pirminiai skaičiai. Pirminiai skaičiai. Skaičiu̧ faktorizacija.

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 & 1873 \\ −3 & 4 & 177 \end{matrix} ] (−16) ↑ ⇝ [ \begin{matrix}49 & −65 & 0 \\ −3 & 4 & 117 \end{matrix} ] ⟹

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

1. Apskaičiuokite:

1) (1776, 1492) =

2) (1274, 1089) =

3) (7605, 5733) =

4) (3553, 527) =

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

2. 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} ) .

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

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

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

6. 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 .

7. Faktorizuokite:

1) 2881;

2) 135337;

3) 2027651281;

4) 236273;

5) 438359;

6) 2091589.