rozwiązanie kongruencji
- wiosna
- Użytkownik
- Posty: 98
- Rejestracja: 2 maja 2008, o 14:01
- Płeć: Kobieta
- Lokalizacja: poznań
- Podziękował: 20 razy
- Pomógł: 1 raz
rozwiązanie kongruencji
Jak wykazać,że kongruencja \(\displaystyle{ x ^{8}\equiv16(mod p)}\) ma rozwiązanie całkowite \(\displaystyle{ x}\) dla każdego \(\displaystyle{ p}\) będącego liczbą pierwszą.
- smigol
- Użytkownik
- Posty: 3454
- Rejestracja: 20 paź 2007, o 23:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 89 razy
- Pomógł: 353 razy
rozwiązanie kongruencji
Czyli każda \(\displaystyle{ p}\) (l. pierwsza) jest dzielnikiem każdej liczby całkowitej \(\displaystyle{ x ^{8} -16}\)
tylko np. dla x=2 i p =7 tak nie jest.
Albo mam rację, albo walnąłem tak głupi błąd, że przez miesiąc nie wyjdę z domu (ze wstydu).
tylko np. dla x=2 i p =7 tak nie jest.
Albo mam rację, albo walnąłem tak głupi błąd, że przez miesiąc nie wyjdę z domu (ze wstydu).
- smigol
- Użytkownik
- Posty: 3454
- Rejestracja: 20 paź 2007, o 23:10
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 89 razy
- Pomógł: 353 razy
rozwiązanie kongruencji
ajjć... faktycznie . Czytanie ze zrozumieniem się kłania*Kasia pisze:smigol, ma rozwiązanie dla każdego p; a nie zachodzi dla dowolnego x i p.
- max
- Użytkownik
- Posty: 3306
- Rejestracja: 10 gru 2005, o 17:48
- Płeć: Mężczyzna
- Lokalizacja: Lebendigentanz
- Podziękował: 37 razy
- Pomógł: 778 razy
rozwiązanie kongruencji
A w jaki sposób chciałbyś tu skorzystać z tego prawa?
Moja propozycja:
Ustalamy \(\displaystyle{ p}\) - dowolną liczbę pierwszą.
Zauważmy, że jeśli \(\displaystyle{ p = 2,}\) to możemy położyć np \(\displaystyle{ x = 2.}\)
Przypuśćmy, że \(\displaystyle{ p>2.}\)
Mamy:
\(\displaystyle{ x^{8} - 16 = (x^{2} - 2)(x^{2} + 2)(x^{4} + 4).}\)
Chcemy, aby było \(\displaystyle{ (x^{2} - 2)(x^{2} + 2)(x^{4} + 4)\equiv 0\pmod{p},}\) czyli, żeby jeden z nawiasów przystawał do zera modulo \(\displaystyle{ p.}\)
Jeśli \(\displaystyle{ 2}\) lub \(\displaystyle{ -2}\) jest resztą kwadratową modulo \(\displaystyle{ p}\) to koniec dowodu.
Załóżmy zatem, że \(\displaystyle{ 2}\) i \(\displaystyle{ -2}\) są nieresztami kwadratowymi modulo \(\displaystyle{ p.}\)
Z oznacza to w szczególności, że \(\displaystyle{ (-2)^{\frac{p-1}{2}}\equiv 2^{\frac{p-1}{2}}\pmod{p},}\) czyli \(\displaystyle{ (-1)^{\frac{p-1}{2}}\equiv 1\pmod{p}}\) a stąd \(\displaystyle{ 2|\frac{p-1}{2},}\) czyli \(\displaystyle{ p\equiv 1\pmod{4}.}\)
Niech \(\displaystyle{ \zeta}\) będzie pierwiastkiem pierwotnym modulo \(\displaystyle{ p.}\)
Istnieją wtedy liczby całkowite \(\displaystyle{ k,l}\) takie, że
\(\displaystyle{ \zeta^{k} \equiv 2, \ \zeta^{l}\equiv -2\pmod{p}.}\)
Obie liczby \(\displaystyle{ k,l}\) są nieparzyste, bo inaczej byłoby np \(\displaystyle{ (\zeta^{\frac{k}{2}})^{2}\equiv 2}\) wbrew założeniu, że \(\displaystyle{ 2}\) jest nieresztą kwadratową modulo \(\displaystyle{ p.}\)
Mamy \(\displaystyle{ -4\equiv \zeta^{k+l}}\) więc jeśli \(\displaystyle{ k, l}\) dają różne reszty modulo \(\displaystyle{ 4,}\) to z ich nieparzystości \(\displaystyle{ 4| k + l}\) i z tej kongruencji dostajemy, że
\(\displaystyle{ (\zeta^{\frac{k+l}{4}})^{4}+ 4\equiv 0\pmod{p}}\)
czyli koniec dowodu.
Pozostaje przypadek, gdy \(\displaystyle{ k,l}\) dają takie same reszty modulo \(\displaystyle{ 4.}\)
Ponieważ \(\displaystyle{ -1\equiv \zeta^{k-l}\pmod{p},}\) to wynika stąd, że \(\displaystyle{ -1}\) jest resztą dwukwadratową modulo \(\displaystyle{ p.}\)
Zauważmy, że wynika stąd, że \(\displaystyle{ (-1)^{\frac{p-1}{4}}\equiv 1\pmod{p}.}\)
Rzeczywiście ponieważ dla pewnego \(\displaystyle{ x}\) jest \(\displaystyle{ x^{4}\equiv -1,}\) to z małego tw Fermata:
\(\displaystyle{ (-1)^{\frac{p-1}{4}}\equiv (x^{4})^{\frac{p-1}{4}} \equiv x^{p-1}\equiv 1\pmod{p}}\)
Stąd musi być \(\displaystyle{ 2|\frac{p-1}{4}}\) czyli \(\displaystyle{ p \equiv 1\pmod{8},}\) co można zapisać jako \(\displaystyle{ p = 8s + 1.}\)
Ale wtedy \(\displaystyle{ 2}\) jest resztą kwadratową modulo \(\displaystyle{ p}\) co wynika np z , gdyż wśród liczb \(\displaystyle{ 2, 4, \ldots 4s, 4s + 2,\ldots, p-1 = 8s}\) jest dokładnie \(\displaystyle{ 2s}\) liczb większych od \(\displaystyle{ \frac{p}{2} = 4s + \frac{1}{2}}\) - sprzeczność z założeniem, że \(\displaystyle{ 2}\) jest nieresztą kwadratową modulo \(\displaystyle{ p.}\)
Moja propozycja:
Ustalamy \(\displaystyle{ p}\) - dowolną liczbę pierwszą.
Zauważmy, że jeśli \(\displaystyle{ p = 2,}\) to możemy położyć np \(\displaystyle{ x = 2.}\)
Przypuśćmy, że \(\displaystyle{ p>2.}\)
Mamy:
\(\displaystyle{ x^{8} - 16 = (x^{2} - 2)(x^{2} + 2)(x^{4} + 4).}\)
Chcemy, aby było \(\displaystyle{ (x^{2} - 2)(x^{2} + 2)(x^{4} + 4)\equiv 0\pmod{p},}\) czyli, żeby jeden z nawiasów przystawał do zera modulo \(\displaystyle{ p.}\)
Jeśli \(\displaystyle{ 2}\) lub \(\displaystyle{ -2}\) jest resztą kwadratową modulo \(\displaystyle{ p}\) to koniec dowodu.
Załóżmy zatem, że \(\displaystyle{ 2}\) i \(\displaystyle{ -2}\) są nieresztami kwadratowymi modulo \(\displaystyle{ p.}\)
Z oznacza to w szczególności, że \(\displaystyle{ (-2)^{\frac{p-1}{2}}\equiv 2^{\frac{p-1}{2}}\pmod{p},}\) czyli \(\displaystyle{ (-1)^{\frac{p-1}{2}}\equiv 1\pmod{p}}\) a stąd \(\displaystyle{ 2|\frac{p-1}{2},}\) czyli \(\displaystyle{ p\equiv 1\pmod{4}.}\)
Niech \(\displaystyle{ \zeta}\) będzie pierwiastkiem pierwotnym modulo \(\displaystyle{ p.}\)
Istnieją wtedy liczby całkowite \(\displaystyle{ k,l}\) takie, że
\(\displaystyle{ \zeta^{k} \equiv 2, \ \zeta^{l}\equiv -2\pmod{p}.}\)
Obie liczby \(\displaystyle{ k,l}\) są nieparzyste, bo inaczej byłoby np \(\displaystyle{ (\zeta^{\frac{k}{2}})^{2}\equiv 2}\) wbrew założeniu, że \(\displaystyle{ 2}\) jest nieresztą kwadratową modulo \(\displaystyle{ p.}\)
Mamy \(\displaystyle{ -4\equiv \zeta^{k+l}}\) więc jeśli \(\displaystyle{ k, l}\) dają różne reszty modulo \(\displaystyle{ 4,}\) to z ich nieparzystości \(\displaystyle{ 4| k + l}\) i z tej kongruencji dostajemy, że
\(\displaystyle{ (\zeta^{\frac{k+l}{4}})^{4}+ 4\equiv 0\pmod{p}}\)
czyli koniec dowodu.
Pozostaje przypadek, gdy \(\displaystyle{ k,l}\) dają takie same reszty modulo \(\displaystyle{ 4.}\)
Ponieważ \(\displaystyle{ -1\equiv \zeta^{k-l}\pmod{p},}\) to wynika stąd, że \(\displaystyle{ -1}\) jest resztą dwukwadratową modulo \(\displaystyle{ p.}\)
Zauważmy, że wynika stąd, że \(\displaystyle{ (-1)^{\frac{p-1}{4}}\equiv 1\pmod{p}.}\)
Rzeczywiście ponieważ dla pewnego \(\displaystyle{ x}\) jest \(\displaystyle{ x^{4}\equiv -1,}\) to z małego tw Fermata:
\(\displaystyle{ (-1)^{\frac{p-1}{4}}\equiv (x^{4})^{\frac{p-1}{4}} \equiv x^{p-1}\equiv 1\pmod{p}}\)
Stąd musi być \(\displaystyle{ 2|\frac{p-1}{4}}\) czyli \(\displaystyle{ p \equiv 1\pmod{8},}\) co można zapisać jako \(\displaystyle{ p = 8s + 1.}\)
Ale wtedy \(\displaystyle{ 2}\) jest resztą kwadratową modulo \(\displaystyle{ p}\) co wynika np z , gdyż wśród liczb \(\displaystyle{ 2, 4, \ldots 4s, 4s + 2,\ldots, p-1 = 8s}\) jest dokładnie \(\displaystyle{ 2s}\) liczb większych od \(\displaystyle{ \frac{p}{2} = 4s + \frac{1}{2}}\) - sprzeczność z założeniem, że \(\displaystyle{ 2}\) jest nieresztą kwadratową modulo \(\displaystyle{ p.}\)