Witam.
Może ktoś mi wyjaśnić jak robić te magiczne drzewka tak żeby się w tym nie pogubić??
zadanie jest takie:
Znaleźć wszystkie liczby całkowite dodatnie n takie, że
\(\displaystyle{ \varphi(n)= 24}\)
gdzie \(\displaystyle{ \varphi}\) jest funkcja eulera.
Dzięki za jakąkolwiek pomoc
Funkcja Eulera- Znaleźć liczby całkowite
-
Sherlock
- Użytkownik
- Posty: 2783
- Rejestracja: 19 lis 2008, o 18:45
- Płeć: Mężczyzna
- Lokalizacja: Katowice
- Pomógł: 739 razy
Funkcja Eulera- Znaleźć liczby całkowite
Kilka rozwiązań można otrzymać od razu z własności funkcji Eulera:
\(\displaystyle{ 24=4 \cdot 6=(5-1)(7-1)=\varphi(5)\varphi(7)=\varphi(35)}\)
\(\displaystyle{ 24=2 \cdot 12=(3-1)(13-1)=\varphi(3)\varphi(13)=\varphi(39)}\)
Od kilku dni rozkminiam algorytm opisany w pracy Hansraja Gupta:
... a81_22.pdf
Jeśli połapałem to co powinienem to w celu znalezienia rozwiązań \(\displaystyle{ \varphi^{-1}(24)}\) liczymy co następuje:
1. Wypisujemy dzielniki \(\displaystyle{ m=24}\) czyli \(\displaystyle{ \lbrace1,2,3,4,6,8,12,24\rbrace}\).
2. Dodajemy do dzielników \(\displaystyle{ 1}\) czyli \(\displaystyle{ \lbrace2,3,4,5,7,9,13,25\rbrace}\).
3. Wybieramy liczby pierwsze: \(\displaystyle{ \lbrace2,3,5,7,13\rbrace}\).
4. Teraz tworzymy tabelę gdzie w kolumnie A mamy \(\displaystyle{ p}\) czyli liczby pierwsze z punktu 3 ułożone malejąco, \(\displaystyle{ d}\) (kolumna B) to wykładnik potęgi taki, że \(\displaystyle{ \varphi(p^d)}\) (kolumna D) jest dzielnikiem \(\displaystyle{ m}\).
5. W kolumnie E dzielimy \(\displaystyle{ m=24}\) przez wartość z kolumny D.
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
13 &1 &13 &12 &2& \\
7 &1 &7 &6 &4& \\
5 &1 &5 &4 &6 &\\
3 &1 &3 &2 &12 &\\
3 &2 &9 &6 &4 &\\
\hline
2 &1 &2 &1 &24* &\\
\hline
2 &2 &4 &2 &12 &\\
2 &3 &8 &4 &6 &\\
2 &4 &16 &8 &3 &\\
\hline
\end{tabular}}\)
6. Ostatnia kolumna F zawiera iloczyn kolumny C i elementów zbioru \(\displaystyle{ \varphi^{-1}( \frac{m}{\varphi({p^d})} )}\) (jeśli istnieją) nie posiadających dzielników pierwszych mniejszych lub równych \(\displaystyle{ p}\) (stąd też dodatkowy indeks dolny p). Gwiazdka \(\displaystyle{ *}\) wskazuje wartość w kolumnie E równą \(\displaystyle{ m}\) - w tym wierszu w kolumnie F mnożymy \(\displaystyle{ p^d}\) przez elementy już otrzymane w kolumnach F powyżej (ciężko to wytłumaczyć ale poniżej powinno być już jasne).
Dalsze wyliczenia sprowadzają się więc do znalezienia:
\(\displaystyle{ \varphi^{-1}(2) \\
\varphi^{-1}(4) \\
\varphi^{-1}(6) \\
\varphi^{-1}(12) \\}\)
Dla \(\displaystyle{ \varphi^{-1}(3)}\) nie istnieją rozwiązania.
Dla \(\displaystyle{ \varphi^{-1}(1)=\lbrace1,2\rbrace}\)
Zatem:
\(\displaystyle{ m=2}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
3 &1 &3 &2 &1& 3\cdot\lbrace 1 \rbrace=\lbrace3\rbrace\\
\hline
2 &1 &2 &1 &2*& 2\cdot\lbrace3\rbrace=\lbrace6\rbrace} \\
\hline
2 &2 &4 &2 &1& 4\cdot\lbrace1\rbrace}=\lbrace4\rbrace}\\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(2)=\lbrace3,4,6\rbrace}\)
\(\displaystyle{ m=4}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
5 &1 &5 &4 &1& 5\cdot\lbrace 1 \rbrace=\lbrace5\rbrace\\
3 &1 &3 &2 &2& 3\cdot PUSTY \\
\hline
2 &1 &2 &1 &4*& 2\cdot\lbrace 5 \rbrace=\lbrace10\rbrace\\
\hline
2 &2 &4 &2 &2& 4\cdot\lbrace 3 \rbrace=\lbrace12\rbrace\\
2 &3& 8 &4 &1& 8\cdot\lbrace 1 \rbrace=\lbrace8\rbrace\\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(4)=\lbrace5,8,10,12 \rbrace}\)
\(\displaystyle{ m=6}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
7 &1 &7 &6 &1& 7\cdot\lbrace 1 \rbrace=\lbrace7\rbrace \\
3 &1 &3 &2 &3& - \\
3 &2 &9 &6 &1& 9\cdot\lbrace 1 \rbrace=\lbrace9\rbrace \\
\hline
2 &1 &2 &1 &6*& 2\cdot\lbrace 7,9 \rbrace=\lbrace14,18\rbrace \\
\hline
2 &2 &4 &2 &3& - \\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(6)=\lbrace 7,9,14,18 \rbrace}\)
\(\displaystyle{ m=12}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
13 &1 &13 &12 &1& 13\cdot\lbrace 1 \rbrace=\lbrace13\rbrace \\
7 &1 &7 &6 &2& 7\cdot PUSTY \\
5 &1 &5 &4 &3& - \\
3 &1 &3 &2 &6& 3\cdot\lbrace 7 \rbrace=\lbrace21\rbrace \\
3 &2 &9 &6 &2& 9\cdot PUSTY \\
\hline
2 &1 &2 &1 &12*& 2\cdot\lbrace 13,21 \rbrace=\lbrace26,42\rbrace \\
\hline
2 &2 &4 &2 &6& 4\cdot\lbrace 7,9 \rbrace=\lbrace28,36\rbrace \\
2 &3 &8 &4 &3& - \\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(12)=\lbrace 13,21,26,28,36,42 \rbrace}\)
No to wracamy do naszego problemu:
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
13 &1 &13 &12 &2& 13\cdot PUSTY\\
7 &1 &7 &6 &4& 7\cdot PUSTY\\
5 &1 &5 &4 &6 & 5\cdot\lbrace 7,9 \rbrace=\lbrace35,45\rbrace\\
3 &1 &3 &2 &12 & 3\cdot\lbrace 13 \rbrace=\lbrace39\rbrace\\
3 &2 &9 &6 &4 & 9\cdot\lbrace 5 \rbrace=\lbrace45\rbrace\\
\hline
2 &1 &2 &1 &24* & 2\cdot\lbrace 35,39,45 \rbrace=\lbrace70,78,90\rbrace\\
\hline
2 &2 &4 &2 &12 & 4\cdot\lbrace 13,21 \rbrace=\lbrace52,84\rbrace\\
2 &3 &8 &4 &6 & 8\cdot\lbrace 7,9 \rbrace=\lbrace56,72\rbrace\\
2 &4 &16 &8 &3 & -\\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(24)=\lbrace 35,39,45,52,56,70,72,78,84,90 \rbrace}\)
\(\displaystyle{ 24=4 \cdot 6=(5-1)(7-1)=\varphi(5)\varphi(7)=\varphi(35)}\)
\(\displaystyle{ 24=2 \cdot 12=(3-1)(13-1)=\varphi(3)\varphi(13)=\varphi(39)}\)
Od kilku dni rozkminiam algorytm opisany w pracy Hansraja Gupta:
... a81_22.pdf
Jeśli połapałem to co powinienem to w celu znalezienia rozwiązań \(\displaystyle{ \varphi^{-1}(24)}\) liczymy co następuje:
1. Wypisujemy dzielniki \(\displaystyle{ m=24}\) czyli \(\displaystyle{ \lbrace1,2,3,4,6,8,12,24\rbrace}\).
2. Dodajemy do dzielników \(\displaystyle{ 1}\) czyli \(\displaystyle{ \lbrace2,3,4,5,7,9,13,25\rbrace}\).
3. Wybieramy liczby pierwsze: \(\displaystyle{ \lbrace2,3,5,7,13\rbrace}\).
4. Teraz tworzymy tabelę gdzie w kolumnie A mamy \(\displaystyle{ p}\) czyli liczby pierwsze z punktu 3 ułożone malejąco, \(\displaystyle{ d}\) (kolumna B) to wykładnik potęgi taki, że \(\displaystyle{ \varphi(p^d)}\) (kolumna D) jest dzielnikiem \(\displaystyle{ m}\).
5. W kolumnie E dzielimy \(\displaystyle{ m=24}\) przez wartość z kolumny D.
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
13 &1 &13 &12 &2& \\
7 &1 &7 &6 &4& \\
5 &1 &5 &4 &6 &\\
3 &1 &3 &2 &12 &\\
3 &2 &9 &6 &4 &\\
\hline
2 &1 &2 &1 &24* &\\
\hline
2 &2 &4 &2 &12 &\\
2 &3 &8 &4 &6 &\\
2 &4 &16 &8 &3 &\\
\hline
\end{tabular}}\)
6. Ostatnia kolumna F zawiera iloczyn kolumny C i elementów zbioru \(\displaystyle{ \varphi^{-1}( \frac{m}{\varphi({p^d})} )}\) (jeśli istnieją) nie posiadających dzielników pierwszych mniejszych lub równych \(\displaystyle{ p}\) (stąd też dodatkowy indeks dolny p). Gwiazdka \(\displaystyle{ *}\) wskazuje wartość w kolumnie E równą \(\displaystyle{ m}\) - w tym wierszu w kolumnie F mnożymy \(\displaystyle{ p^d}\) przez elementy już otrzymane w kolumnach F powyżej (ciężko to wytłumaczyć ale poniżej powinno być już jasne).
Dalsze wyliczenia sprowadzają się więc do znalezienia:
\(\displaystyle{ \varphi^{-1}(2) \\
\varphi^{-1}(4) \\
\varphi^{-1}(6) \\
\varphi^{-1}(12) \\}\)
Dla \(\displaystyle{ \varphi^{-1}(3)}\) nie istnieją rozwiązania.
Dla \(\displaystyle{ \varphi^{-1}(1)=\lbrace1,2\rbrace}\)
Zatem:
\(\displaystyle{ m=2}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
3 &1 &3 &2 &1& 3\cdot\lbrace 1 \rbrace=\lbrace3\rbrace\\
\hline
2 &1 &2 &1 &2*& 2\cdot\lbrace3\rbrace=\lbrace6\rbrace} \\
\hline
2 &2 &4 &2 &1& 4\cdot\lbrace1\rbrace}=\lbrace4\rbrace}\\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(2)=\lbrace3,4,6\rbrace}\)
\(\displaystyle{ m=4}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
5 &1 &5 &4 &1& 5\cdot\lbrace 1 \rbrace=\lbrace5\rbrace\\
3 &1 &3 &2 &2& 3\cdot PUSTY \\
\hline
2 &1 &2 &1 &4*& 2\cdot\lbrace 5 \rbrace=\lbrace10\rbrace\\
\hline
2 &2 &4 &2 &2& 4\cdot\lbrace 3 \rbrace=\lbrace12\rbrace\\
2 &3& 8 &4 &1& 8\cdot\lbrace 1 \rbrace=\lbrace8\rbrace\\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(4)=\lbrace5,8,10,12 \rbrace}\)
\(\displaystyle{ m=6}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
7 &1 &7 &6 &1& 7\cdot\lbrace 1 \rbrace=\lbrace7\rbrace \\
3 &1 &3 &2 &3& - \\
3 &2 &9 &6 &1& 9\cdot\lbrace 1 \rbrace=\lbrace9\rbrace \\
\hline
2 &1 &2 &1 &6*& 2\cdot\lbrace 7,9 \rbrace=\lbrace14,18\rbrace \\
\hline
2 &2 &4 &2 &3& - \\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(6)=\lbrace 7,9,14,18 \rbrace}\)
\(\displaystyle{ m=12}\)
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
13 &1 &13 &12 &1& 13\cdot\lbrace 1 \rbrace=\lbrace13\rbrace \\
7 &1 &7 &6 &2& 7\cdot PUSTY \\
5 &1 &5 &4 &3& - \\
3 &1 &3 &2 &6& 3\cdot\lbrace 7 \rbrace=\lbrace21\rbrace \\
3 &2 &9 &6 &2& 9\cdot PUSTY \\
\hline
2 &1 &2 &1 &12*& 2\cdot\lbrace 13,21 \rbrace=\lbrace26,42\rbrace \\
\hline
2 &2 &4 &2 &6& 4\cdot\lbrace 7,9 \rbrace=\lbrace28,36\rbrace \\
2 &3 &8 &4 &3& - \\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(12)=\lbrace 13,21,26,28,36,42 \rbrace}\)
No to wracamy do naszego problemu:
\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}
\hline
A & B & C & D & E & F \\
\hline
p & d & p^d & \varphi(p^d) & m/\varphi(p^d) & p^d \cdot \varphi^{-1}_{p}( m/\varphi(p^d)) \\
\hline
13 &1 &13 &12 &2& 13\cdot PUSTY\\
7 &1 &7 &6 &4& 7\cdot PUSTY\\
5 &1 &5 &4 &6 & 5\cdot\lbrace 7,9 \rbrace=\lbrace35,45\rbrace\\
3 &1 &3 &2 &12 & 3\cdot\lbrace 13 \rbrace=\lbrace39\rbrace\\
3 &2 &9 &6 &4 & 9\cdot\lbrace 5 \rbrace=\lbrace45\rbrace\\
\hline
2 &1 &2 &1 &24* & 2\cdot\lbrace 35,39,45 \rbrace=\lbrace70,78,90\rbrace\\
\hline
2 &2 &4 &2 &12 & 4\cdot\lbrace 13,21 \rbrace=\lbrace52,84\rbrace\\
2 &3 &8 &4 &6 & 8\cdot\lbrace 7,9 \rbrace=\lbrace56,72\rbrace\\
2 &4 &16 &8 &3 & -\\
\hline
\end{tabular}}\)
\(\displaystyle{ \varphi^{-1}(24)=\lbrace 35,39,45,52,56,70,72,78,84,90 \rbrace}\)