Podzielność i przesunięcie
- mol_ksiazkowy
- Użytkownik
- Posty: 11378
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3153 razy
- Pomógł: 747 razy
Podzielność i przesunięcie
Niech \(\displaystyle{ p>3}\) będzie liczbą pierwsza, zaś \(\displaystyle{ m}\) liczbą całkowitą. Udowodnić, że istnieją liczby całkowita \(\displaystyle{ x, y}\) takie, że \(\displaystyle{ 2x^2+3y^2 -m}\) jest podzielne przez \(\displaystyle{ p}\)
- Slup
- Użytkownik
- Posty: 793
- Rejestracja: 27 maja 2016, o 20:49
- Płeć: Kobieta
- Lokalizacja: Warszawa
- Podziękował: 23 razy
- Pomógł: 156 razy
Re: Podzielność i przesunięcie
Zauważmy, że odwzorowanie \(\displaystyle{ x\mapsto x^2}\) określone dla ciała \(\displaystyle{ \mathbb{Z}_p}\) reszto modulo \(\displaystyle{ p}\) przyjmuje dokładnie \(\displaystyle{ \frac{p-1}{2}+1}\) wartości. Innymi słowy reszt kwadratowych modulo \(\displaystyle{ p}\) jest \(\displaystyle{ \frac{p-1}{2}+1}\).
Ustalmy \(\displaystyle{ m\in \mathbb{Z}}\) oraz \(\displaystyle{ p>3}\). Wówczas równanie
\(\displaystyle{ 2X+3Y=m}\)
ma na płaszczyźnie \(\displaystyle{ \mathbb{Z}_p\times \mathbb{Z}_p}\) dokładnie \(\displaystyle{ p}\) rozwiązań (zbiorem rozwiązań jest prosta afiniczna nad \(\displaystyle{ \mathbb{Z}_p}\)). Ponadto z faktu, że \(\displaystyle{ p>3}\) wynika, że jeśli \(\displaystyle{ (X_1,Y_1)}\) oraz \(\displaystyle{ (X_2,Y_2)}\) są dwoma różnymi rozwiązaniami tego równania, to zachodzi własność
\(\displaystyle{ X_1 \neq X_2,\,Y_1\neq Y_2}\)
Wystarczy wykazać, że istnieje rozwiązanie powyższego równania \(\displaystyle{ (X,Y)}\) takie, że zarówno \(\displaystyle{ X}\) jak i \(\displaystyle{ Y}\) są resztami kwadratowymi modulo \(\displaystyle{ p}\). Niech \(\displaystyle{ A}\) będzie zbiorem rozwiązań \(\displaystyle{ (X,Y)}\) tego równania takich, że \(\displaystyle{ X}\) jest resztą kwadratową. Analogicznie niech \(\displaystyle{ B}\) będzie zbiorem rozwiązań \(\displaystyle{ (X,Y)}\) tego równania takich, że \(\displaystyle{ Y}\) jest resztą kwadratową. Z własności podanej wyżej, faktu, że równanie ma dokładnie \(\displaystyle{ p}\) rozwiązań oraz uwagi na temat liczby reszt kwadratowych modulo \(\displaystyle{ p}\) otrzymujemy, że
\(\displaystyle{ |A| = |B| = \frac{p-1}{2}+1,\,|A\cup B|\leq p}\)
Stąd z zasady szufladkowej otrzymujemy, że \(\displaystyle{ A\cap B \neq \emptyset}\), co dokładnie oznacza tezę.
Ustalmy \(\displaystyle{ m\in \mathbb{Z}}\) oraz \(\displaystyle{ p>3}\). Wówczas równanie
\(\displaystyle{ 2X+3Y=m}\)
ma na płaszczyźnie \(\displaystyle{ \mathbb{Z}_p\times \mathbb{Z}_p}\) dokładnie \(\displaystyle{ p}\) rozwiązań (zbiorem rozwiązań jest prosta afiniczna nad \(\displaystyle{ \mathbb{Z}_p}\)). Ponadto z faktu, że \(\displaystyle{ p>3}\) wynika, że jeśli \(\displaystyle{ (X_1,Y_1)}\) oraz \(\displaystyle{ (X_2,Y_2)}\) są dwoma różnymi rozwiązaniami tego równania, to zachodzi własność
\(\displaystyle{ X_1 \neq X_2,\,Y_1\neq Y_2}\)
Wystarczy wykazać, że istnieje rozwiązanie powyższego równania \(\displaystyle{ (X,Y)}\) takie, że zarówno \(\displaystyle{ X}\) jak i \(\displaystyle{ Y}\) są resztami kwadratowymi modulo \(\displaystyle{ p}\). Niech \(\displaystyle{ A}\) będzie zbiorem rozwiązań \(\displaystyle{ (X,Y)}\) tego równania takich, że \(\displaystyle{ X}\) jest resztą kwadratową. Analogicznie niech \(\displaystyle{ B}\) będzie zbiorem rozwiązań \(\displaystyle{ (X,Y)}\) tego równania takich, że \(\displaystyle{ Y}\) jest resztą kwadratową. Z własności podanej wyżej, faktu, że równanie ma dokładnie \(\displaystyle{ p}\) rozwiązań oraz uwagi na temat liczby reszt kwadratowych modulo \(\displaystyle{ p}\) otrzymujemy, że
\(\displaystyle{ |A| = |B| = \frac{p-1}{2}+1,\,|A\cup B|\leq p}\)
Stąd z zasady szufladkowej otrzymujemy, że \(\displaystyle{ A\cap B \neq \emptyset}\), co dokładnie oznacza tezę.