Funkcja eulera w zadaniach

[nowik1991]

1) \(\displaystyle{ \phi (10!) =?}\)

2) Znajdź jakąkolwiek liczbę, dla której\(\displaystyle{ \phi(n) = 1000}\)

3) Sprawdź czy \(\displaystyle{ \phi (n) = 14}\) posiada rozwiązania?

4) Czy każda liczba naturalna jest wartością funkcji \(\displaystyle{ \phi(n)}\)

[Pancernik]

1) \(\displaystyle{ \phi \left( 10!\right) =829440}\)

Wiesz jak działa ta funkcja?

[nowik1991]

Tzn. powiem tak dla prostych liczb wiem:

Jeżeli np mamy \(\displaystyle{ \phi (5) = (5-1) = 4}\) dla liczb nieparzystych.

Natomiast jak jest liczba parzysta to rozkładamy na czynniki pierwsze ale w przypadku \(\displaystyle{ 10!}\) niestety nie wiem jak to działa.

[Pancernik]

Tzn. powiem tak dla prostych liczb wiem:

Jeżeli np mamy \(\displaystyle{ \phi (5) = (5-1) = 4}\) dla liczb nieparzystych.

Hymm, chyba jednak nie wiesz.
Bo np. \(\displaystyle{ \phi (15)=8}\)

Tak jest dla liczb pierwszych: \(\displaystyle{ \phi (p) = (p-1)}\)

[nowik1991]

Mhm no to ok. Jednak nie wiedziałbym jak należy obliczyć \(\displaystyle{ 10!}\) i te pozostałe przykłady.

[Pancernik]

Tu jest fajnie wyjaśniona ta funkcja:

\(\displaystyle{ 10!=1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7 \cdot 8 \cdot 9 \cdot 10}\)

Rozkładamy teraz na czynniki pierwsze.
\(\displaystyle{ 10!=2 \cdot 3 \cdot 2\cdot 2 \cdot 5 \cdot 2\cdot 3 \cdot 7 \cdot 2\cdot 2\cdot 2 \cdot 3\cdot 3 \cdot 2\cdot 5=2^8\cdot 3^4\cdot 5^2\cdot 7}\)

Teraz mamy iloczyn liczb względnie pierwszych, czyli możemy zrobić tak:
\(\displaystyle{ \phi \left( 10!\right) =\phi \left(2^8\right)\cdot \phi \left(3^4\right)\cdot \phi \left(5^2\right)\cdot \phi \left(7\right)}\)

Rozpisze każdą funkcję osobno:
\(\displaystyle{ \phi \left(2^8\right)=2^8 \cdot \left( 1- \frac{1}{2} \right) =2^8 \cdot \frac{1}{2} =2^7=128\\
\phi \left(3^4\right)=3^4 \cdot \left( 1- \frac{1}{3} \right) =3^4 \cdot \frac{2}{3} =3^3 \cdot 2=54\\
\phi \left(5^2\right)=5^2 \cdot \left( 1- \frac{1}{5} \right) =5^2 \cdot \frac{4}{5} =5 \cdot 4=20\\
\phi \left(7\right)=7 \cdot \left( 1- \frac{1}{7} \right) =7 \cdot \frac{6}{7} =6}\)

\(\displaystyle{ \phi \left( 10!\right) =128 \cdot 54 \cdot 20 \cdot 6=829440}\)

[nowik1991]

A np \(\displaystyle{ 7!}\) by było równe:

\(\displaystyle{ 7! = 1 \cdot 2 \cdot 3 \cdot 4 \cdot 5 \cdot 6 \cdot 7}\)

\(\displaystyle{ 7!= 2 \cdot 3 \cdot 2 \cdot 2 \cdot \cdot 5 \cdot 2 \cdot 3 \cdot 7}\)

\(\displaystyle{ \phi (7!) = \phi (2^4) \cdot \phi(3^2) \cdot \phi (5) \cdot \phi(7) = 8 \cdot 3 \cdot 4 = 96}\)

I to jest dobry wynik?

[Pancernik]

Dobrze rozłożyłeś, ale źle policzyłeś.

\(\displaystyle{ \phi (2^4) =8\\
\phi(3^2) =6\\
\phi (5) =4\\
\phi(7) =6}\)

[nowik1991]

a no tak...przepraszam przeoczenie...bo nie rozpisałem tego na kartce.

Ok a wiedziałbyś może jak zrobić dalsze zadania?

[Pancernik]

W 4) jest odpowiedź NIE.

No bo wartości dla \(\displaystyle{ n \in \mathbb{N} \setminus \left\{ 1,2\right\}}\) są parzyste. Dla \(\displaystyle{ n \in \left\{ 1,2\right\}, \phi \left( n\right) = 1}\).

Dowód:
Weźmy \(\displaystyle{ n \in \mathbb{N} \setminus \left\{ 1,2\right\}}\) i niech
\(\displaystyle{ \left( p_k\right) _{k=1,2,\dots}}\) - dzielniki liczby \(\displaystyle{ n}\), które są pierwsze i \(\displaystyle{ k \le n}\)
\(\displaystyle{ p_1 = 2}\) - jeśli \(\displaystyle{ n}\) parzyste (w przeciwnym razie nieparzyste)
\(\displaystyle{ \left( p_k\right) _{k=2,3,\dots}}\) - nieparzyste dzielniki pierwsze liczby \(\displaystyle{ n}\)
to
\(\displaystyle{ \phi \left( n\right)=n \cdot \frac{p_1-1}{p_1} \cdot \frac{p_2-1}{p_2} \cdot \dots \cdot \frac{p_k-1}{p_k}}\)
\(\displaystyle{ p_k-1}\) - parzyste

Czyli liczba parzysta i nieparzysta pomnożona przez liczbę parzystą jest parzysta.

Więc wartościami są liczby parzyste.-- 23 gru 2012, o 01:48 --Nie wiem jeszcze jak poprawnie wyliczyć zadania 2 i 3 ale odpowiedzi są takie:

2)
\(\displaystyle{ \phi \left(1111\right)=1000\\
\phi \left(1255\right)=1000\\
\phi \left(1375\right)=1000\\
\phi \left(1875\right)=1000\\
\phi \left(2008\right)=1000\\
\phi \left(2222\right)=1000\\
\phi \left(2500\right)=1000\\
\phi \left(2510\right)=1000\\
\phi \left(2750\right)=1000\\
\phi \left(3012\right)=1000\\
\phi \left(3750\right)=1000}\)
Wydaje mi się, że to wszystkie możliwości.

3) Nie posiada rozwiązań.

[nowik1991]

Ja bym 2 zrobił tak:

\(\displaystyle{ 1000 = 2 \cdot 500 = (3-1) \cdot (501-1) = \phi(3) \cdot \phi(501) = \phi (1503)}\)

Nie wiem czy to dobry sposób bo według niego:

\(\displaystyle{ 14 = 2 \cdot 7 = (3-1) \cdot (8-1) = \phi( 24)}\)

[Pancernik]

A policz \(\displaystyle{ \phi\left( 1503\right)}\) i \(\displaystyle{ \phi\left( 24\right)}\). I ile ci wyjdzie? bo na pewno nie to:

Ja bym 2 zrobił tak:

\(\displaystyle{ 1000 = 2 \cdot 500 = (3-1) \cdot (501-1) = \phi(3) \cdot \phi(501) = \phi (1503)}\)

Nie wiem czy to dobry sposób bo według niego:

\(\displaystyle{ 14 = 2 \cdot 7 = (3-1) \cdot (8-1) = \phi( 24)}\)

-- 25 gru 2012, o 02:08 --

Z drugiej strony mały to być liczby względnie pierwsze. A te nie są:

\(\displaystyle{ \phi(3) \cdot \phi(501)}\)

\(\displaystyle{ \mbox{NWD}\left( 3,501\right) =3}\)

A powinno być tak: \(\displaystyle{ \mbox{NWD}\left( a,b\right) =1}\)-- 25 gru 2012, o 02:13 --A to co wykorzystałeś działa dl liczb pierwszych, a \(\displaystyle{ 501}\) i \(\displaystyle{ 8}\) nie są pierwsze.

[nowik1991]

Korzystałem z: 305918.htm#p4964185

Czyli tam jest źle?

-- 25 gru 2012, o 12:27 --

Czyli jednym słowem mam zawsze szukać liczb pierwszych tak? Czy jest jakiś sposób na złożone?-- 25 gru 2012, o 12:36 --\(\displaystyle{ 1000 = 10 \cdot 100 = (11-1) \cdot (101-1) = \phi(11) \cdot \phi(101) = \phi (1111)}\)

Czyli chyba by się zgadzało

\(\displaystyle{ 1000 = 4 \cdot 250 = (5-1) \cdot (251-1) = \phi(5) \cdot \phi(251) = \phi (1255)}\)

[Pancernik]

Najlepiej szukać liczb pierwszych, albo ich wielokrotności -- 26 gru 2012, o 18:02 --Nie wielokrotności tylko kolejnych potęg.