Witam właśnie mam zadanie sprawdzić czy:
\(\displaystyle{ \phi(n) = 14}\)
Myślę, że to nie zachodzi....
dzielniki możliwe to \(\displaystyle{ 2}\) oraz \(\displaystyle{ 7}\) więc musiałabym to zapisać tak:
\(\displaystyle{ \phi(n) = 14 = 2 \cdot 7 = (3-1) \cdot (8-1) = \phi(24)}\) co oczywiście nie ma bytu ponieważ \(\displaystyle{ \phi(24) = 2^3 \cdot 3 = 4 \cdot 2 = 8}\) czyli \(\displaystyle{ \neq}\). Czyli abyśmy mogli znaleźć takie \(\displaystyle{ n}\) to byśmy musieli mieć dzielniki parzyste.
Tylko właśnie nie wiem czy wystarczy takie zapisanie...
Proszę o pomoc
Funkcja Eulera - dowod
-
angela1992
- Użytkownik
- Posty: 6
- Rejestracja: 28 gru 2012, o 13:29
- Płeć: Kobieta
- Lokalizacja: tu i tam
- Podziękował: 2 razy
-
pawellogrd
- Użytkownik
- Posty: 844
- Rejestracja: 19 lis 2009, o 15:03
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 121 razy
- Pomógł: 156 razy
Funkcja Eulera - dowod
A skąd takie przejście: \(\displaystyle{ (3-1) \cdot (8-1) = \phi(24)}\) ? Ono jest błędne, bo jeśli korzystałaś z tego, że \(\displaystyle{ \phi(n)=(p_1-1)(p_2=1)...(p_k-1) \mbox{ gdzie } n=p_1 \cdot p_2 \cdot ... \cdot p_k}\) to zauważ, że liczby \(\displaystyle{ p_1, p_2, ... , p_k}\) muszą być pierwsze. A liczba \(\displaystyle{ 8}\) raczej pierwsza nie jest.
Uogólniając powyższe, jeśli \(\displaystyle{ n=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot ... \cdot p_k^{\alpha_k}}\), to zachodzi \(\displaystyle{ \phi(n) = p_1^{\alpha_1 - 1} \cdot (p_1 - 1) \cdot ... \cdot p_k^{\alpha_k - 1} \cdot (p_k - 1)}\)
(Powyższe było przypadkiem, gdy \(\displaystyle{ \alpha_1 = \alpha_2 = ... = \alpha_k = 1}\))
Stąd nie ma liczb \(\displaystyle{ p>15}\) dzielących się przez \(\displaystyle{ n}\), inaczej zachodziłoby \(\displaystyle{ \phi(n)>p-1>14}\), co byłoby sprzecznością. Zatem możliwymi liczbami pierwszymi \(\displaystyle{ p}\) są: \(\displaystyle{ 2,3,5,7,11,13}\) ale \(\displaystyle{ 5,7,11,13}\) mogą być odrzucone od razu ze względu na to, że \(\displaystyle{ 14}\) nie dzieli się przez \(\displaystyle{ 4,6,10,12}\). Zostają nam: \(\displaystyle{ 2,3}\) zatem otrzymujemy:
\(\displaystyle{ n=2^{\alpha} \cdot 3^{\beta}}\), stąd \(\displaystyle{ \phi(n)=2^{\alpha-1} \cdot (2-1) \cdot 3^{\beta - 1} \cdot (3-1) = 2^{\alpha} \cdot 3^{\beta - 1}}\)
Zatem mamy do rozwiązania równanie \(\displaystyle{ 2^{\alpha} \cdot 3^{\beta - 1} = 14}\) gdzie \(\displaystyle{ \alpha=1}\), bo w innym przypadku liczba \(\displaystyle{ 14}\) nie byłaby podzielna przez \(\displaystyle{ 2^{\alpha}}\), więc równanie nie miałoby rozwiązania. Zatem mamy do rozwiązania:
\(\displaystyle{ 2 \cdot 3^{\beta - 1} = 14}\)
Dzielimy obustronnie przez \(\displaystyle{ 2}\) i otrzymujemy:
\(\displaystyle{ 3^{\beta - 1} = 7}\)
Oczywiście nie istnieje taka liczba całkowita \(\displaystyle{ \beta}\), żeby powyższe równanie było spełnione. Zatem otrzymaliśmy sprzeczność stąd wniosek, że nie istnieje takie \(\displaystyle{ n}\), dla którego \(\displaystyle{ \phi(n)=14}\)
Uogólniając powyższe, jeśli \(\displaystyle{ n=p_1^{\alpha_1} \cdot p_2^{\alpha_2} \cdot ... \cdot p_k^{\alpha_k}}\), to zachodzi \(\displaystyle{ \phi(n) = p_1^{\alpha_1 - 1} \cdot (p_1 - 1) \cdot ... \cdot p_k^{\alpha_k - 1} \cdot (p_k - 1)}\)
(Powyższe było przypadkiem, gdy \(\displaystyle{ \alpha_1 = \alpha_2 = ... = \alpha_k = 1}\))
Stąd nie ma liczb \(\displaystyle{ p>15}\) dzielących się przez \(\displaystyle{ n}\), inaczej zachodziłoby \(\displaystyle{ \phi(n)>p-1>14}\), co byłoby sprzecznością. Zatem możliwymi liczbami pierwszymi \(\displaystyle{ p}\) są: \(\displaystyle{ 2,3,5,7,11,13}\) ale \(\displaystyle{ 5,7,11,13}\) mogą być odrzucone od razu ze względu na to, że \(\displaystyle{ 14}\) nie dzieli się przez \(\displaystyle{ 4,6,10,12}\). Zostają nam: \(\displaystyle{ 2,3}\) zatem otrzymujemy:
\(\displaystyle{ n=2^{\alpha} \cdot 3^{\beta}}\), stąd \(\displaystyle{ \phi(n)=2^{\alpha-1} \cdot (2-1) \cdot 3^{\beta - 1} \cdot (3-1) = 2^{\alpha} \cdot 3^{\beta - 1}}\)
Zatem mamy do rozwiązania równanie \(\displaystyle{ 2^{\alpha} \cdot 3^{\beta - 1} = 14}\) gdzie \(\displaystyle{ \alpha=1}\), bo w innym przypadku liczba \(\displaystyle{ 14}\) nie byłaby podzielna przez \(\displaystyle{ 2^{\alpha}}\), więc równanie nie miałoby rozwiązania. Zatem mamy do rozwiązania:
\(\displaystyle{ 2 \cdot 3^{\beta - 1} = 14}\)
Dzielimy obustronnie przez \(\displaystyle{ 2}\) i otrzymujemy:
\(\displaystyle{ 3^{\beta - 1} = 7}\)
Oczywiście nie istnieje taka liczba całkowita \(\displaystyle{ \beta}\), żeby powyższe równanie było spełnione. Zatem otrzymaliśmy sprzeczność stąd wniosek, że nie istnieje takie \(\displaystyle{ n}\), dla którego \(\displaystyle{ \phi(n)=14}\)
-
MasterJoda
- Użytkownik
- Posty: 1
- Rejestracja: 4 lut 2013, o 18:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
Funkcja Eulera - dowod
Taka drobnostka, ale chyba chodziło o liczby dzielące \(\displaystyle{ n}\).pawellogrd pisze:
Stąd nie ma liczb \(\displaystyle{ p>15}\) dzielących się przez \(\displaystyle{ n}\), inaczej zachodziłoby \(\displaystyle{ \phi(n)>p-1>14}\), co byłoby sprzecznością.