witam proszę o rozwiązanie następujących zadań:
zad1.
Wykaż, że liczba \(\displaystyle{ 561}\) jest liczbą Carmichaela, tzn. dla dowolnego a względnie
pierwszego z \(\displaystyle{ 561}\) zachodzi kongruencja
\(\displaystyle{ a ^{f(561)} \equiv 1 \pmod{561}.}\)
Wykaż, iż takze liczba \(\displaystyle{ 41041}\) jest liczbą Carmichaela
czy wystarczy te liczby rozłożyć na czynniki pierwsze oraz sprawdzić że działa wzór:
\(\displaystyle{ M(m)=(6m+1)(12m+1)(18m+1).}\)
zad 2.
Wykaż, że potęga liczby pierwszej nie jest liczbą Carmichaela.
zad 3.
Wykaż, że żadna liczba parzysta nie jest liczbą Carmichaela
zad 4.
Wykaż, że każda liczba Carmichaela ma przynajmniej trzy dzielniki pierwsze
liczby Carmichaela
liczby Carmichaela
Ostatnio zmieniony 27 mar 2016, o 20:55 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Powód: Poprawa wiadomości.
-
bakala12
- Użytkownik
- Posty: 3044
- Rejestracja: 25 mar 2010, o 15:34
- Płeć: Mężczyzna
- Lokalizacja: Gołąb
- Podziękował: 24 razy
- Pomógł: 513 razy
liczby Carmichaela
Należy się posługiwać definicją liczb Carmichaela a nie jakimś wzorem, który nie zawsze działa. Są to liczby złożone, które spełniają małe twierdzenie Fermata, przy dowolnej podstawie \(\displaystyle{ a}\) (oczywiście względnie pierwszej z tą liczbą). Formalnie:
\(\displaystyle{ n}\) jest liczbą Carmichaela \(\displaystyle{ \Leftrightarrow \forall_{a \in \ZZ} NWD\left(a,n\right)=1 \Rightarrow a^{n-1} \equiv 1 \pmod{n}}\)
Więc pierwsze zadanie można zrobić tak:
\(\displaystyle{ 561=3 \cdot 11 \cdot 17}\)
Trzeba pokazać, że jeśli
\(\displaystyle{ NWD\left(3, a\right)=1}\), to \(\displaystyle{ a^{561}\equiv 1 \pmod{3}}\) (co jest łatwe) i to samo dla \(\displaystyle{ 11}\) i \(\displaystyle{ 17}\). To dość prosto wynika z małego twierdzenia Fermata.
Dla \(\displaystyle{ 41041}\) to samo.
Drugie też jest proste. Nie wprost, załóżmy, że istnieje liczba pierwsza \(\displaystyle{ p}\) taka, że dla pewnego \(\displaystyle{ k}\) liczba \(\displaystyle{ p^{k}}\) jest liczbą Carmichaela. Wówczas byłoby:
\(\displaystyle{ a^{p^{k}-1}\equiv 1 \pmod{p^{k}}}\).
Czyli \(\displaystyle{ p^{k}|a^{p^{k}-1}-1}\). To jest jednak niemożliwe, bo łatwo można pokazać, że dla \(\displaystyle{ x \neq y}\) i dla liczby pierwszej \(\displaystyle{ p}\) takiej, że \(\displaystyle{ p|x-y}\) oraz \(\displaystyle{ p \nmid x}\) i \(\displaystyle{ NWD\left(p,n\right)=1}\) mamy \(\displaystyle{ p \nmid \frac{x^{n}-y^{n}}{x-y}}\). I to koniec.
\(\displaystyle{ n}\) jest liczbą Carmichaela \(\displaystyle{ \Leftrightarrow \forall_{a \in \ZZ} NWD\left(a,n\right)=1 \Rightarrow a^{n-1} \equiv 1 \pmod{n}}\)
Więc pierwsze zadanie można zrobić tak:
\(\displaystyle{ 561=3 \cdot 11 \cdot 17}\)
Trzeba pokazać, że jeśli
\(\displaystyle{ NWD\left(3, a\right)=1}\), to \(\displaystyle{ a^{561}\equiv 1 \pmod{3}}\) (co jest łatwe) i to samo dla \(\displaystyle{ 11}\) i \(\displaystyle{ 17}\). To dość prosto wynika z małego twierdzenia Fermata.
Dla \(\displaystyle{ 41041}\) to samo.
Drugie też jest proste. Nie wprost, załóżmy, że istnieje liczba pierwsza \(\displaystyle{ p}\) taka, że dla pewnego \(\displaystyle{ k}\) liczba \(\displaystyle{ p^{k}}\) jest liczbą Carmichaela. Wówczas byłoby:
\(\displaystyle{ a^{p^{k}-1}\equiv 1 \pmod{p^{k}}}\).
Czyli \(\displaystyle{ p^{k}|a^{p^{k}-1}-1}\). To jest jednak niemożliwe, bo łatwo można pokazać, że dla \(\displaystyle{ x \neq y}\) i dla liczby pierwszej \(\displaystyle{ p}\) takiej, że \(\displaystyle{ p|x-y}\) oraz \(\displaystyle{ p \nmid x}\) i \(\displaystyle{ NWD\left(p,n\right)=1}\) mamy \(\displaystyle{ p \nmid \frac{x^{n}-y^{n}}{x-y}}\). I to koniec.