Tw. o rozkładzie liczby naturalnej na iloczyn liczb pierwszych
Dla dowolnej liczby naturalne n istnieją liczby pierwsze różne między sobą p1<p2<...<pk oraz liczby naturalne α1,α2,...,αk takie, że
n=p1α1⋅p2α2⋅,...,⋅pkαk
Przykład
Rozłóż liczbę 20 na iloczyn liczb pierwszych
20=2⋅2⋅5=22⋅5
Największy wspólny dzielnik dwóch liczb - NWD
Jeżeli dwie liczby rozłożymy na iloczyn czynników pierwszych
n=p1α1⋅p2α2⋅,...,⋅pkαk
m=p1β1⋅p2β2⋅,...,⋅pkβk
Wykładniki potęg w powyższych iloczynach mogą być równe zeru!
to NWD(n,m)=p1min
Najmniejsza wspólna wielokrotność dwóch liczb - NWW
Jeżeli dwie liczby rozłożymy na iloczyn czynników pierwszych
n = {p_{1}}^ {\alpha_{1}} \cdot {p_{2}}^ {\alpha_{2}} \cdot, ... , \cdot {p_{k}}^ {\alpha_{k}}
m = {p_{1}}^ {\beta_{1}} \cdot {p_{2}}^ {\beta_{2}} \cdot, ... , \cdot {p_{k}}^ {\beta_{k}}
Wykładniki potęg w powyższych iloczynach mogą być równe zeru!
to NWW(n, m)={p_{1}}^ {\max(\alpha_{1},\beta_{1})} \cdot {p_{2}}^ {\max(\alpha_{2},\beta_{2})} \cdot, ... , \cdot {p_{k}}^ {\max(\alpha_{k},\beta_{k})}
analogicznie wprowadzamy NWD i NWW wielu liczb.
Przykład
Oblicz NWD(96, 112) oraz NWW(96, 112).
Rozkładamy liczby na iloczyn czynników pierwszych
96=2\cdot2\cdot2\cdot 2\cdot2\cdot 3=2^{5}\cdot 3^{1}\cdot 7^{0}
112=2\cdot 2\cdot 2\cdot 2 \cdot 7^{1} =2^{4}\cdot 3^{0} \cdot 7^{1}
Zatem
NWW(96,112) = 2^{\max{(5,4)}}\cdot 3^{\max{(1, 0)}} \cdot 7^{\max{(0,1)}}
NWW(96,112) = 2^{5}\cdot 3^{1} \cdot 7^{1} = 32\cdot 3\cdot 7= 672
NWD(96,12)=2^{\min{(5,4)}}\cdot 3^{\min{(1, 0)}} \cdot 7^{\min{(0,1)}}
NWD(96,12)=2^{4}\cdot 3^{0} \cdot 7^{0}
NWD(96,12)=16\cdot 1 \cdot 1 = 16
Własności przydatne w programowaniu
- a\cdot b = NWD(a, b)\cdot NWW(a, b)
- NWD(a, b) = NWD(b, a \bmod b)
- NWD(a_{1}, ..., a_{n})=NWD(NWD(a_{1}, a_{2}, ..., a_{n-1}), a_{n})
- NWW(a_{1}, ..., a_{n})=NWW(NWW(a_{1}, a_{2}, ..., a_{n-1}), a_{n})
Dowód 1)
Rozłóżmy obie liczby na iloczyn czynników pierwszych
a = {p_{1}}^ {\alpha_{1}} \cdot {p_{2}}^ {\alpha_{2}} \cdot, ... , \cdot {p_{k}}^ {\alpha_{k}}
b = {p_{1}}^ {\beta_{1}} \cdot {p_{2}}^ {\beta_{2}} \cdot, ... , \cdot {p_{k}}^ {\beta_{k}}
Wtedy
NWD(a, b)\cdot NWW(a, b)={p_{1}}^ {\min(\alpha_{1},\beta{1})} \cdot {p_{2}}^ {\min(\alpha_{2},\beta{2})} \cdot, ... , \cdot {p_{k}}^ {\min(\alpha_{k},\beta{k})}\cdot \cdot {p_{1}}^ {\max(\alpha_{1},\beta_{1})} \cdot {p_{2}}^ {\max(\alpha_{2},\beta_{2})} \cdot, ... , \cdot {p_{k}}^ {\max(\alpha_{k},\beta_{k})}=
{p_{1}}^ {\min{(\alpha_{1},\beta_{1})}+\max{(\alpha_{1},\beta_{1})}} \cdot {p_{2}}^ {\min{(\alpha_{2},\beta_{2})}+\max{(\alpha_{2},\beta_{2})}} \cdot, ... , \cdot {p_{k}}^ {\min{(\alpha_{k},\beta_{k})}+\max{(\alpha_{k},\beta_{k})}}=
{p_{1}}^ {\alpha_{1}+\beta_{1}}+ \cdot {p_{2}}^ {{\alpha_{2}+\beta_{2}}} \cdot, ... , \cdot {p_{k}}^ {{\alpha_{k}+\beta_{k}}}=a\cdot b
Dowody własności 3) i 4) można przeprowadzić analogicznie opierając się na równościach
\min({\min{(a_{1}, ..., a_{k-1})}, a_{k})}=\min{(a_{1}, ... ,a_{k})}
\max({\max{(a_{1}, ..., a_{k-1})}, a_{k})}=\max{(a_{1}, ... ,a_{k})}
Z własności 3) łatwo policzyć NWW mając dane NWD dwóch liczb.
NWW(96, 112)= (96:NWD(96, 112))\cdot 112 = 96:16 \cdot 112 = 6\cdot 112= 672
Z własności 3) lub 4) łatwo policzyć NWD lub NWW z wielu liczb (z k liczb).
Przykłady
Oblicz NWD(24,36,42)
Rozwiązanie
Z własności 3) mamy
NWD(24,36,42)=NWD(NWD(24,36),42)=...
Dokończ obliczenia.
powrót do spisu
