Ukryta treść:
Rozwiązać z funkcją Eulera
-
mol_ksiazkowy
- Użytkownik
- Posty: 13371
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3425 razy
- Pomógł: 809 razy
Rozwiązać z funkcją Eulera
Rozwiázać równanie \(\displaystyle{ n \sigma(n) \equiv 2 \ (\bmod \ \phi(n)).}\)
Ostatnio zmieniony 8 lip 2023, o 22:11 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
Ares7531
Re: Rozwiązać z funkcją Eulera
rozwiązaniem jest:
\(\displaystyle{ n=p>3}\)
A wytłumaczenie tego jest proste załóżmy, że:
\(\displaystyle{ n=p^sk , (p,k)=1 , s>1}\)
\(\displaystyle{ \delta(n)=\delta(p^sk)=\delta(p^s) \cdot \delta(k)= \frac{p^{s+1}-1}{p-1} \cdot \delta(k) }\)
\(\displaystyle{ \varphi(n)=\varphi(p^sk)=\varphi(p^s) \cdot \varphi(k)=(p^s-p^{s-1}) \cdot \varphi (k)}\)
utwórzmy ułamek:
\(\displaystyle{ \frac{n \cdot \delta(n)}{\varphi(n)}= \frac{p^s \cdot k \cdot \frac{p^{s+1}-1}{p-1}\delta(k) }{(p^s-p^{s-1}) \cdot \varphi (k)} = \frac{p^s \cdot k(p^{s+1}-1) \cdot \delta(k)}{p^{s-1}(p-1)^2 \cdot \varphi(k)} }\)
i teraz widać, że jeżeli \(\displaystyle{ p>2}\) to ułamek ten skraca się przez liczbę większą od dwóch,
jeżeli: \(\displaystyle{ p=2 , s=2}\) to też łatwo wykazać, że jeżeli następna liczba pierwsza jest w pierwszej potędze to i tak ułamek skraca się przez przynajmniej dwa co daje już razem cztery...
dla: \(\displaystyle{ n=4}\) łatwo wykazać, że reszta wyniesie zero...
czyli wiemy, że wszystkie liczby pierwsze muszą być w potędze co najwyżej jeden
niech np.: \(\displaystyle{ n=p \cdot q}\)
nasz ułamek wyniesie:
\(\displaystyle{ \frac{pq (p+1)(q+1)}{(p-1)(q-1)} }\)
jak widać skróci się przez przynajmniej cztery albo reszta wyniesie zero...
powiem tylko o co chodzi z tym skracaniem i jak się ma to do reszt np.:
\(\displaystyle{ \frac{18}{10} =1 r 8}\)
po skróceniu:
\(\displaystyle{ \frac{9}{5} =1 r 4}\)
reszta tyle razy się zmniejszy ile razy skrócimy więc skoro nasze ułamki skracamy przez liczby większe od dwóch to i potem właściwą resztę musimy pomnożyć przez liczbę większą od dwóch co daje liczbę albo zero albo większą od dwóch...
natomiast dla:
\(\displaystyle{ n=p>3}\)
nasz ułamek wyjdzie:
\(\displaystyle{ \frac{p(p+1)}{p-1} = \frac{p^2-p+2p}{p-1} = \frac{2p}{p-1} = \frac{2(p-1)+2}{p-1} =2 \mod (p-1)}\)
cnd...
dla:
\(\displaystyle{ p=2,3}\)
reszty wyjdą zero...
\(\displaystyle{ n=p>3}\)
A wytłumaczenie tego jest proste załóżmy, że:
\(\displaystyle{ n=p^sk , (p,k)=1 , s>1}\)
\(\displaystyle{ \delta(n)=\delta(p^sk)=\delta(p^s) \cdot \delta(k)= \frac{p^{s+1}-1}{p-1} \cdot \delta(k) }\)
\(\displaystyle{ \varphi(n)=\varphi(p^sk)=\varphi(p^s) \cdot \varphi(k)=(p^s-p^{s-1}) \cdot \varphi (k)}\)
utwórzmy ułamek:
\(\displaystyle{ \frac{n \cdot \delta(n)}{\varphi(n)}= \frac{p^s \cdot k \cdot \frac{p^{s+1}-1}{p-1}\delta(k) }{(p^s-p^{s-1}) \cdot \varphi (k)} = \frac{p^s \cdot k(p^{s+1}-1) \cdot \delta(k)}{p^{s-1}(p-1)^2 \cdot \varphi(k)} }\)
i teraz widać, że jeżeli \(\displaystyle{ p>2}\) to ułamek ten skraca się przez liczbę większą od dwóch,
jeżeli: \(\displaystyle{ p=2 , s=2}\) to też łatwo wykazać, że jeżeli następna liczba pierwsza jest w pierwszej potędze to i tak ułamek skraca się przez przynajmniej dwa co daje już razem cztery...
dla: \(\displaystyle{ n=4}\) łatwo wykazać, że reszta wyniesie zero...
czyli wiemy, że wszystkie liczby pierwsze muszą być w potędze co najwyżej jeden
niech np.: \(\displaystyle{ n=p \cdot q}\)
nasz ułamek wyniesie:
\(\displaystyle{ \frac{pq (p+1)(q+1)}{(p-1)(q-1)} }\)
jak widać skróci się przez przynajmniej cztery albo reszta wyniesie zero...
powiem tylko o co chodzi z tym skracaniem i jak się ma to do reszt np.:
\(\displaystyle{ \frac{18}{10} =1 r 8}\)
po skróceniu:
\(\displaystyle{ \frac{9}{5} =1 r 4}\)
reszta tyle razy się zmniejszy ile razy skrócimy więc skoro nasze ułamki skracamy przez liczby większe od dwóch to i potem właściwą resztę musimy pomnożyć przez liczbę większą od dwóch co daje liczbę albo zero albo większą od dwóch...
natomiast dla:
\(\displaystyle{ n=p>3}\)
nasz ułamek wyjdzie:
\(\displaystyle{ \frac{p(p+1)}{p-1} = \frac{p^2-p+2p}{p-1} = \frac{2p}{p-1} = \frac{2(p-1)+2}{p-1} =2 \mod (p-1)}\)
cnd...
dla:
\(\displaystyle{ p=2,3}\)
reszty wyjdą zero...