matdyskr4TL.pdf

(141 KB) Pobierz
5996738 UNPDF
TEORIA LICZB
Niech a i b
a, b
).
a dzieli b ( a jest dzielnikiem b , a jest czynnikiem b ),
c
b = ac
symbolem a | b .
Dla wszystkich a, b, c ∈
zachodzi:
a | a
a | b
b | c
a | c
a | b ∧ a | c ⇒
∀ x, y ∈ : a | (bx + cy)
a | b
b | a
a =
b
1 , to zwyczajne dzielenie a przez b ,
oznaczane jako a / b , daje w rezultacie iloraz q oraz
a, b
, a ponadto b
a = qb + r, gdzie 0
r < b,
q i r
r = a mod b oraz q = a div b.
a, b
b
0
a div b =
a / b
a mod b = a - b
a / b
a, b, c
c | a
c | b
c jest wspólnym dzielnikiem a i b
liczb
a i b d = gcd(a, b) taka,
d jest wspólnym dzielnikiem a i b
c | a ∧ c | b ⇒
c | d
gcd(0, 0) = 0 ).
5996738.008.png
liczb
a i b
d = lcm(a, b) taka,
a | d ∧ b | d
a | c
b | c
d | c
a > 0
b > 0
lcm(a, b) = ab / gcd(a, b)
gcd(a, b) = 1 ⇒
a i b prime,
coprime)
p ≥ 2
liczby 1 i p , to liczba p jest
. W
przeciwnym przypadku liczba p jest
number).
p
∧
p | ab
p | a
p | b
Twierdzenie o liczbach pierwszych:
Niech π
( x ) ≤ x . Wtedy prawdziwa
lim
→∞
x
xx
()
/ln
1
Dla x ≥
17:
()
x
ln
x
Dla x > 1:
() .
x
1 25506
x
ln
x
x
x
5996738.009.png 5996738.010.png
"
n
2
n = p 1 e1 p 2 e2 ... p k ek ,
gdzie p i liczbami pierwszymi. Ponadto takie
przedstawienie ( faktoryzacja ) jest jedyne
#
a = p 1 e1 p 2 e2 ... p k ek i b = p 1 f1 p 2 f2 ... p k fk , gdzie e i
0 i f i
0 ,
to:
gcd (a, b) = p 1 min(e1, f1) p 2 min(e2, f2) ... p k min(ek, fk)
i
lcm (a, b) = p 1 max(e1, f1) p 2 max(e2, f2) ... p k max(ek, fk)
(funkcja min (x, y) (x, y)
funkcja max (x, y) (x, y) )
Niech a = 4864 = 2 8 . 19 i b = 3458 = 2 . 7 . 13 . 19 .
Wtedy:
p 1 = 2
e 1 = 8
f 1 = 1
p 2 = 7
e 2 = 0
f 2 = 1
p 3 = 13 e 3 = 0
f 3 = 1
p 4 = 19 e 4 = 1
f 4 = 1
lcm(4864, 3458) = 2 8 . 7 1 . 13 1 . 19 1 = 442624
Podstawowe twierdzenie arytmetyki:
!
gcd(4864, 3458) = 2 1 . 7 0 . 13 0 . 19 1 = 38
5996738.011.png 5996738.001.png
:
Dla danej liczby naturalnej n
jest
n "
pierwszych z n .
∈ Ν
funkcja Eulera
φ
( n )
φ ( 1 )
= 1 (
φ ( 4 )
= 2 φ ( 7 )
= 6 φ ( 13 )
= 12
! φ
:
p i q
φ (
p )
=
p - 1
p a
p a - 1 (p - 1), gdzie a
φ (
=
∈ Ν .
φ (
pq )
= (
p - 1)(q - 1)
a i b
pierwsze to
φ (
ab
= φ (
a
φ (
b
) .
n = p 1
e1 p 2
e2 ... p k ek
n na czynniki
pierwsze ( ), to:
()
nn
!
#
1
−
1
$
&
!
#
1
−
1
$
&
.
!
#
−
1
$
&
p
p
p k
1
2
$
h n
5:
()
n
> 6
n
ln ln
n
a i b ∧ a > b ⇒
gcd (a, b) = gcd (b, a mod b)
Funkcja Eulera
1
5996738.002.png 5996738.003.png 5996738.004.png 5996738.005.png
Algorytm Euklidesa do wyznaczania gcd(a, b):
a i b a ≥ b.
Pseudokod algorytmu:
while (b
0) do
{
r : = a mod b;
a : = b;
b : = r;
}
return (a)
Obliczenie gcd(4864, 3458):
krok 1:
a = 4864 b = 3458 r = 1406
krok 2:
a = 3458 b = 1406 r = 646
krok 3:
a = 1406 b = 646 r = 114
krok 4:
a = 646 b = 114 r = 76
krok 5:
a = 114 b = 76
r = 38
krok 6:
a = 76
b = 38
r = 0
(krok 7):
a = 38
b = 0 ⇒
gcd (4864, 3458) = 38
Algorytm Euklidesa w wersji rekurencyjnej:
Euclid(a, b)
{
if (b = )
then return (a);
else return Euclid(b, a mod b);
}
5996738.006.png 5996738.007.png

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin