Funkcja Eulera

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ś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: 13