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