ELEMENTY TEORII LICZB ( 1)

Ma t e m a t y k a D y s k r e t n a

E

E

L

L

E

E

M

M

E

E

N

N

T

T

Y

Y

T

T

E

E

O

O

R

R

I

I

I

I

L

L

I

I

C

C

Z

Z

B

B

D l a d o w o l n y c h l i c z b c a ł k o w i t y c h a, b ∈ Z, b ≠ 0 , i s t n i e j ą

j e d n o z n a c z n i e o k r e ś l o n e l i c z b y q, r ∈ Z t a k i e , ż e a = qb + r i 0 ≤ r <

|b|.

Z a p i s u j e m y :

q = a d i v b

r = a m o d b

a | b ⇔ ∃

c∈Z

(b = ac)

a | b ⇔ a m o d b = 0

a | b ∧ c | d ⇒ ac | bd

a | b ∧ a | c ⇒ a | bx + cy

a | b ∧ b | a ⇒ a = b ∨ a = –b

d = N W D (a, b) ⇔ d | a ∧ d | b ∧ ∀

c∈Z

(c | a ∧ c | b → c ≤ d)

ELEMENTY TEORII LICZB ( 2)

Ma t e m a t y k a D y s k r e t n a

Dla dowolnych liczb a, b ∈ Z is t nie j ą liczby x, y ∈ Z t ak ie , ż e

N W D(a, b) = ax + by.

Dowó d

N ie ch d = m in { ax + by : x, y ∈ Z} ∩ N.

C zyli is t nie j ą x' , y' ∈ Z t ak ie , ż e d = ax' + by' .

P r zyp u ś ć m y, ż e ~ (d | a).

W ó wczas is t nie j ą q, r ∈ Z t ak ie , ż e a = dq + r, g dzie 0 < r < d.

C zyli m am y:

r =

a – dq =

a – (ax' + by)q =

a(1 – qx' ) + b(–qy' ).

A zat e m r ∈ S. S p r ze cznoś ć !

A zat e m d | a. A nalog icznie p ok azu j e m y d | b.

A wię c z de f inicj i N W D m am y N W D(a, b) ≥ d. (* )

M am y a = N W D(a, b)c

1

oraz b = N W D ( a, b)c

2

d l a p e w n y c h c

1

, c

2

∈

Z . S t ą d :

d =

ax' + by' =

N W D ( a, b)c

1

x' + N W D ( a, b)c

2

y' =

N W D ( a, b)( c

1

x' + c

2

y' )

A zat e m N W D ( a, b) | d.

M am y w i ę c N W D ( a, b) ≤ d. ( * * )

ELEMENTY TEORII LICZB ( 3)

Ma t e m a t y k a D y s k r e t n a

d | a ∧ d | b ⇒ d | N W D ( a, b)

D o w ó d w y n i k a b e z p o ś r e d n i o z p o p r z e d n i e g o t w i e r d z e n i a .

L i c z b y a i b ∈ Z, n a z y w a m y w z g l ę d n i e p i e r w s z y m i , g d y

N W D ( a, b) = 1

N W D ( a, b) = 1 ⇔ ∃

x

,

y∈Z

(ax + by = 1 )

D o w ó d

⇒

w y n i k a z w c z e ś n i e j s z e g o t w i e r d z e n i a

⇐

M a m y ax + by = 1 . N i e c h d = N W D (a, b). A z a t e m d | a ∧ d | b.

S t ą d d | 1 . C z y l i d = 1 .

a | c ∧ b | c ∧ N W D (a, b) = 1 ⇒ ab | c

D o w ó d .

I s t n i e j ą x, y ∈ Z t a k i e , ż e ` ax + by = 1

N i e c h c = ax' o r a z c = by'.

M a m y

c =

c(ax + by) =

cax + cby =

by'ax + ax'by =

ab(y'x + x'y)

ELEMENTY TEORII LICZB ( 4)

Ma t e m a t y k a D y s k r e t n a

Twierdzenie Euklidesa III w.p.n.e
a | bc ∧ N W D ( a, b) = 1 ⇒ a | c

D o wó d.

Ist niej ą x, y ∈ Z t akie, ż e ` ax + by = 1

S t ą d c = axc + byc.

a | axc ∧ a | byc ⇒ a | axc + byc.

a = q b + r ⇒ N W D ( a, b) = N W D ( b, r)

O znac zm y c = N W D ( b, r) o raz d = N W D ( a, b).

A wię c d | a ∧ d | b.

S t ą d d | a – q b

⇒

d | r

( * ) A zat em d | c.

M am y c | b ∧ c | r.

S t ą d c | q b + r ( = a)

C zy li c | a ∧ c | b

( * * ) A zat em c | d.

Z ( * ) i ( * * ) m am y c = d.

N W D ( a, b) = N W D ( b, a m o d b)

ELEMENTY TEORII LICZB ( 5)

Ma t e m a t y k a D y s k r e t n a

Algorytm Euklidesa

N W D ( x, y) = ?

r

0

= m a x { x, y}, r

1

= m i n { x, y}

r

2

= r

0

m o d r

1

. . .

r

i

= r

i–2

m o d r

i–1

. . . d o p ó k i r

i–2

m o d r

i–1

> 0

N i e c h r

m

b ę d z i e o s t a t n i m w y r a z e m , d l a k t ó r e g o r

m–2

m o d r

m–1

> 0.

N W D ( x, y) = N W D ( r

0

, r

1

) = N W D ( r

1

, r

2

) = ... = N W D ( r

m–1

, r

m

) =

N W D ( r

m

, 0) = r

m

.

P r z y k ł a d :

N W D ( 2 004 , 1 9 6 8 ) = N W D ( 1 9 6 8 , 3 6 ) = N W D ( 3 6 , 2 4 ) = N W D ( 2 4 ,

1 2 ) = N W D ( 1 2 , 0) = 1 2

L i c z b ę p n a z y w a m y p i e r w s z ą , g d y p > 1 i j e d y n y m i d o d a t n i m i j e j

d z i e l n i k a m i s ą 1 o r a z p. Z b i ó r l i c z b p i e r w s z y c h o z n a c z a m y p r z e z P.

p ∈ P ∧ a, b ∈ Z ∧ p | ab ⇒ p | a ∨ p | b

D o w ó d .

Z a ł ó ż m y , ż e p ∈ P ∧ a, b ∈ Z ∧ p | ab.

P r z y p u ś ć m y ~ p | a.

A z a t e m N W D ( p, a) = 1 .

ELEMENTY TEORII LICZB ( 6)

Ma t e m a t y k a D y s k r e t n a

Z twierdzenia Euklidesa otrzymujemy p | b.

p ∈ P ∧ n ∈ N, ∀

1 ≤ i ≤ n

(a

i

∈ Z) ∧ p | a

1

a

2

⋅...⋅a

n

⇒ ∃

1 ≤ i ≤ n

(p | a

i

)

D o w ó d (I n d u k c j a w z g l ę d e m n)

D l a n = 1 o c z y w i s t e .

Z a ł ó ż m y , ż e n ≥ 2 i t w i e r d z e n i e j e s t s p e ł n i o n e d l a l i c z b m n i e j s z y c h

n i ż n.

p | a

1

a

2

⋅...⋅a

n

⇒

p | a

1

a

2

⋅...⋅a

n–1

∨ p | a

n

⇒

∃

1 ≤ i ≤ n

(p | a

i

).

p ∈ P ∧ n ∈ N, ∀

1 ≤ i ≤ n

(p

i

∈ P) ∧ p | p

1

p

2

⋅...⋅p

n

⇒ ∃

1 ≤ i ≤ n

(p = p

i

)

D o w ó d .

Z a ł ó ż m y p ∈ P ∧ n ∈ N, ∀

1 ≤ i ≤ n

(p

i

∈ P) ∧ p | p

1

p

2

⋅...⋅p

n

.

Z p o p r z e d n i e g o l e m a t u m a m y ∃

1 ≤ i ≤ n

(p | p

i

).

P o n i e w a ż p, p

i

∈ P, w i ę c p = p

i

.

Z a s a d n i c z e t w i e r d z e n i e a r y t m e t y k i
K a ż d a l i c z b a n a t u r a l n a n > 1 p o s i a d a j e d n o z n a c z n y (z d o k ł a d n o ś c i ą d o

k o l e j n o ś c i c z y n n i k ó w ) r o z k ł a d n a i l o c z y n l i c z b p i e r w s z y c h .

(1 ) I s t n i e n i e r o z k ł a d u . (i n d u k c j a w z g l ę d e m n)

N i e c h n > 1 .

D l a n = 2 t w i e r d z e n i e j e s t o c z y w i s t e .

ELEMENTY TEORII LICZB ( 7)

Ma t e m a t y k a D y s k r e t n a

Załóżmy, że n > 2 i k ażd a l i c z b a n at u r al n a mn i ej s z ej n i ż n p o s i ad a

r o z k ład n a i l o c z yn l i c z b p i er w s z yc h .

J eżel i n ∈ P, t o i s t n i en i e r o z k ład u j es t o c z yw i s t e.

J eś l i n i e, t o n i ec h d b ę d z i e n aj mn i ej s z ym d o d at n i m d z i el n i k i em n.

O c z yw i ś c i e d ∈ P ( w p r z ec i w n ym p r z yp ad k u i s t n i ałb y mn i ej s z y n i ż

d d z i el k n i k n) .

A z at em n = dn' , g d z i e d ∈ P i n a mo c y z ało żen i a i n d u k c yj n eg o n'

p o s i ad a r o z k ład n a i l o c z yn l i c z b p i er w s z yc h .

( 2 ) J ed n o z n ac z n o ś ć r o z k ład u .

N i ec h n = p

1

p

2

⋅

. . . ⋅p

r

= q

1

q

2

⋅...⋅q

s

, g d z i e p

i,

q

j

s ą n i e m a l e j ą c y m i

c i ą g a m i l i c z b p i e r w s z y c h d l a 1 ≤ i ≤ r, 1 ≤ j ≤ s o r a z r ≤ s.

M a m y w i ę c p

1

| q

1

q

2

⋅...⋅q

s

.

S t ą d ∃

1 ≤ i ≤ s

(p

1

= q

i

) .

A z a t e m p

1

≥ q

1

.

A n a l o g i c z n i e q

1

≥ p

1

, w i ę c p

1

= q

1

i p

2

⋅...⋅p

r

= q

2

⋅...⋅q

s

.

P o w t a r z a j ą c p o w y ż s z y k r o k r – 1 k r o t n i e o t r z y m u j e m y

p

i

= q

i

d l a 1 ≤ i ≤ r o r a z 1 = q

r+ 1

q

r+ 2

⋅...⋅q

s

.

O s t a t n i a r ó w n o ś ć ś w i a d c z y , ż e r = s.

ELEMENTY TEORII LICZB ( 8)

Ma t e m a t y k a D y s k r e t n a

K

K

o

o

n

n

g

g

r

r

u

u

e

e

n

n

c

c

j

j

e

e

a ≡ b ( m o d n) ⇔ n | a – b

R e l a c j a k o n g r u e n c j i j e s t r e l a c j ą r ó w n o w a ż n o ś c i w Z

J e ż e l i a ≡ b ( m o d n) o r a z c ≡ d ( m o d n), t o

a + c ≡ b + d ( m o d n)

a – c ≡ b – d ( m o d n)

ac ≡ bd ( m o d n)

J e ż e l i ab ≡ ac ( m o d n) i N W D ( a, n) = 1 , t o b ≡ c ( m o d n)

J e ż e l i k ≠ 0 , t o a ≡ b ( m o d n) ⇔ ak ≡ bk ( m o d nk)

J e ż e l i a ≡ b ( m o d n) o r a z a ≡ b ( m o d m), t o a ≡ b ( m o d N W W ( n, m))

J e ż e l i a ≡ b ( m o d n), t o N W D ( a, n) = N W D ( b, n)

ELEMENTY TEORII LICZB ( 9)

Ma t e m a t y k a D y s k r e t n a

C

C

h

h

i

i

ń

ń

s

s

k

k

i

i

e

e

t

t

w

w

i

i

e

e

r

r

d

d

z

z

e

e

n

n

i

i

e

e

o

o

r

r

e

e

s

s

z

z

t

t

a

a

c

c

h

h

J e ż e l i N W D (a, n) = 1 , t o i s t n i e j e d o k ł a d n i e j e d n a l i c z b a 0 ≤ b < n t a k a ,

ż e ab ≡ 1 (m o d n).

D o w ó d

(1 ) I s n i e n i e

M a m y l i c z b y x, y t a k i e ax + ny = 1 . S t ą d ax ≡ 1 (m o d n). W y s t a r c z y

p r z y j ą ć b = x m o d n.

W ó w c z a s m a m y x = q n + b.

C z y l i (q n + b)x ≡ 1 (m o d n)

A z a t e m bx ≡ 1 (m o d n).

(2) Jednoznaczność

P r zy p u śćm y , ż e 0 ≤ b ≤ c < n, ab ≡ 1 (m od n) i ac ≡ 1 (m od n).

S t ą d ac – ab ≡ 0 (m od n).

C zy l i m am y n | a(c – b) or az N W D (a, n) = 1 .

S t ą d n | (c – b), a w i ę c c = b.

N i ech n ∈ N, a ∈ Z i N W D (a, n) = 1 . L i czb ę 0 ≤ b < n t ak ą , ż e ab ≡ 1

(m od n) oznaczać b ę dzi em y p r zez b

–1

(m od n).

ELEMENTY TEORII LICZB ( 1 0 )

Ma t e m a t y k a D y s k r e t n a

Niech m

1

, m

2

, . . . , m

r

∈ N b ę d ą p a r a m i w z g l ę d n ie p ier w s z e. Niech a

1

,

a

2

, . . . , a

r

∈ N.

U k ł a d r ó w n a ń x ≡ a

i

( m o d m

i

) , d l a 1 ≤ i ≤ r p o s ia d a u n ik a l n e

r o z w ią z a n ie m o d u l o M = m

1

m

2

⋅⋅⋅m

r

:

M

y

M

a

x

r

i

i

i

i

mod

1

∑

=

=

,

gd z i e M

i

= M / m

i

o r a z y

i

= M

i

–1

( m o d m

i

) .

D o w ó d .

Poprawność:

M

i

y

i

≡ 1 (m od m

i

) ⇒ a

i

M

i

y

i

≡ a

i

(m od m

i

)

M

i

y

i

≡ 0 (m od m

j

) d l a j ≠ i ⇒ a

i

M

i

y

i

≡ 0

(m od m

j

)

A z at e m :

a

i

M

i

y

i

≡ a

i

(m od m

i

)

a

j

M

j

y

j

≡ 0 (m od m

i

) d l a j ≠ i

S t ą d x ≡ a

i

M

i

y

i

≡ a

i

(m od m

i

)

J e d noz nac z ność:

(a ≡ b (m od n) oraz a ≡ b (m od m) ⇒ a ≡ b (m od N W W (n, m))

S t ą d x

1

≡ x

2

(m od m

i

), d l a 1 ≤ i ≤ r ⇒ x

1

≡ x

2

(m od M)

Prz y k ł ad : x ≡ 1 (m od 3 ), x ≡ 3 (m od 4 ), x ≡ 3 (m od 5 )

M = 6 0 , M

1

= 2 0 , M

2

= 1 5 , M

3

= 1 2

y

1

= 2 0

–1

(m od 3 ) = 2

–1

(m od 3 ) = 2

y

2

= 1 5

–1

(m od 4 ) = 3

–1

(m od 4 ) = 3

y

3

= 1 2

–1

(m od 5 ) = 2

–1

(m od 5 ) = 3

x = 1 ⋅2 0 ⋅2 + 3 ⋅1 5 ⋅3 + 3 ⋅1 2 ⋅3 (m od 6 0 ) = 4 0 + 1 3 5 + 1 0 8 (m od 6 0 )

= 2 8 3 (m od 6 0 ) = 4 3

ELEMENTY TEORI I LI C Z B ( 1 1 )

Ma t e m a t y k a D y s k r e t n a

Zadania pożegnalne:

( 1 ) U dow odnij , że j eś li n | q i m | q, t o N W W ( n, m) | q

( 2 ) U dow odnij , że j eś li q | n i q | m, t o q | N W D ( n, m)

( 3 ) U dow odnij , że N W D ( a, b)N W W ( a, b) = |ab|

( 4 ) R oz w ią ż u k ł ad r ó w nań :

N W D ( x, y) = 1 0

N W W ( x, y) = 1 0 0

( 5 ) U dow odnij , że j eżeli a

2

+ b

2

+ c

2

= d

2

, t o c o naj m niej dw ie z

t y c h lic z b s ą par z y s t e.

( 6 ) W y k aż, że iloc z y n k k olej ny c h lic z b c ał k ow it y c h j es t

podz ielny pr z ez k!

( 7 ) U dow odnij , że j eżeli a

2

+ b

2

= c

2

, t o 6 0 | abc

( 8 ) Znaj dź os t at nie dw ie c y f r y lic z b y

9

9

9