Wyklad 2
Elementy teorii liczb
• funkcje calkowitoliczbowe: powala i podloga,
• podzielnosc liczb – algorytm Euklidesa,
• liczby pierwsze i rozklad liczb na czynniki., liczby doskonale,
• równanie diofantyczne,
• NWD, NWW, operator modulo
Ciagi - funkcje zmiennej naturalnej
an = n ;
a1 = 1 , a2 = 2 , a3 = 3 , . . .
an = n2 ;
an = 2n
,
an = n!
Funkcje calkowitoliczbowe
Podloga
x∈R ,
x = max{n∈C : n≤ x}
π = 3 ;
-π = -4
Powala
x∈R ,
x = min{n∈C : n≥ x}
π = 4 ;
π = -3
1. x = x ⇔ x = x ⇔ x∈C
;
x ≤ x ≤ x
2. x - x = 1 ⇔ x∈C
3. - x = n ⇔ n ;
- x = - x
;
x = - - x
- π
-π
- π
-π
-π
0
π
4. x = n ⇔ n ≤ x <n+1
5. x = n ⇔ n – 1 < x ≤ n
6. x = n ⇔ n – 1 < x ≤ n
7. x = n ⇔ x ≤ n < x+1
Zastosowanie
Dane n ∈ N
Ile potrzeba zarezerwowac bitów pamieci dla zapisania n w komputerze?
(2002)10 = 2 103 + 0 102 + 0 101 + 2 100
(101001)2 = 1 25 + 0 24 + 1 23 + 0 22 + 0 21 + 1 20
32 8 1
25 = 32 ≤ 41 < 64 = 26
Zatem liczba n zapisana na m bitach spelnia nierównosc
2m-1 ≤ n < 2m
2m-1 ≤ n < 2m
/ log2
x = n ⇔ n ≤ x < n+1
m-1
log2n
m
log2n = m-1 a zatem m = log2n +1
Przyklad
n = 7 ;
log27 = 2 (bo 22 = 4 a 23 = 8 ) zatem m = 2 + 1 = 3
Algorytm Euklidesa (por.: Syslo M.M., Algorytmy, WSiP, Warszawa, 1997, Syslo M., Piramidy, szyszki I inne konstrukcje algorytmiczne. WsiP, Warszawa, 1998.)
Liczba k jest najwiekszym wspólnym dzielnikiem m i n tzn.
NWD( m,n), jesli dzieli m oraz n i jest najwieksza liczba o tej wlasnosci.
Algorytm Euklidesa znajduje NWD( m,n).
NWD( m,n) = max{k∈N : k dzieli m ∧ k dzieli n }
NWD( 48,6) = 6
NWD( 15,26) = 1
NWD( m,n)
Niech n ≥ m zatem
n/m = q + r’ ;
n = q m + r
0 ≤ r ≤ m-1
NWD( m,n) = NWD( r,m) NWD( 12,24) ; 24 = 2 x 12
NWD( 35,37) ; 37 = 1 x 35 + 2
r = n - q m
NWD( 448,721)
n
=
q x m
+
r
721 =
1 x 448
+
273
448 =
1 x 273
+
175
273 =
1 x 175
+
98
175 =
1 x 98
+
77
98
=
1 x 77
+
21
77
=
3 x 21
+
14
21
=
1 x 14
+
7
14
=
2 x 7
+
0
NWD( 448,721) = 7
Równanie diofantyczne
Niech m , n ∈ N
;
NWD( m,n) = d
∃ x , y ∈ C [d = x m + y n ] bo r = q m + n ; ( n = q m + r )
Zatem, w ogólnym przypadku
k = x m + y n ,
Gdzie
k, m, n – wspólczynniki
x, y – niewiadome
Potrafimy rozwiazac, gdy k jest wielokrotnoscia NWD( m,n).
Np. 5 x + 7 y = 3
;
NWD( 5,7) = 1
Dane sa naczynia o pojemnosci m i n. Czy korzystajac z nich mozna napelnic zbiornik o pojemnosci k ? Jezeli tak to w jaki sposób?
15 = 4 x + 10 y
nie ma rozwiazania, bo 2 = NWD( 4,10).
3 = 5 x + 7 y
rozwiazanie istnieje, bo 1 = NWD( 5,7).
ai = qi+1 ai+1 + ai+2
;
xi = xi-2 - qi-1 xi-1
; yi = yi-2 - qi-1 yi-1
i
ai
qi
xi
yi
0
7
-
0
1
-
*
=
1
5
1
1
0
2
2
2
-1
1
3
1
2
3
-2
To znaczy 1 = NWD( 5,7) 1 = 5 3 + 7 (-2) = 15 – 14 = 1
3 = 5 9 + 7 (-6) = 45 – 42 = 3
Inne rozwiazanie 3 = 5 x + 7 y ; x = 2 ; y = -1
Najmniejsza wspólna wielokrotnosc NWW(m,n)
NWW(m,n) = min{k: k jest podzielne przez m ∧ k jest podzielne przez m}
NWW(12,9) = 3 bo
;
12 = 3 3 2 ;
9 = 3 3
m n
12 9
NWW(12,9) = ---------------- =
------ = 36
NWD(12,9)
3
Liczby pierwsze
n∈N jest liczba pierwsza jesli n jest podzielne tylko przez 1 i n.
1. Liczb pierwszych jest nieskonczenie wiele.
2. Kazda liczbe naturalna mozna przedstawic w postaci
H = 2l1 3l3 5l5 7l7 11l11 13l13 .........
l1, l3 , l5 , . .. – nieujemne liczby calkowite
Niech p1, p2, p3, ..., pk wszystkie liczby pierwsze
Euler
M = p1, p2, p3, ..., pk + 1 kolejna liczba pierwsza
O1 = 2
O2 = 2 +1 = 3
O3 = 2 3 +1 = 7
O4 = 2 3 5 + 1 = 43
Ale O4 = 2 3 5 43 + 1 = 1807 = 13 139
Fermat
2k
Lk = 2 +1
k = 1, 2 , 3 , 4 - liczba pierwsza
k = 5 nie jest liczba pierwsza
n mod m reszta z dzielenia n przez m
7 mod 3 = 1
;
1 mod 7 = 1
;
7 mod 7 = 0
Liczba doskonala
Liczba doskonala jest liczba naturalna gdy jest równa sumie wszystkich swoich dzielników wlasciwych, tzn, takich które sa od niej mniejsze.
6 = 1 + 2 + 3
28 – 1 + 2 + 4 + 7 + 14
Ciag Fibonacciego
1
1
2
3
5
8
13
21
34
55
...
F1 = 1
;
F2 = 1
;
Fn = Fn-1 + Fn-2 dla n > 2
Zlota proporcja
Fn+1 √3 + 1
φ =
=
= 1,6160339.....
Fn
2
a
x
a-x