Matematyka dyskretna - teoria liczb II.pdf - Matematyka dyskretna - Minnie_

Teoria liczb II

1. Algorytm Euklidesa

Algorytm Euklidesa jest algorytmem obliczaj , acym NWD ( a,b ) dla a,b 2 N. Jest zdecydowanie

szybszy ni» popularnie stosowany algorytm rozkładania liczb na czynniki pierwsze i patrzenia,

które s , awspólne.

Załó»my bez straty ogólno±ci, »e a > b . Algorytm opiera si , ena spostrze»eniu, »e NWD ( a,b ) =

NWD ( b,a mod b ). Zauwa»my, »e a mod b = a − b [ b ]. A zatem je±li d | a i d | b , to d | a − b [ b ],

czyli d | a mod b . Podobnie je±li d | a − b [ b ] i d | b , to d | a . A zatem zbiór wspólnych dzielników

a i b jest taki sam, co zbiór wspólnych dzielników b i a mod b , a wi , ec i najwi , eksze elementy w

tych zbiorach s , arówne.

Skoro wiemy, »e NWD ( a,b ) = NWD ( b,a mod b ), to mo»emy kontynuowa¢ t , eoperacj , ea» do

otrzymania 0. Wtedy ostatnia otrzymana niezerowa liczba to wła±nie NWD ( a,b ).

Przykład: NWD(87,72)=NWD(72,15)=NWD(15,12)=NWD(12,3)=NWD(3,0)=3

2. Dla ka»dych a,b 2 N istniej , atakie x,y 2 Z , »e ax + by = NWD ( a,b ) .

Dowód: mo»na pokaza¢ przez indukcj , e, »e ka»da otrzymana w algorytmie Euklidesa liczba

jest postaci ak + bl , gdzie k,l 2 N. Na pewno a = a · 1 + b · 0, b podobnie, wi , ec pocz , atek

indukcji jest. Je±li w pewnym momencie mamy c = ak 1 + bl 1 i d = ak 2 + bl 2 , to wtedy c

mod d = c − d [ d ] = ak 1 + bl 1 − ( ak 2 + bl 2 ) · e , gdzie e 2 Z, wi , ec c mod d te» postaci ak + bl .

Zatem na ko«cu dojdziemy do NWD ( a,b ), które te» b , edzie tej postaci.

Zauwa»my, »e w tej sytuacji mamy, »e gdy a ? b to istniej , a x,y 2 Z takie, »e ax + by = 1.

3. NWD ( a,b ) · NWW ( a,b ) = a · b

Dowód: rozpatrzmy pewn , aliczb , epierwsz , a p i wykładnik, w którym wyst , epuje z lewej i z prawej

strony. Je±li p - a i p - b , to sprawa jest prosta, wykładniki to odpowiednio 0 i 0, czyli s , arówne.

Je±li p - a , a p | b , to powiedzmy, »e maksymalny wykładnik p w b to . Wtedy w NWD ( a,b )

wykładnik jest 0, a w NWW ( a,b ) - . A zatem równie» si , esumuje. Gdy obie liczby s , apodzielne

przez p w pot , egach odpowiednio i , to wykładnik przy NWD ( a,b ) b , edzie min( , ), a przy

NWW ( a,b ) b , edzie max( , ), a wi , ec tak»e po obu stronach wykładniki sumuj , asi , edo tej samej

liczby. Skoro p była dowoln , aliczb , apierwsz , a, to znaczy, »e liczby po obu stronach s , afaktycznie

równe.

4. Ci , ag Fibonacciego

Ci , ag Fibonacciego deﬁniuje si , enast , epuj , aco: F 0 = 0 ,F 1 = 1 ,F n +2 = F n +1 + F n . Warto zna¢ jego

pierwsze kilka warto±ci - 0 , 1 , 1 , 2 , 3 , 5 , 8 , 13 , 21 , 34 , 55 ,... - pomaga to dostrzec ci , ag Fibonacciego

w zadaniach, które w tre±ci wcale go nie maj , a, a zauwa»enie, »e tak naprawd , emowa o tym

ci , agu praktycznie rozwi , azuje zadanie. Ci , ag ten posiada sporo ciekawych własno±ci, niektóre z

nich to:

1. NWD ( F n +1 ,F n ) = 1

Mo»emy zastosowa¢ algorytm Euklidesa i dostajemy: NWD ( F n +1 ,F n ) = NWD ( F n ,F n − 1 ) =

... = NWD ( F 2 ,F 1 ) = NWD ( F 1 ,F 0 ) = NWD (1 , 0) = 1

2. F n = F n − 1 F n +1 + ( − 1) n +1

Dowodzimy poprzez indukcj , e.

Pocz , atek: F 1 = F 2 · F 0 + 1, zgadza si , e.

Krok: F n +1 = F n +1 ( F n + F n − 1 ) = F n F n +1 + F n +1 F n − 1 = F n F n +1 + F n + ( − 1) n +1+1 = F n ( F n +1 +

F n ) + ( − 1) n +2 = F n F n +2 + ( − 1) n +2

3.n | m ) F n | F m

Rozpatrujemy reszty modulo F n . F 0 0 ,F 1 1 ,F 2 1 ,F 3 2 ...F n 0, wi , ec je±li

F n +1 k , to F n +2 k,F n +3 2 k...F 2 n F n · k 0. Podobnie F 3 n 0 itd.

Warto zauwa»y¢, »e maj , ac dane 2 kolejne wyrazy ci , agu mo»emy si , ecofa¢, czyli znajdowa¢

poprzednie wyrazy, tzn. 2 kolejne wyrazy tego ci , agu okre±laj , acały ci , ag.

Konsekwencj , atego jest, »e reszty modulo k dla ka»dego k 2 N powtarzaj , asi , e, czyli je»eli

wyst , apił ju» kiedy± wyraz np. podzielny przez k , to b , edzie ich niesko«czenie wiele.

Istnieje wzór jawny na ci , ag Fibonacciego, tak zwany wzór Bineta:

F n =

p 5 ( 1 + p 5

) n − p 5 ( 1 − p 5

) n

Warto wiedzie¢, »e taki istnieje, ale nie koniecznie trzeba go zna¢.

5. Liczb pierwszych jest niesko«czenie wiele

Dowód: Dowód przeprowadzimy nie wprost. Przypu±¢my, »e jest sko«czenie wiele liczb pierw-

szych, niech b , ed , ato: p 1 ,p 2 ,...,p n . Rozwa»my liczb , e p = p 1 p 2 p 3 ...p n + 1. Zauwa»my, »e

p 1 - p,p 2 - p...p n - p , a zatem p dzieli si , etylko przez 1 i przez sam , asiebie, wi , ec jest liczb , a

pierwsz , a. Dodatkowo p jest wi , eksza od wszystkich p i , wi , ec wcze±niej rozpatrywane liczby nie

były wszystkimi liczbami pierwszymi, w ten sposób doszli±my do sprzeczno±ci.

6. Małe twierdzenie Fermata

Niech p b , edzie liczb , apierwsz , a, n 2 N ,p - n . Wtedy zachodzi n p n mod p (inna wersja:

n p − 1 1 mod p ).

Dowód: Rozpatrzmy zbiór A = { n, 2 n, 3 n,..., ( p − 1) n } mod p . Poka»emy, »e A = { 1 , 2 ,...,p −

1 } . Najpierw zauwa»my, »e wszystkie liczby postaci in mod p s , az zakresu od 1 do p − 1, bo

n ? p oraz i ? p . Oprócz tego wszystkie te liczby s , aró»ne. Przypu±¢my, »e in mod p = jn

mod p . Wtedy p | in − jn , czyli p | n ( i − j ). Jednak p ? n , wi , ec p | i − j . Skoro 1 ¬ i,j ¬ p − 1,

to i − j = 0, czyli i = j . A zatem ka»de dwie liczby tej postaci s , aró»ne. Mamy wi , ec

{ n, 2 n,..., ( p − 1) n } mod p = { 1 , 2 ,...,p − 1 } mod p . Po wymno»eniu stronami dostajemy:

n p − 1 ( p − 1)! ( p − 1)! mod p , jednak ( p − 1)! ? p , wi , ec n p − 1 1 mod p , c.n.d.

7. Tw. Eulera

Niech n 2 N ,a ? n , wtedy a ' ( n ) 1 mod n .

Najpierw wyja±nijmy, »e ' ( n ) jest liczb , aliczb wzgl , ednie pierwszych z n mniejszych od n ,

' ( n ) = |{ 1 ¬ k ¬ n : k ? n }| . Zauwa»my, »e je±li p jest liczb , apierwsz , a, to ' ( p ) = p − 1, bo

wszystkie liczby mniejsze od p s , az ni , awzgl , ednie pierwsze, a ' ( p k ) = p k − 1 ( p − 1), bo nie s , az

ni , awzgl , ednie pierwsze tylko liczby podzielne przez p , czyli co p -ta. Jednocze±nie je»eli a ? b ,

to ' ( ab ) = ' ( a ) ' ( b ), w ten sposób mo»na ju» obliczy¢ ' ( n ) dla ka»dego n 2 N.

Zwró¢my uwag , e, »e małe twierdzenie Fermata jest szczególnym przypadkiem twierdzenia Eu-

lera, gdy» ' ( p ) = p − 1. Przejd¹my teraz do dowodu tw. Eulera, b , edzie on bardzo podobny do

dowodu małego tw. Fermata.

Dowód: niech A = { ka : 1 ¬ k ¬ n,k ? n } mod n . Poka»emy, »e A = { k : 1 ¬ k ¬

n,k ? n } mod n = B . Ka»da liczba ka mod n s , az zakresu od 1 do n − 1 i na dodatek

s , awzgl , ednie pierwsze z n , bo k ? n i a ? n . Poza tym je±li ka mod n = la mod n , to

k 2 A ka Q

k 2 A k mod n , z czego wynika, »e

a ' ( n ) Q

k 2 A k Q

k 2 A k mod n . Jednak poniewa» Q

k 2 A k ? n , to a ' ( n ) 1 mod n , c.n.d.

8. Chi«skie tw. o resztach

Niech n 1 ,n 2 ,...,n k 2 N ,n i ? n j dla i 6 = j,a 1 ,a 2 ,...,a k 2 N. Wtedy istnieje dokładnie

jedna liczba a 2{ 0 , 1 ,...,n 1 n 2 ...n k − 1 } taka, »e a a i mod n i .

Dowód: zauwa»my, najpierw, »e mo»liwych układów reszt modulo n 1 ,n 2 ,...,n k jest n 1 n 2 ...n k .

Zauwa»my te» »e dla ka»dej liczby z przedziału od 0 do n 1 n 2 ...n k − 1 układ reszt, które daje ona

modulo n i jest ró»ny. Gdyby x i y dawały ten sam układ reszt, to n 1 | x − y,n 2 | x − y,...,n k |

x − y , czyli n 1 n 2 ...n k | x − y , a to dla x i y z naszego przedziału mo»liwe jest tylko przy x = y .

A zatem wszystkie układy reszt s , aprzyjmowane i to ka»dy dokladnie raz, czyli jakkolwiek so-

bie nie wybierzemy » , adanego układu znajdziemy dokładnie jedn , aliczb , ew naszym przedziale

realizuj , ac , ate reszty, c.n.d.

9. Tw. Wilsona

n 2 N ,n > 1 jest liczb , apierwsz , awtedy i tylko wtedy gdy ( n − 1)! − 1 mod n

Dowód:

„ ( ” Najpierw dowodzimy w lewo.

Dowodzimy nie wprost. Załó»my, »e n jest zło»one. A zatem n = p 1 · p 2 ,n > p 1 ,p 2 > 1. Wtedy

p 1 | ( n − 1)!, wi , ec ( n − 1)! nie jest wzgl , ednie pierwszy z n . Sprzeczno±¢.

„ ) ” Teraz dowodzimy w prawo.

Liczba p jest pierwsza, wi , ec dla ka»dego k istnieje odwrotno±¢ modulo p , czyli V k W l : k · l 1

mod n . Tylko dwie liczby s , aw parze ze sob , a, s , ato 1 oraz p − 1, gdy» aby p | x 2 − 1 potrzeba,

by p | ( x + 1)( x − 1), czyli p | ( x − 1) lub p | ( x + 1). Liczb od 1 do p − 1 jest parzy±cie wiele,

wi , ec wszystkie dobior , asi , ew pary, czyli ( p − 1)! 1 mod p.

n | a ( k − l ), czyli n | k − l , czyli k = l . Zatem Q

Matematyka dyskretna - teoria liczb II.pdf

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: