Tw. o rozkładzie liczby naturalnej na iloczyn liczb pierwszych

Tw. o rozkładzie liczby naturalnej na iloczyn liczb pierwszych

Dla dowolnej liczby naturalnej $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łóżmy 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?ci 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
  1. $a\cdot b = NWD(a, b)\cdot NWW(a, b)$
  2. $NWD(a, b) = NWD(b, a \bmod b)$
  3. $NWD(a_{1}, …, a_{n})=NWD(NWD(a_{1}, a_{2}, …, a_{n-1}), a_{n})$
  4. $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
Post Views: 34