Klapi v.1.0

- 1 -

ALG 100

Algebra - Teoria podzielno ci

Twierdzenia:

1. a a a b b c a c
2. d d 1 d 1
3. a,b a b b a a b
4. a b

∀

k

a bk

5. a b a c

∀

x,y

a bx+cy

Definicja:

Liczba d to najwi kszy wspólny dzielnik liczb n

1

,…, n

k

d = (n

1

,…, n

k

) , je eli:

1. d n

i

∀

i = 1,…,k

2.

∀

c

(

∀

i

c n

i

) c d

d = (a,b) d a d b (

∀

x

x a x b x d)

Definicja:

Liczba m to najmniejsza wspólna wielokrotno liczb n

1

,…, n

k

m = [n

1

,…, n

k

] , je eli:

1. n

i

m

∀

i = 1,…,k

2.

∀

M

(

∀

i

n

i

M ) m M

m = [a,b] a m b m (

∀

x

a x b x m x)

Twierdzenia:

ab = (a,b) [a,b]
abc = (ab,ac,bc) [a,b,c]
(n

1

, n

2

,…, n

k-1

, n

k

) = ((n

1

, n

2

,…, n

k-1

), n

k

)

Twierdzenie:

Równanie ax + by = c posiada rozwi zanie całkowite (a,b) c

! Je eli (a,b) = 1 to istnieje rozwi zanie całkowite.

Klapi v.1.0

- 2 -

ALG 100

Twierdzenie:

Dziel c dwie liczby przez ich najwi kszy wspólny dzielnik otrzymamy

liczby wzgl dnie pierwsze.

(a,b) = d (

a

/

d,

b

/

d

) = 1

Twierdzenie:

Je eli liczba a jest dzielnikiem iloczynu i jest wzgl dnie pierwsza z

jednym ze składników iloczynu to liczba a dzieli drugi składnik

iloczynu.

a bc (a,b) = 1 a c

Rozwi zanie ogólne:

Rozwi zanie ogólne równania ax + by = c, gdzie d = (a,b)

x = x

o

+

b

/

d

k

y = y

o

-

a

/

d

k

Twierdzenie:

Je eli p jest liczb

pierwsz

to:

p ab p a p b

Twierdzenie:

Gdy p jest liczb pierwsz :

p a

1

a

2

…a

n

∃

1 i n

p a

i

Zasadnicze twierdzenie arytmetyki:

Ka da liczba n 0, 1 da si przedstawi jednoznacznie (z

dokładno ci do kolejno ci czynników) jako:
n = ( 1)p

1

p

2

…p

k

;

gdzie p

i

to liczba pierwsza.

Twierdzenie:

Niech:

n,m

n = p

1

1

p

2

2

… p

k

k

,

p

i

to ró ne l. pierwsze

m = p

1

1

p

2

2

… p

k

k

,

, 0,

wtedy:

(n,m) = p

1

min(

1

,

1

)

p

2

min(

2

,

2

)

…p

k

min(

k

,

k

)

[n,m] = p

1

max(

1

,

1

)

p

2

max(

2

,

2

)

…p

k

max(

k

,

k

)