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
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.
Re: tocjent równanie
: 13 cze 2024, o 21:35
autor: 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}.}\)
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ć
Re: tocjent równanie
: 14 cze 2024, o 00:09
autor: 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.}\)
Re: tocjent równanie
: 14 cze 2024, o 00:46
autor: 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.
Re: tocjent równanie
: 14 cze 2024, o 01:39
autor: 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.}\)
Re: tocjent równanie
: 14 cze 2024, o 05:38
autor: 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`)
.
Re: tocjent równanie
: 14 cze 2024, o 10:23
autor: Dasio11
Samouk1 pisze: 14 cze 2024, o 01:39
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.
