Reszta z dzielenia przez kwadrat

Podzielność. Reszty z dzielenia. Kongruencje. Systemy pozycyjne. Równania diofantyczne. Liczby pierwsze i względnie pierwsze. NWW i NWD.
Thingoln
Użytkownik
Użytkownik
Posty: 133
Rejestracja: 27 lip 2019, o 22:19
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 52 razy
Pomógł: 15 razy

Reszta z dzielenia przez kwadrat

Post autor: Thingoln »

Witajcie!

Weźmy przykład:
\(\displaystyle{ a^{2p-2} - 1 = (a^{p-1}+1)(a^{p-1}-1)}\), gdzie \(\displaystyle{ a \in \mathbb{N^{+}}, \ p \in \mathbb{P}, \ a \perp p}\)

Z twierdzenia Eulera wiemy, że w takim wypadku \(\displaystyle{ p | a^{p-1} - 1}\), więc \(\displaystyle{ (a^{p-1}+1)(a^{p-1}-1) \equiv 0 \pmod{p}}\)

Zastanawia mnie jednak, co gdybyśmy chcieli znaleźć resztę z dzielenia przez \(\displaystyle{ p^2}\). Czy takie coś jest poprawne?
\(\displaystyle{ (a^{p-1}+1)(a^{p-1}-1) \equiv R \pmod{p^2} \iff (a^{p-1}+1) \equiv R \pmod{p}}\)

Nie wiem jednak, czy można coś takiego zrobić. Jeśli tak, to czy można również zastosować to w takim przypadku?
\(\displaystyle{ (a^{p-1}+1)(a^{p-1}-1) + 1 \equiv R \pmod{p^2} \iff a^{p-1}+1 + 1 \equiv a^{p-1} + 2 \equiv R \pmod{p}}\)

Liczba 1 jest w końcu niepodzielna przez żadną liczbę pierwszą, tym bardziej więc przez jej kwadrat.
Do tej pory miałem do czynienia z raczej łatwymi zadaniami z podzielności, ale warto się rozwijać. Prosiłbym więc o wytłumaczenie i odpowiedź, czy to, co napisałem, ma chociaż trochę sensu; byłbym również wdzięczny za odesłanie do ewentualnych źródeł informacji, twierdzeń i zależności, które mogą okazać się w tym przypadku przydatne lub na które warto zwrócić uwagę.
Z góry dziękuję. :)
Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15685
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 195 razy
Pomógł: 5219 razy

Re: Reszta z dzielenia przez kwadrat

Post autor: Premislav »

Thingoln pisze: 28 lis 2019, o 21:45

Zastanawia mnie jednak, co gdybyśmy chcieli znaleźć resztę z dzielenia przez \(\displaystyle{ p^2}\). Czy takie coś jest poprawne?
\(\displaystyle{ (a^{p-1}+1)(a^{p-1}-1) \equiv R \pmod{p^2} \iff (a^{p-1}+1) \equiv R \pmod{p}}\)

Nie, nie jest poprawne. Kontrprzykład: niech \(\displaystyle{ a=3, \ p=5, \ R=2}\). Mamy
\(\displaystyle{ 3^{4}+1\equiv 2\pmod{5}}\), ale nieprawdą jest, że \(\displaystyle{ 3^{8}-1\equiv 2\pmod{25}}\), wszak
\(\displaystyle{ 3^{8}-1=81^{2}-1\equiv 6^{2}-1\pmod{25}}\) i \(\displaystyle{ 6^{2}-1=35\equiv 10\pmod{25}}\)
Nie chcę być zbyt surowy, ale jeśli masz jakąś hipotezę, to czemu nie sprawdzisz jej na pierwszych lepszych liczbach?
Choć możliwe też, że zaistniały tu jakieś literówki i stąd wzięło się dość chybione sformułowanie.

Twierdzenie Eulera nie załatwi tak łatwo sprawy w przypadku podzielności przez \(\displaystyle{ p^{2}}\), mamy bowiem
\(\displaystyle{ \varphi\left(p^{2}\right)=(p-1)p}\) (ogólniej: nietrudno policzyć \(\displaystyle{ \varphi\left(p^{k}\right)=(p-1)p^{k-1}, \ p\in \PP, \ k=1,2\ldots}\)), a to jest trochę odległe od \(\displaystyle{ 2p-2}\).
Właściwie niewiele więcej jestem w stanie powiedzieć niż to, że dla \(\displaystyle{ (a,p)=1, \ p\in \PP}\) reszta z dzielenia \(\displaystyle{ a^{2p-2}-1}\) przez \(\displaystyle{ p^{2}}\) będzie podzielna przez \(\displaystyle{ p}\), co jest raczej oczywiste, wszak jak wcześniej wskazałeś \(\displaystyle{ a^{p-1}-1\equiv 0\pmod{p}}\).


Co do źródeł wiedzy na temat teorii liczb, Wstęp do teorii liczb Sierpińskiego i monografia Teoria liczb tego samego autora może się nadać, a jak jesteś bardziej nastawiony na rozwiązywanie zadań, to tematy z działu High School Olympiads z AoPS (warto zerknąć też na pliki, które można sobie pobrać z tegoż forum). Wydaje mi się też, że przerabiałeś którąś z książeczek pana Neugebauera z serii Matematyka olimpijska (albo pomyliłem Cię z innym użytkownikiem), to ta poświęcona algebrze i teorii liczb będzie bardzo mocnym źródłem. Nie przychodzi mi jednakże do głowy żadne źródło odnoszące się bezpośrednio do tego zadania. :(
Thingoln
Użytkownik
Użytkownik
Posty: 133
Rejestracja: 27 lip 2019, o 22:19
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 52 razy
Pomógł: 15 razy

Re: Reszta z dzielenia przez kwadrat

Post autor: Thingoln »

Premislav pisze: 29 lis 2019, o 02:39 Co do źródeł wiedzy na temat teorii liczb, Wstęp do teorii liczb Sierpińskiego i monografia Teoria liczb tego samego autora może się nadać, a jak jesteś bardziej nastawiony na rozwiązywanie zadań, to tematy z działu High School Olympiads z AoPS (warto zerknąć też na pliki, które można sobie pobrać z tegoż forum). Wydaje mi się też, że przerabiałeś którąś z książeczek pana Neugebauera z serii Matematyka olimpijska (albo pomyliłem Cię z innym użytkownikiem), to ta poświęcona algebrze i teorii liczb będzie bardzo mocnym źródłem. Nie przychodzi mi jednakże do głowy żadne źródło odnoszące się bezpośrednio do tego zadania. :(
Dziękuję bardzo! Nigdy nie miałem w ręku książki pana Sierpińskiego i nie wiem, czy warto zainteresować się którąś z jego książek. Mam już Algebrę i teorię liczb pana Neugebauera, ale brakuje mi w niej chociażby rozwiązań do większości ćwiczeń; wydaje mi się również, że do zastosowania szkolnego (konkursy, ciekawe sposoby rozwiązania zadań na maturze) jest w niej zdecydowanie za dużo teorii, która przydałaby mi się być może dopiero na studiach (np. grupy). Czy warto w takiej sytuacji zdecydować się na sięgnięcie po chociażby wspomniany Wstęp do teorii liczb?
Forum AoPS sprawdziłem i jestem pod wrażeniem; myślę, że będę często zaglądał. :)
Premislav pisze: 29 lis 2019, o 02:39 Nie chcę być zbyt surowy, ale jeśli masz jakąś hipotezę, to czemu nie sprawdzisz jej na pierwszych lepszych liczbach?
Choć możliwe też, że zaistniały tu jakieś literówki i stąd wzięło się dość chybione sformułowanie.
Literówki nie było, ale przyznaję, że sam też o tym pomyślałem jakiś czas po napisaniu tego posta. :?
ODPOWIEDZ