Udowodnić nierówność

[max123321]

Udowodnić, że istnieje bezwzględna dodatnia stała \(\displaystyle{ C}\), że
\(\displaystyle{ \phi (n) \ge C \frac{n}{\log n} }\)
Czy można poprawić \(\displaystyle{ \log n}\) w mianowniku?

Jak to zrobić? Może mi ktoś pomóc?

[DamianTL]

Co to jest \(\displaystyle{ \phi(n)}\)?

[Premislav]

Wynika to łatwo z pewnej klasycznej armaty. Twierdzenie o Liczbach Pierwszych (jak miałeś funkcje analityczne, to się za bardzo nie zdziwisz, jak sądzę):

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Prime_number_theorem

[max123321]

Nie jestem pewien, ale chyba nie miałem jeszcze Twierdzenia o Liczbach Pierwszych na wykładzie, więc nie wiem czy mogę z tego korzystać. Miałem na razie takie rzeczy jak twierdzenie Czebyszewa i tym podobne, więc jak można to jakoś zrobić bez korzystania z TLP to będę wdzięczny.

[Janusz Tracz]

Ze wzoru Legendrea wynika, że wykładnik \(\displaystyle{ p}\)-adyczny (tj.: wykładnik \(\displaystyle{ p}\) w kanonicznej faktoryzacji) \(\displaystyle{ {n \choose k} }\) to:

\(\displaystyle{ \mu_p \left( {n \choose k} \right) = \sum_{i=1}^{ \infty } \left( \left\lfloor \frac{n}{p^i} \right\rfloor - \left\lfloor \frac{k}{p^i} \right\rfloor -\left\lfloor \frac{n-k}{p^i} \right\rfloor \right) }\)

lemat: Dla dowolnych \(\displaystyle{ x,y\in\RR}\) liczba \(\displaystyle{ \left\lfloor x+y \right\rfloor-\left\lfloor x \right\rfloor-\left\lfloor y \right\rfloor}\) jest równa \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\).

Zatem w sumie tej występują jedynie zera i jedynki. Więc \(\displaystyle{ p_i^{ \alpha _i} \le n}\) oraz \(\displaystyle{ {n \choose k} \le n^{\pi (n)}}\). Ostatecznie:

\(\displaystyle{ 2^n = \sum_{k=0}^{n} {n \choose k} \le (n+1)n^{\pi (n)} }\)

zlogarytmuj i oszacuj to co trzeba tak by po jednaj stronie dostać oczekiwane \(\displaystyle{ C \cdot n/ \ln n}\).

[max123321]

A to \(\displaystyle{ \phi (n)}\) to co to jest? Funkcja Eulera, czy \(\displaystyle{ \pi (n)}\)? Jak to należy rozumieć?

[Janusz Tracz]

Nie wiem ja tylko wypisie znaczki w odpowiedzi na Twoje znaczki. Ale mam pomysł. Zadzwoń do wykładowcy i się spytaj.

[DamianTL]

A to \(\displaystyle{ \phi (n)}\) to co to jest? Funkcja Eulera, czy \(\displaystyle{ \pi (n)}\)? Jak to należy rozumieć?

Wygląda jak jedna z nierówności z twierdzenia Czebyszewa, stąd pewnie intuicja chłopaków, że chodzi o \(\displaystyle{ \pi(n).}\) Natomiast co oznacza \(\displaystyle{ \phi (n),}\) to chyba najlepiej właśnie spytać prowadzącego.

[max123321]

Ok, pytałem wykładowcy, \(\displaystyle{ \phi (n)}\) to funkcja Eulera. Jak zatem to zrobić?

Dodano po 2 dniach 19 godzinach 1 minucie 6 sekundach:
Może mi ktoś z tym pomóc?