Ojlerova funkcija

Ojlerova funkcija 27.05.2005. u 09:08 · pre 261 mesec #1

Kako od nekog velikog broja n naći broj svih uzajamno prostih sa n, to je valjda Ojlerova funkcija. Recimo:

Kako izračunati F(57)?

Re: Ojlerova funkcija 27.05.2005. u 10:31 · pre 261 mesec #2

$n=p_1^{\alpha_1} p_2^{\alpha_2}\ldots p_k^{\alpha_k}$
$\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})\cdots (1-\frac{1}{p_k})$

Potpis

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Re: Ojlerova funkcija 27.05.2005. u 11:04 · pre 261 mesec #3

Ok. Thanks...
Ali bi to u ovom primeru, za 57, bilo kako...?

Re: Ojlerova funkcija 27.05.2005. u 11:32 · pre 261 mesec #4

? Pa zar nije vec dovoljno jasno ?

$57=3\cdot 19$
$\phi (57)=57\cdot (1-\frac {1}{3})\cdot (1-\frac {1}{19})=36$

Potpis

I HAD A NIGHTMARE
IT ALL STARTED NORMAL
10101010
10110011
THEN ALL OF A SUDDEN
1100102
GAAAAH
_____________________________
www.princeton.edu/~skrstic
www.niwifi.co.sr

Re: Ojlerova funkcija 28.05.2005. u 13:53 · pre 261 mesec #5

Uf da...
Hvala puno.
Pozdrav...

Re: Ojlerova funkcija 28.06.2005. u 11:36 · pre 259 meseci #6

Za Ojlerovu funkciju važi i ovo:

$(m,n)=1\;\Longrightarrow\;\varphi(m\cdot n)=\varphi(m)\cdot\varphi(n)$

To jest Ojlerova funkcija je multiplikativna aritmetička funkcija. Dalje, $\varphi(p^n)=p^{n-1}(p-1)$ , što za $p\in{\rm\bold P}$ daje $\varphi(p)=p-1$ .

Konkretno, $(3,19)=1\;\Longrightarrow\;\varphi(3\cdot19)=\varphi(3)\cdot\varphi(19)=2\cdot18=36$ .

Re: Ojlerova funkcija 29.06.2005. u 10:03 · pre 259 meseci #7

Negde sam videla da Ojlerova f-ja slika $N \to N_0$ . A od cega je $\varphi (?) = 0$ ? Koliko je $\varphi (1)$ ?

Re: Ojlerova funkcija 29.06.2005. u 11:52 · pre 259 meseci #8

$\varphi(1)=1$ , ali to što si videla nije pogrešno jer prilikom takvog zapisivanja ne podrazumeva se da sve vrednosti kodomena moraju biti uključene u skup vrednosti funkcije, odnosno kodomen je bilo koji nadskup skupa vrednosti funkcije. Možeš bez problema reći $\varphi:N\rightarrow R$ i opet nisi pogrešila.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Ojlerova funkcija 29.06.2005. u 12:21 · pre 259 meseci #9

Vidi ovo! Sad mi nesto pade na pamet. Jos u januaru sam videla zadatak:

Neka je $\psi (n) = \Sigma \varphi (d) , d \vert n , n \in N$ a $\varphi$ Ojlerova f-ja. Ako je p prost, naci $\psi (p^r).$

Ispostavlja se da je $\psi (p^r) = p^r$ ali mora da bude $\varphi (1) = 1$ da bi se nesto skratilo. Ja sam mislila da se po definiciji uzima $\varphi (1) = 1$ , pa sam bila zbunjena...

Naravno, znam da je "legitimno" i $\varphi : N \to R$ :) ...

Re: Ojlerova funkcija 29.06.2005. u 12:26 · pre 259 meseci #10

Joj, ja sam magarac, pritisnuo sam pogrešan taster pri kucanju. Ispravio sam sad, izvinjavam se na grešci.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Re: Ojlerova funkcija 30.06.2005. u 20:47 · pre 259 meseci #11

Ukoliko za neku funkciju $f:{\rm\bold N}\rightarrow{\rm\bold R}$ važi: $\forall m,n\in{\rm\bold N}\quad(m,n)=1\;\Longrightarrow\;f(mn)=f(m)\,f(n)$ i $g:{\rm\bold N}\rightarrow{\rm\bold R}$ , $g(n)=\sum\limits_{d|n}f(d)$ , onda se može lako dokazati da i za $g$ važi $\forall m,n\in{\rm\bold N}\quad(m,n)=1\;\Longrightarrow\;g(mn)=g(m)\,g(n)$ , odnosno i $g$ je multiplikativna aritmetička funkcija. Za $f:=\varphi$ i $g:=\psi$ se dobija tvrđenje.

Re: Ojlerova funkcija 01.07.2005. u 08:20 · pre 259 meseci #12

Dirichlet-ov proizvod se definiše kao:

$(f\star g)(n):=\displaystyle \sum_{d\vert n}f(d)g(\frac{n}{d})=\sum_{n=d_1 d_2}f(d_1)g(d_2)$

Ako su $f$ i $g$ multiplikativne, onda je i $f\star g$ .
Dokaz:
$(f\star g)(1)=\displaystyle \sum_{d\vert 1}f(d)g(\frac{1}{d})=f(1)g(1)=1$

$(f\star g)(mn)=\displaystyle \sum_{mn=d_1 d_2}f(d_1)g(d_2)$ ,
pošto su $m$ i $n$ uzajamno prosti, onda za svako $d\vert mn$ važi: $d=(d,m)(d,n)$ , pa dobijamo:
$\displaystyle \sum_{mn=d_1 d_2}f(d_1)g(d_2)=\\ =\sum_{mn=d_1 d_2}f((d_1,m)(d_1,n))g((d_2,m)(d_2,n))=\\ =\sum_{mn=d_1 d_2}f((d_1,m))f((d_1,n))g((d_2,m))g((d_2,n))=\\ =\sum_{mn=d_1 d_2}f((d_1,m))g((d_2,m))f((d_1,n))g((d_2,n))=\\ =\sum_{m=d_1 d_2}f(d_1)g(d_2)\sum_{n=d_1 d_2}f(d_1)g(d_2)=\\ =(f\star g)(m)(f\star g)(n)$ ,

Pretposlednja jednakost važi zato što : iz $mn=d_1 d_2$ , sledi i $(d_1,m)(d_2,m)=m$ (i analogno $(d_1,n)(d_2,n)=n$ ). Dakle, svaka faktorizacija $mn=d_1 d_2$ generiše jedinstvene (do na poredak) faktorizacije $m=(d_1,m)(d_2,m)$ i $n=(d_1,n)(d_2,n)$ , kao i obrnuto svake dve faktorizacije $m=d_{1,m}d_{2,m}$ i $n=d_{1,n}d_{2,n}$ generišu jedinstvenu (do na poredak) faktorizaciju $mn=(d_{1,m}d_{1,n})(d_{2,m}d_{2,n})$ za koju je $d_{1,m}=(d_{1,m}d_{1,n},m)$ , $d_{1,n}=(d_{1,m}d_{1,n},n)$ i analogno za $d_{2,m}$ i $d_{2,n}$ .
Time je dokazano tvrđenje.

Primetimo najzad da je funkcija $J(n):=1$ multiplikativna i da je $(f\star J)(n)=\displaystyle \sum_{d\vert n}f(n)$ takođe multiplikativna, pod uslovom da je i f takva.

Što se tiče zadatka, sada nije teško pokazati i $\sum_{d\vert n}\varphi(n)=n$ (naravno, sam zadatak se može rešiti i daleko prostije)

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Ojlerova funkcija 01.07.2005. u 09:39 · pre 259 meseci #13

I još nešto. Cabo, da li bi mogao malo da obrazložiš:

Citat:

Cabo: ...odnosno i $g$ je multiplikativna aritmetička funkcija. Za $f:=\varphi$ i $g:=\psi$ se dobija tvrđenje.

jer ne vidim kako multiplikativnost f-je $g$ povlači tvrđenje, a da prethodno ne upotrebiš samo tvrđenje $\psi(p^r)=p^r$

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Ojlerova funkcija 01.07.2005. u 10:27 · pre 259 meseci #14

Citat:

uranium: Dirichlet-ov proizvod se definiše kao:

$(f\star g)(n):=\displaystyle \sum_{d\vert n}f(d)g(\frac{n}{d})=\sum_{n=d_1 d_2}f(d_1)g(d_2)$

Nisam znao da se konvolucija aritmetičkih funkcija zove još i Dirihletovim proizvodom. U svakom slučaju, za ovu operaciju se koristi termin konvolucija.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Ojlerova funkcija 01.07.2005. u 10:56 · pre 259 meseci #15

Kad smo već kod konvolucije, da li bi mogao da objasniš geometrijski smisao i motivaciju za uvođenje te operacije (mislim na ono sa integralima - nikako da ukapiram

).

Sad mi je nešto palo na pamet.
Definicija multiplikativnosti f-je $f$ zahteva da važi: $f(1)=1$ .

Ako za f-ju $f$ važi $(m,n)=1\Rightarrow f(m\cdot n)=f(m)\cdot f(n)$ , onda je ili $f(1)=0$ ili $f(1)=1$ .
Jer ako je $f(1)=a$ , onda mora biti $f(1)=f(1\cdot 1)=f(1)\cdot f(1)$ tj. $a=a^2$ .
Dakle, ili je $a=0$ ili $a=1$ . E sad, ako bi bilo $a=0$ onda bi bilo i $f(n)=f(1\cdot n)=f(1)\cdot f(n)=0$ (jer je $(n,1)=1$ za svako $n$ ). Znači, jedino nula f-ja bi mogla biti multiplikativna pri ovakvoj definiciji, a to je skroz bezveze, dakle, mora biti $f(1)=1$ .

S druge strane, imam utisak da je neko namerno prilagodio definiciju Ojlerove f-je tako da ona postane multiplikativna u smislu gornje definicije. Oduvek mi je malo "štrčala" 0 u definicije f-je $\varphi(n):=\left | \left\{ (x,n)=1\vert 0\leq x<n \right\}\right |$ . Ako bi u ovoj definiciji bilo, $0<x<n$ (a to mi izgleda mnogo prirodnije), onda bi bilo $\varphi(1)=0$ pa bi ono što je milicas našla u vezi sa kodomenom bilo potpuno opravdano!
Da li neko može da "iskopa" negde originalnu Ojlerovu definiciju ove f-je?

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Ojlerova funkcija 02.07.2005. u 01:23 · pre 259 meseci #16

Citat:

uranium: S druge strane, imam utisak da je neko namerno prilagodio definiciju Ojlerove f-je tako da ona postane multiplikativna u smislu gornje definicije. Oduvek mi je malo "štrčala" 0 u definicije f-je $\varphi(n):=\left | \left\{ (x,n)=1\vert 0\leq x<n \right\}\right |$ . Ako bi u ovoj definiciji bilo, $0<x<n$ (a to mi izgleda mnogo prirodnije), onda bi bilo $\varphi(1)=0$ pa bi ono što je milicas našla u vezi sa kodomenom bilo potpuno opravdano!
Da li neko može da "iskopa" negde originalnu Ojlerovu definiciju ove f-je?

A zašto ne staviš da je $\varphi(n):=\left | \left\{ (x,n)=1\vert 1\leq x\leq n \right\}\right |?$

Primeti da je množenje polinoma zapravo jedna konvolucija nizova, kao i formalno množenje redova. Kontinualni analogon bi bio
$\int_{-\infty}^{+\infty}f(x)dx\cdot\int_{-\infty}^{+\infty}g(y)dy= \int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}f(x)g(t-x)dxdt$
pod uslovom da prva dva integrala postoje i da pritom apsolutno konvergiraju.

Potpis

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Re: Ojlerova funkcija 02.07.2005. u 08:56 · pre 259 meseci #17

Citat:

Nedeljko: A zašto ne staviš da je $\varphi(n):=\left | \left\{ (x,n)=1\vert 1\leq x\leq n \right\}\right |?$

Može i tako

Citat:

Nedeljko:
...Kontinualni analogon bi bio
$\int_{-\infty}^{+\infty}f(x)dx\cdot\int_{-\infty}^{+\infty}g(y)dy= \int_{-\infty}^{+\infty}\int_{-\infty}^{+\infty}f(x)g(t-x)dxdt$
pod uslovom da prva dva integrala postoje i da pritom apsolutno konvergiraju.

Sve je to O.K. ali definicija kaže da dotična formula opisuje meru preklapanja datih funkcija kada jednu od njih (sve jedno je koju) "pomeraš" preko druge - e to mi baš nije očigledno

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Ojlerova funkcija 04.07.2005. u 21:57 · pre 259 meseci #18

Citat:

uranium: I još nešto. Cabo, da li bi mogao malo da obrazložiš:
jer ne vidim kako multiplikativnost f-je $g$ povlači tvrđenje, a da prethodno ne upotrebiš samo tvrđenje $\psi(p^r)=p^r$ :)

Ja nisam ni rekao da je $g$ multiplikativna, već da je $f$ multiplikativna, a da se može lako dokazati da odatle sledi da je $g$ multiplikativna.

Re: Ojlerova funkcija 05.07.2005. u 01:04 · pre 259 meseci #19

Ako upotrebiš modus ponens videćeš da si to ipak rekao

Potpis

_{Attempt all the problems. Those you can do, don't do. Do the ones you cannot.}

Re: Ojlerova funkcija 05.07.2005. u 18:01 · pre 259 meseci #20

Nije mi cilj da se ovde natežem oko sitnica, pa ću dati kompletno tvrđenje i dokaz. Ovo sam imao na umu.

Tvrđenje: Ukoliko za neku funkciju $f: {\rm\bold N}\rightarrow{\rm\bold R}$ važi: $\forall m, n\in{\rm\bold N}\quad(m,n)=1\;\Longrightarrow\;f(mn)=f(m)\,f(n)$ , odnosno ako je funkcija $f$ multiplikativna aritmetička funkcija, onda je funkcija $g: {\rm\bold N}\rightarrow{\rm\bold R}$ , definisana sa $g(n)=\sum\limits_{d|n}f(d)$ , takođe multiplikativna aritmetička funkcija, odnosno važi: $\forall m, n\in{\rm\bold N}\quad(m,n)=1\;\Longrightarrow\;g(mn)=g(m)\,g(n)$ .

Dokaz: Neka je $(m,n)=1$ . Imamo:

$\input amstex \def\suml{\sum\limits} $$\align g(mn)&=\suml_{u|mn}f(u)=\suml_{c|m}\suml_{d|n}f(cd)=\suml_{c|m}\suml_{d|n}f(c)\,f(d)=\\ &=\suml_{c|m}\Bigl(f(c)\suml_{d|n}f(d)\Bigr)=\suml_{c|m}f(c)\,g(n)=g(n)\suml_{c|m}f(c)=\\ &=g(n)\,g(m)=g(m)\,g(n), \endalign$$ \bye$

čime je tvrđenje dokazano.

E, sad, ako primenimo ovo tvrđenje na funkciju $\varphi$ , koja je očito multiplikativna aritmetička funkcija, dobićemo da je i funkcija $\psi$ takođe multiplikativna aritmetička funkcija, pošto je $\psi(n)=\sum\limits_{d|n}\varphi(d)$ .

Forum kao aplikacija na telefonu

Srodne teme