Tw. o rozkładzie liczby naturalnej na iloczyn liczb pierwszych
Dla dowolnej liczby naturalne $n$ istniej± liczby pierwsze różne między sob± $p_{1} < p_{2} < ... < p_{k}$ oraz liczby naturalne $\alpha_{1}, \alpha_{2}, ..., \alpha_{k}$ takie, że
$$n = {p_{1}}^ {\alpha_{1}} \cdot {p_{2}}^ {\alpha_{2}} \cdot, ... , \cdot {p_{k}}^ {\alpha_{k}}$$
Przykład
Rozłóż liczbę 20 na iloczyn liczb pierwszych
$20 = 2\cdot 2\cdot 5=2^{2}\cdot5$
Największy wspólny dzielnik dwóch liczb - NWD
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 $$NWD(n, m)={p_{1}}^ {\min(\alpha_{1},\beta{1})} \cdot {p_{2}}^ {\min(\alpha_{2},\beta{2})} \cdot, ... , \cdot {p_{k}}^ {\min(\alpha_{k},\beta{k})}$$
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
