tocjent równanie

[bazyl01]

Rozwiąż równanie \(\displaystyle{ \phi(n)=10}\). Jakże krótkie polecenie, a zastanawiam się jak je ruszyć?

[Janusz Tracz]

Brutalna metoda z wykorzystaniem nietrywialnych oszacowań:    

Dla \(\displaystyle{ n>2}\) zachodzą nierówności

\(\displaystyle{ {\frac {n}{e^{\gamma } \ln \ln n+{\frac {3}{\ln \ln n}}}} < \phi (n)\le n-1.}\)

Zatem jeśli ma zachodzić \(\displaystyle{ \phi(n)=10}\) to \(\displaystyle{ n}\) musi spełniać odpowiednie nierówności. Jedna oczywista \(\displaystyle{ 11\le n}\) oraz mniej oczywista

\(\displaystyle{ {\frac {n}{e^{\gamma } \ln \ln n+{\frac {3}{\ln \ln n}}}} < 10}\)

jednak numerycznie do ogarnięcia, dająca, że \(\displaystyle{ n\le 46}\). Skończenie wiele przypadków można już zbadać ręcznie, \(\displaystyle{ n=11}\) oraz \(\displaystyle{ n=22}\) to imho jedyne dobre. Nie twierdzę, że to jest kanoniczne (i najprostsze) rozwiązanie ale to jest metoda, która zadziała zawsze.

[bazyl01]

Może tak zacząć. Jeśli liczba pierwsza \(\displaystyle{ p}\) dzieli \(\displaystyle{ n}\), to \(\displaystyle{ (p-1)\lvert \phi(n)=10}\).
Mamy \(\displaystyle{ D_{10}=\{1,2,5,10\}}\), a więc \(\displaystyle{ (p-1)\in\{1,2,5,10\}}\) stąd \(\displaystyle{ p\in\{2,3,11\}}\), zatem liczba \(\displaystyle{ n}\) musi być postaci \(\displaystyle{ n=2^a3^b11^c.}\)

Skorzystam z faktu, że funkcja \(\displaystyle{ \phi}\) jest multiplikatywna i że dla liczby pierwszej \(\displaystyle{ p}\) zachodzi równość \(\displaystyle{ \phi(p^n)=(p-1)p^{n-1}.}\)

\(\displaystyle{ \phi(n)=\phi(2^a3^b11^c)=(2-1)2^{a-1}(3-1)3^{b-1}(11-1)11^{c-1}=2^{a-1}\cdot2\cdot3^{b-1}\cdot10\cdot11^{c-1}=2^{a+1}\cdot3^{b-1}\cdot5\cdot11^{c-1}}\).

Z drugiej zaś strony \(\displaystyle{ 3\nmid 10}\) oraz \(\displaystyle{ 11\nmid 10}\), więc \(\displaystyle{ b,c \le 1}\).

I tu dalej nie wiem jak ograniczać

[Samouk1]

Dla liczby \(\displaystyle{ 10}\) można(?) to zrobić jeszcze (też dość brutalnie) korzystając z twierdzenie Eulera. Wiemy, że \(\displaystyle{ a^{\phi(n)} \equiv 1 (\mbox{mod n})}\) dla \(\displaystyle{ a}\) i \(\displaystyle{ n}\) względnie pierwszych.

\(\displaystyle{ \phi(n) = 10}\)

\(\displaystyle{ 3^{\phi(n)} = 3^{10}}\)

Teraz z twierdzenia Eulera: \(\displaystyle{ 3^{10} - 1 \equiv 0 (\mbox{mod n})}\)

czyli równość spełnia dzielnik liczby \(\displaystyle{ 3^{10}-1 = 59 048 = 2^3 \cdot 11^2 \cdot 61.}\) Teraz zostaje ta brutalna część czyli sprawdzenie \(\displaystyle{ 24}\) dzielników ręcznie. Co faktycznie daje \(\displaystyle{ 11}\) i \(\displaystyle{ 22.}\)

[bazyl01]

A to moje rozwiązanie ktoś wie jak dociągnąć do końca?

Dodano po 51 minutach 31 sekundach:
Już dałem radę, dziękuję za pomoc i komentarze.

[Samouk1]

Być może trop dobry, ale funkcja \(\displaystyle{ \phi}\) nie jest zawsze multiplikatywna, przykładowo \(\displaystyle{ 8 = \phi(16) = \phi(4 \cdot 4) \neq \phi(4) \cdot \phi(4) = 4.}\) Być może nie widzę czegoś oczywistego, ale tutaj potrzebuję uzasadnienia.

Szukasz ograniczenia \(\displaystyle{ a.}\) Tutaj możesz skorzystać z mojego ograniczenia: \(\displaystyle{ n}\) jest dzielnikiem liczby \(\displaystyle{ 2^3 \cdot 11^2 \cdot 61}\) zatem \(\displaystyle{ a \le 3.}\)

[a4karo]

Jeżeli \(\displaystyle{ n= \prod {p_i}^{k_i} }\) to \(\displaystyle{ \phi(n)= \prod {p_i}^{k_i-1}(p_i-1) }\), zatem \(\displaystyle{ p_i-1|10}\), co ogranicza czynniki pierwsze do zbioru \(\displaystyle{ \{2,3,11\}}\).
Ponieważ \(\displaystyle{ \phi(2^a3^b)}\) nie dzieli się prze `5`, czynnik `11` jest konieczny, a wtedy `\phi(n)\ge \phi(11)=10`, co oznacza tylko dwie możliwości: `n=11` lub `n=22` (bo `\phi(2)=1`)
.

[Dasio11]

Być może trop dobry, ale funkcja \(\displaystyle{ \phi}\) nie jest zawsze multiplikatywna, przykładowo \(\displaystyle{ 8 = \phi(16) = \phi(4 \cdot 4) \neq \phi(4) \cdot \phi(4) = 4.}\) Być może nie widzę czegoś oczywistego, ale tutaj potrzebuję uzasadnienia.

W teorii liczb bycie funkcją multiplikatywną nie wymaga, by wzór \(\displaystyle{ \phi(x \cdot y) = \phi(x) \cdot \phi(y)}\) zachodził dla wszystkich liczb naturalnych \(\displaystyle{ x}\), \(\displaystyle{ y}\), a jedynie dla względnie pierwszych.