Mam problem z zadaniem w którym muszę znaleźć liczbę rozwiązań kongruencji. Oto przykład:
\(\displaystyle{ x ^{18} \equiv 1(mod 27)}\)
Nie mam pojęcia jak robi się takie coś. Domyślam się, że trzeba użyć symbolu Legendre'a.
Z góry dzęki za pomoc.
-- 15 lut 2011, o 16:29 --
Jeśli nikt nie chce mi pomóc to może ktoś sprawdzi czy dobrze myśle, że z TW Eulera wynika że ta kongruencja ma nieskończenie wiele rozwiązań.
Liczba rozwiązań kongruencji
-
_Piotrek_
- Użytkownik
- Posty: 9
- Rejestracja: 15 lut 2011, o 19:34
- Płeć: Mężczyzna
- Lokalizacja: Gliwice
- Pomógł: 2 razy
Liczba rozwiązań kongruencji
Nie chce mi się tego dokładnie liczyć, ale wyjaśnię, jak należy to rozwiązać:
Niechaj x = 27K + y, gdzie K jest liczbą całkowitą, a y liczbą całkowitą od 0 do 26. Można to założyć bez straty ogólności zadania, bo dobierając odpowiednie K oraz y można uzyskać każdy całkowity x.
Wówczas
\(\displaystyle{ x ^{18}=(27K + y) ^{18} = (27K)^{18}+18*(27K)^{17}*y^{1} +...+18*(27K)^{1}*y^{17}+y^{18}.}\)
Wszystkie składniki ostatniej sumy oprócz ostatniego mają czynnik 27K, zatem dzielą się przez 27. Zatem o tym czy x^{18} jest podzielne przez 27 decyduje sam tylko czynnik y^{18}, to samo jest w przypadku badania, czy przystaje jedynce modulo 27.
Co to wnosi? Że wystarczy zbadać jakie reszty z dzielenia przez 27 dają liczby 0^{18}, 1^{18}, 2^{18} itd aż do 26^{18}. Jeżeli 1 przystaje D modulo 27, to 28 = 27 + 1 też przystaje D.
Udowodniliśmy, że
x^{n} = (x-Kp)^{n} mod(p) gdzie K jest całkowite.
Napewno liczba 1 spełnia tę kongruencję, więc automatycznie wszystkie liczby postaci 1+27K, gdzie K całkowite. Jakie kolejne - trzeba by policzyć.
Niechaj x = 27K + y, gdzie K jest liczbą całkowitą, a y liczbą całkowitą od 0 do 26. Można to założyć bez straty ogólności zadania, bo dobierając odpowiednie K oraz y można uzyskać każdy całkowity x.
Wówczas
\(\displaystyle{ x ^{18}=(27K + y) ^{18} = (27K)^{18}+18*(27K)^{17}*y^{1} +...+18*(27K)^{1}*y^{17}+y^{18}.}\)
Wszystkie składniki ostatniej sumy oprócz ostatniego mają czynnik 27K, zatem dzielą się przez 27. Zatem o tym czy x^{18} jest podzielne przez 27 decyduje sam tylko czynnik y^{18}, to samo jest w przypadku badania, czy przystaje jedynce modulo 27.
Co to wnosi? Że wystarczy zbadać jakie reszty z dzielenia przez 27 dają liczby 0^{18}, 1^{18}, 2^{18} itd aż do 26^{18}. Jeżeli 1 przystaje D modulo 27, to 28 = 27 + 1 też przystaje D.
Udowodniliśmy, że
x^{n} = (x-Kp)^{n} mod(p) gdzie K jest całkowite.
Napewno liczba 1 spełnia tę kongruencję, więc automatycznie wszystkie liczby postaci 1+27K, gdzie K całkowite. Jakie kolejne - trzeba by policzyć.