Prosta reszta
-
mol_ksiazkowy
- Użytkownik
- Posty: 11474
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3157 razy
- Pomógł: 748 razy
Prosta reszta
Niech \(\displaystyle{ k}\) będzie liczbą całkowitą nieujemną, a \(\displaystyle{ p=4k-1}\) liczbą pierwszą. Wyznaczyć resztę z dzielenia przez \(\displaystyle{ p}\) liczby \(\displaystyle{ (1^2+1)...((2k-1)^2+1)}\)
-
Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Prosta reszta
Nie jest jasne, czy ten iloczyn, którego resztę mamy wyznaczyć, jest równy
\(\displaystyle{ \prod_{i=1}^{2k-1}\left(i^{2}+1\right)}\), czy \(\displaystyle{ \prod_{i=1}^{k}\left((2i-1)^{2}+1\right)}\). Proszę sprecyzować.
Dodano po 8 minutach 33 sekundach:
W każdym razie może się przydać taka obserwacja (to się chyba nazywa tożsamość Brahmagupty)
\(\displaystyle{ \left(a^{2}+b^{2}\right)\left(c^{2}+d^{2}\right)=(ac+bd)^{2}+(ad-bc)^{2}}\)
\(\displaystyle{ \prod_{i=1}^{2k-1}\left(i^{2}+1\right)}\), czy \(\displaystyle{ \prod_{i=1}^{k}\left((2i-1)^{2}+1\right)}\). Proszę sprecyzować.
Dodano po 8 minutach 33 sekundach:
W każdym razie może się przydać taka obserwacja (to się chyba nazywa tożsamość Brahmagupty)
\(\displaystyle{ \left(a^{2}+b^{2}\right)\left(c^{2}+d^{2}\right)=(ac+bd)^{2}+(ad-bc)^{2}}\)
-
mol_ksiazkowy
- Użytkownik
- Posty: 11474
- Rejestracja: 9 maja 2006, o 12:35
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Podziękował: 3157 razy
- Pomógł: 748 razy
-
Premislav
- Użytkownik
- Posty: 15688
- Rejestracja: 17 sie 2012, o 13:12
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 196 razy
- Pomógł: 5221 razy
Re: Prosta reszta
Jednak wzór Brahmagupty jest tu zbędny. Reszt kwadratowych modulo \(\displaystyle{ p}\) różnych od zera mamy dokładnie
\(\displaystyle{ \frac{p-1}{2}}\), czyli w tym przypadku \(\displaystyle{ 2k-1}\). W tym iloczynie są obecne wszystkie, bo gdyby dla pewnych \(\displaystyle{ i,j\in\left\{1,\ldots 2k-1\right\}, \ i\ge j}\) było
\(\displaystyle{ i^{2}+1\equiv j^{2}+1\pmod{p}}\), to \(\displaystyle{ p|(i-j)(i+j)}\), ale \(\displaystyle{ 0<i+j\le 2k-1+2k-1<4k-1=p}\), stąd \(\displaystyle{ p|(i-j)}\), czyli \(\displaystyle{ i=j}\)
Pozostaje skonstatować, że z twierdzenia Wilsona \(\displaystyle{ (p-1)!\equiv -1\pmod{p}}\)
Dodano po 7 minutach 36 sekundach:
Chociaż trzeba jeszcze sie wytłumaczyć, czemu żaden z czynników nie dzieli się przez \(\displaystyle{ p}\), bo jeszcze mogłaby być reszta zero zamiast \(\displaystyle{ -1}\) (tudzież \(\displaystyle{ p-1}\)). Nie chce mi się tego robić, co kończy dowód.
Dodano po 35 minutach 34 sekundach:
Dobra, myślałem, że z tym ostatnim trzeba się trochę rachunkowo paprać, ale mam one-linera z MTF kończącego tę kwestię, tak że wrzucę.
Nie wprost, niech dla liczby pierwszej \(\displaystyle{ p=4k-1}\) i liczby \(\displaystyle{ i\in\left\{1,\ldots 4k-2\right\}}\) będzie \(\displaystyle{ i^{2}\equiv -1\pmod{p}}\), wtedy z jednej strony mamy \(\displaystyle{ i^{4k-2}\equiv -1\pmod{p}}\), z drugiej z małego twierdzenia Fermata \(\displaystyle{ i^{4k-2}\equiv 1\pmod{p}}\), bo \(\displaystyle{ p-1=4k-2}\), sprzeczność.
\(\displaystyle{ \frac{p-1}{2}}\), czyli w tym przypadku \(\displaystyle{ 2k-1}\). W tym iloczynie są obecne wszystkie, bo gdyby dla pewnych \(\displaystyle{ i,j\in\left\{1,\ldots 2k-1\right\}, \ i\ge j}\) było
\(\displaystyle{ i^{2}+1\equiv j^{2}+1\pmod{p}}\), to \(\displaystyle{ p|(i-j)(i+j)}\), ale \(\displaystyle{ 0<i+j\le 2k-1+2k-1<4k-1=p}\), stąd \(\displaystyle{ p|(i-j)}\), czyli \(\displaystyle{ i=j}\)
Pozostaje skonstatować, że z twierdzenia Wilsona \(\displaystyle{ (p-1)!\equiv -1\pmod{p}}\)
Dodano po 7 minutach 36 sekundach:
Chociaż trzeba jeszcze sie wytłumaczyć, czemu żaden z czynników nie dzieli się przez \(\displaystyle{ p}\), bo jeszcze mogłaby być reszta zero zamiast \(\displaystyle{ -1}\) (tudzież \(\displaystyle{ p-1}\)). Nie chce mi się tego robić, co kończy dowód.
Dodano po 35 minutach 34 sekundach:
Dobra, myślałem, że z tym ostatnim trzeba się trochę rachunkowo paprać, ale mam one-linera z MTF kończącego tę kwestię, tak że wrzucę.
Nie wprost, niech dla liczby pierwszej \(\displaystyle{ p=4k-1}\) i liczby \(\displaystyle{ i\in\left\{1,\ldots 4k-2\right\}}\) będzie \(\displaystyle{ i^{2}\equiv -1\pmod{p}}\), wtedy z jednej strony mamy \(\displaystyle{ i^{4k-2}\equiv -1\pmod{p}}\), z drugiej z małego twierdzenia Fermata \(\displaystyle{ i^{4k-2}\equiv 1\pmod{p}}\), bo \(\displaystyle{ p-1=4k-2}\), sprzeczność.