Podzielność

Notatka Nr 3								15.03.04

WSKiZ

Matematyka Dyskretna

Notacja.
•	mn		- liczba m dzieli n

Własności relacji podzielności
•	Jeśli m|a i m|b, to m|(a+b) i m|(a-b)
•	Jeśli m|a i a|b, to m|b (tę własność nazywamy przechodniością podzielności)
•	Jeśli m|a, to dla każdej liczby całkowitej b, m|ba
•	Jeśli m|a i a0, to |m||a|
•	Jeśli m|a i a|m, to m=a  lub m=-a

Z tych własności wynika wprost następujący fakt.
Fakt. Jeśli a, b Z  i b0, to istnieje dokładnie jedna para liczb q, r taka, że 0r<q oraz a=bq+r.

Definicja. Liczba naturalna n>1 jest liczbą pierwszą, jeśli jedynymi jej dzielnikami są 1 i n.

Twierdzenie. Każda liczba naturalna da się przedstawić w postaci iloczynu liczb pierwszych. Rozkład ten jest jednoznaczny.

Wnioski.
•	Jeśli liczba pierwsza p dzieli iloczyn ab, to p|a lub p|b.
•	Jeśli m|a i n|a oraz m i n nie mają wspólnych dzielników większych od 1, to mn|a.

Definicja. Liczbę d nazywamy wspólnym dzielnikiem liczb n i m, jeśli d|n oraz d|n. Największy wspólny dzielnik liczb n i m oznaczamy przez NWD(n,m).

Definicja. Jeśli NWD(n,m)=1, to mówimy, że liczby n i m są względnie pierwsze.

Problem: Znajdowanie największego wspólnego dzielnika.
Dane: n,m – liczby naturalne
Wynik: NWD(n,m)

Sposób nr 1.
1.	Rozkładamy n na czynniki pierwsze
2.	Rozkładamy m na czynniki pierwsze
3.	Wyznaczamy wszystkie liczby, które wystąpiły w obydwu rozkładach. Obliczamy ich iloczyn, biorąc każdą z nich tyle razy, ile razy wystąpiła w każdym z rozkładów (dokładniej: jeśli liczba p występuje w rozkładzie n kn razy  a w rozkładzie m – km razy, to p bierzemy do iloczynu min{kn,km}  razy).

Algorytm ten może być stosowany jedynie dla niewielkich liczb, bądź też dla liczb, dla których znamy rozkład na czynniki pierwsze.

Sposób nr 2. (Algorytm Euklidesa)

Korzystamy z następującego spostrzeżenia:
Przykład.
Niech n=10920 a m=53508.
Jak łatwo sprawdzić n=22235713   a m=22377713.
Największy wspólny dzielnik d wyznaczamy jako 223713,  a więc równa się on 1092.  

Fakt. Niech n,m będą liczbami naturalnymi i nm. Wówczas NWD(n,m)=NWD(m,m), gdzie n MOD m  oznacza resztę z dzielenia n  przez m.

Te fakt prowadzi do następującego algorytmu:

function NWD(n,m)
A0max{n,m}
A1min{n,m}
i1
while Ai>0 do 
	Ai+1Ai-1 MOD Ai
	ii+1
NWDAi-1

Zaletą algorytmu Euklidesa jest jego szybkość. Można sprawdzić, że wykonuje on O(log(max {n,m})) iteracji. 

Problem: Znajdowanie najmniejszej wspólnej wielokrotności.

Definicja. Każdą liczbę naturalną podzielną przez liczbą n nazywamy wielokrotnością liczby n.

Definicja. Najmniejszą wspólną wielokrotnością liczb n i m nazywamy najmniejszą liczbę naturalną (większą od zera), która jest jednocześnie wielokrotnością n i m (oznaczamy ją przez NWW(n,m)).

Najmniejszą wspólną wielokrotność możemy wyznaczyć z następującego wzoru:

Fakt. NWW(n,m)=nm/NWD(n,m).

Tak więc aby obliczyć NWW(n,m) wystarczy iloczyn liczb n i m podzielić przez NWD(n,m). 

Podobnie jak NWD(n,m), najmniejszą wspólną wielokrotność n i m, można łatwo wyznaczyć, znając rozkład n i m  na czynniki pierwsze. Również teraz liczymy iloczyn liczb, które wystąpiły w rozkładach, tym razem jednak jeśli liczba p występuje w rozkładzie n kn razy  a w rozkładzie m – km razy, to p bierzemy do iloczynu max{kn,km}  razy.

Przykład.
Niech podobnie jak poprzednio n=10920 a m=53508.
NWW(n,m)= 2223577713=535080.

Uogólniony algorytm Euklidesa.

Problem. 
	Dane: a, b  N
	Szukane: s i t, takie, że NWD(a,b)=sa+tb.

	Innymi słowy chcemy wyrazić NWD(a,b) jako liniową kombinację liczb a i b.

Rozwiązanie: Uogólniony algorytm Euklidesa.

Zauważmy, że algorytm Euklidesa oblicza ciąg A_i, taki, że A0=max{a,b}, A1=min{a,b}, a przedostatni element tego ciągu jest równy NWD(a,b). Idea uogólnionego algorytmu Euklidesa polega na tym, że wszystkie Ai (jakie są wyliczane przez zwykły algorytm Euklidesa) wyrażamy jako liniowe kombinacje liczb a i b. Możemy to łatwo zrobić dla A0 i A1: oczywiście A0=1a+0b oraz A1=0a+1b. Dla kolejnych Ai kombinację liniową możemy łatwo wyznaczyć znając kombinacje dla Ai-1 oraz Ai-2.. Niech bowiem Ai=sia+tib oraz Ai-1=si-1a+ti-1b. Ponieważ Ai+1=Ai-1-diAi, gdzie di=Ai-1 div Ai, więc mamy
Ai+1= si-1a+ti-1b-di(sia+tib).
Stąd Ai+1=(si-1-disi)a+(ti-1-diti)b, a więc si+1= si-1-disi oraz ti+1=ti-1-diti

Przykład.
Niech a=99 i b =13.
Ai	di	si	ti	
99		1	0	
13	7	0	1	
8	1	1	-7	
5	1	-1	8	
3	1	2	-15	
2	1	-3	23	
1	1	5	-38	
0				

Otrzymaliśmy więc NWD(99,13)=1=599-3813.