dowód podzielności z liczbą pierwszą

Oddzielone od teorii liczb, proste problemy dotyczące zasad dzielenia itp.
VanHezz
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 22 wrz 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Międzyrzecz
Podziękował: 34 razy

dowód podzielności z liczbą pierwszą

Post autor: VanHezz »

Witam,
natrafiłem dzisiaj na z pewnością proste zadanko, ale moje rozwiązanie wydaję się być trochę do góry nogami. Chciałbym was spytać o waszą opinię.

Wykaż, że jeśli \(\displaystyle{ p}\) jest liczbą pierwszą i \(\displaystyle{ p \ge 5}\), to liczba \(\displaystyle{ p^{2} -17}\) jest podzielna przez \(\displaystyle{ 8}\).


Założenie:
\(\displaystyle{ p}\) - liczba pierwsza
\(\displaystyle{ p \ge 5 }\)

Teza:
\(\displaystyle{ p^{2} -17 = 8k}\), gdzie \(\displaystyle{ k \in Z}\)

Dowód:

\(\displaystyle{ p^{2} -17 = 8k}\)

\(\displaystyle{ p^{2} -8-9=8k /:8}\)

\(\displaystyle{ \frac{ p^{2} }{8} - \frac{9}{8} -1 = k}\)

\(\displaystyle{ k= \frac{(p-3)(p+3)}{8} -1}\)

Suma/różnica dwóch liczb nieparzystych jest liczbą parzystą, więc skoro \(\displaystyle{ p}\) jest liczbą pierwszą to \(\displaystyle{ (p-3)}\) i \(\displaystyle{ (p+3)}\) są liczbami parzystymi. Zatem:
\(\displaystyle{
k= \frac{ \frac{p+3}{2} \cdot \frac{p-3}{2} }{2} -1}\)
, gdzie czynniki w liczniku ułamka są całkowite, bo \(\displaystyle{ p \ge 5}\).

Ponadto wiemy, że iloczyn dwóch liczb parzystych jest parzysty, więc podzielny przez 2:

\(\displaystyle{ k= \frac{1}{4} \cdot \frac{(p+3)(p-3)}{2} -1}\)

Iloczyn w liczniku jest więc podzielny przez \(\displaystyle{ 4}\) (jako że każdy czynnik z osobna jest podzielny przez \(\displaystyle{ 2}\)), jak i przez \(\displaystyle{ 2}\) (bo iloczyn dwóch liczb parzystych jest podzielny przez \(\displaystyle{ 2}\)). Zatem iloczyn w liczniku jest podzielny przez \(\displaystyle{ 8}\).
Różnica dwóch liczb całkowitych jest liczbą całkowitą, dlatego \(\displaystyle{ k \in Z}\)

Skoro \(\displaystyle{ k \in Z}\), to \(\displaystyle{ p^{2} -17}\) dzieli się bez reszty przez \(\displaystyle{ 8}\). c.n.u.


Można pewnie rozwiązać to zadanie w dwóch linijkach i niepotrzebnie pokomplikowałem.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: Bran »

Myślę, że najpilniejszą sprawą do omówienia w tym rozumowaniu jest fragment:
VanHezz pisze: 11 sie 2021, o 17:32 Iloczyn w liczniku jest więc podzielny przez \(\displaystyle{ 4}\) (jako że każdy czynnik z osobna jest podzielny przez \(\displaystyle{ 2}\)), jak i przez \(\displaystyle{ 2}\) (bo iloczyn dwóch liczb parzystych jest podzielny przez \(\displaystyle{ 2}\)). Zatem iloczyn w liczniku jest podzielny przez \(\displaystyle{ 8}\).
Zgodzę się, że jest podzielny przez \(\displaystyle{ 4}\), bo \(\displaystyle{ 2 \mid (p-3)}\) i \(\displaystyle{ 2 \mid (p+3).}\) Tylko, że potem pozbywasz się tych dwójek dzieląc przez \(\displaystyle{ 4}\). Nie mamy pewności, że to co zostanie nadal jest parzyste.

Zobacz na przykład:
\(\displaystyle{ 10 \cdot 10}\) dzieli się przez \(\displaystyle{ 4}\), bo każdy z czynników ma przynajmniej jedną dwójkę w rozkładzie. Jako dwie liczby parzyste daje liczbę podzielną przez \(\displaystyle{ 2.}\)
Tylko czy to znaczy, że \(\displaystyle{ 10 \cdot 10}\) jest podzielne przez \(\displaystyle{ 8}\)?

Innymi słowy: Podzielność przez \(\displaystyle{ 2}\) i przez \(\displaystyle{ 4}\) nie jest cechą podzielności przez \(\displaystyle{ 8}\).
VanHezz
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 22 wrz 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Międzyrzecz
Podziękował: 34 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: VanHezz »

No rzeczywiście. \(\displaystyle{ 2}\) i \(\displaystyle{ 4}\) nie są względnie pierwsze.
Wydaje mi się, że powinienem zatem udowodnić jeszcze, że iloczyn \(\displaystyle{ (p-3)(p+3)}\) nie jest podzielny przez \(\displaystyle{ 6}\).

Rozpatruję sobie taki iloczyn:
\(\displaystyle{
(p-3)(p-2)(p-1)p(p+1)(p+2)(p+3)}\)


\(\displaystyle{ (p-3)}\) i \(\displaystyle{ (p+3)}\) mogłyby być podzielne, jako liczby parzyste w tym ciągu, przez \(\displaystyle{ 2}\), \(\displaystyle{ 4}\) lub \(\displaystyle{ 6}\). Przez \(\displaystyle{ 6}\) jednak na pewno nie są podzielne, bo nie są podzielne przez \(\displaystyle{ 3}\). A nie są podzielne przez \(\displaystyle{ 3}\), ponieważ \(\displaystyle{ p \neq 3}\), bo \(\displaystyle{ p \ge 5}\). Dalsze liczby pierwsze też nie są podzielne przez \(\displaystyle{ 3}\), no bo są pierwsze.

Natomiast nie wiem, czy takie wykluczenie rozwiązuje sprawę. Musiałbym jeszcze chyba pokazać, że \(\displaystyle{ (p-3)}\) i \(\displaystyle{ (p+3)}\) nie są jednocześnie podzielne przez \(\displaystyle{ 4}\).
Ostatnio zmieniony 11 sie 2021, o 19:01 przez VanHezz, łącznie zmieniany 1 raz.
Awatar użytkownika
Janusz Tracz
Użytkownik
Użytkownik
Posty: 4060
Rejestracja: 13 sie 2016, o 15:01
Płeć: Mężczyzna
Lokalizacja: hrubielowo
Podziękował: 79 razy
Pomógł: 1391 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: Janusz Tracz »

W rozwiązaniu właściwe nie skorzystałeś z faktu, że \(\displaystyle{ p}\) jest liczbą pierwszą. Zadanie można zrobić zauważając, że teza jest równowaznea stwierdzeniu \(\displaystyle{ (\forall p\in\mathbb{P}_{ \ge 5}) p^2\equiv 1\mod 8}\). Ustalmy więc \(\displaystyle{ p\in\mathbb{P}_{ \ge 5}}\) ponieważ \(\displaystyle{ p}\) jest pierwsze to \(\displaystyle{ p=8k+r}\) dla pewnego \(\displaystyle{ k\in\NN}\) oraz \(\displaystyle{ r\in\left\{ 1,3,5,7\right\} }\). Wtedy jednak

\(\displaystyle{ p^2= (8k+r)^2 \equiv r^2 \equiv 1\mod 8}\)

niezależnie od tego jakie było \(\displaystyle{ k}\) oraz \(\displaystyle{ r}\).
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: Bran »

VanHezz pisze: 11 sie 2021, o 18:57 Natomiast nie wiem, czy takie wykluczenie rozwiązuje sprawę.
Mnie nie przekonuje. Możesz skorzystać z rozwiązania Janusza Tracza lub sam coś wymyślić. Polecam skupić się na resztach z dzielenia przez \(\displaystyle{ 8.}\)

Zauważ, że \(\displaystyle{ p^2 = 8k + 17 = 8m + 1}\), gdzie \(\displaystyle{ k,m \in \NN.}\)

Inspirując się Twoim rozwiązaniem zrobiłbym to tak:
Do wykazania mamy
\(\displaystyle{ p^2 - 1 = 8m}\)

\(\displaystyle{ p^2 - 1 = (p-1)(p+1)}\)

Teraz zauważ coś na temat \(\displaystyle{ (p-1)(p+1)}\) i masz rozwiązanie.
VanHezz
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 22 wrz 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Międzyrzecz
Podziękował: 34 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: VanHezz »

No \(\displaystyle{ (p-1)(p+1)}\) jest podzielne przez \(\displaystyle{ 8}\), bo są to kolejne dwie liczby parzyste, więc jedna musi być podzielna przez \(\displaystyle{ 2}\), a druga przez \(\displaystyle{ 4}\), więc ich iloczyn jest podzielny przez \(\displaystyle{ 8}\). Nie rozumiem tylko, dlaczego w moim rozwiązaniu taka implikacja nie zachodzi.


Mam chyba jeszcze jedno rozwiązanie tego zadania:

zakładam, że
\(\displaystyle{ p}\) - liczba pierwsza
\(\displaystyle{ p \ge 5}\)

\(\displaystyle{ p}\) jako liczba nieparzysta jest postaci:

\(\displaystyle{ p=2k+1}\), gdzie \(\displaystyle{ k \in Z}\) i \(\displaystyle{ k \ge 2}\)

\(\displaystyle{ p^{2} -17 = (2k+1)^{2} -17 = 4k ^{2} +4k-16= 4(k ^{2}+k-4)}\)

Teraz jeśli k jest parzyste to to zawartość nawiasu jest parzysta, a jeśli k jest nieparzyste, to zawartość nawiasu również jest parzysta, bo mamy wówczas sumę dwóch liczb nieparzystych pomniejszoną o liczbę parzystą, co razem daje liczę parzystą.
Zatem skoro zawartość nawiasu zawsze jest parzysta, to można zapisać:

\(\displaystyle{ p^{2}-17=4 \cdot 2n = 8n}\), gdzie \(\displaystyle{ n \in Z }\)
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: Bran »

VanHezz pisze: 11 sie 2021, o 19:54 No \(\displaystyle{ (p-1)(p+1)}\) jest podzielne przez \(\displaystyle{ 8}\), bo są to kolejne dwie liczby parzyste, więc jedna musi być podzielna przez \(\displaystyle{ 2}\), a druga przez \(\displaystyle{ 4}\), więc ich iloczyn jest podzielny przez \(\displaystyle{ 8}\). Nie rozumiem tylko, dlaczego w moim rozwiązaniu taka implikacja nie zachodzi.
W Twoim rozwiązaniu taka implikacja nie zachodzi, bo tam wykazałeś tylko, że te dwie liczby są podzielne przez dwa. Tutaj wykazałeś już więcej - obie są parzyste, ale jedna z nich jest podzielna przez \(\displaystyle{ 4}\) (a nie tylko przez \(\displaystyle{ 2}\)). No i to zasadnicza różnica.

VanHezz pisze: 11 sie 2021, o 19:54 Mam chyba jeszcze jedno rozwiązanie tego zadania:

(...)
Tutaj bardzo dobrze.
Warto zauważyć, że twierdzenie jest prawdziwe dla wszystkich liczb nieparzystych, nie mniejszych niż \(\displaystyle{ 5.}\)
Ostatnio zmieniony 11 sie 2021, o 23:26 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości: nie mniejszych.
VanHezz
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 22 wrz 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Międzyrzecz
Podziękował: 34 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: VanHezz »

Bran pisze: 11 sie 2021, o 21:48 Tutaj bardzo dobrze.
Warto zauważyć, że twierdzenie jest prawdziwe dla wszystkich liczb nieparzystych, niemniejszych niż \(\displaystyle{ 5.}\)
:mrgreen:
Bran pisze: 11 sie 2021, o 21:48
VanHezz pisze: 11 sie 2021, o 19:54 No \(\displaystyle{ (p-1)(p+1)}\) jest podzielne przez \(\displaystyle{ 8}\), bo są to kolejne dwie liczby parzyste, więc jedna musi być podzielna przez \(\displaystyle{ 2}\), a druga przez \(\displaystyle{ 4}\), więc ich iloczyn jest podzielny przez \(\displaystyle{ 8}\). Nie rozumiem tylko, dlaczego w moim rozwiązaniu taka implikacja nie zachodzi.
W Twoim rozwiązaniu taka implikacja nie zachodzi, bo tam wykazałeś tylko, że te dwie liczby są podzielne przez dwa. Tutaj wykazałeś już więcej - obie są parzyste, ale jedna z nich jest podzielna przez \(\displaystyle{ 4}\) (a nie tylko przez \(\displaystyle{ 2}\)). No i to zasadnicza różnica.
Tak, chyba to czuję i wiedziałem, że coś jest z tym nie tak.

\(\displaystyle{
k= \frac{ \frac{p+3}{2} \cdot \frac{p-3}{2} }{2} -1}\)


Czyli chodzi o to, że te krzaczki u góry, ok, są całkowite, ale nie wiadomo czy któryś z nich, jako wynik dzielenia, jest parzysty czy nieparzysty, tak?
No to ja sobie tym problemem "poradziłem" właśnie tak, że tę jedną czwartą przepisałem sobie na bok, wiedząc już, że licznik jest podzielny przez cztery, i znowu dostałem iloczyn dwóch liczba parzystych w liczniku, który jest podzielny przez \(\displaystyle{ 2}\)...

\(\displaystyle{ k = \frac{1}{4} \cdot \frac{(p+3)(p-3)}{2} -1}\)

Tylko właśnie czuję, że taki myk jest jakiś wątpliwy.
Bran
Użytkownik
Użytkownik
Posty: 421
Rejestracja: 19 lut 2019, o 19:30
Płeć: Mężczyzna
Lokalizacja: Polska
Podziękował: 163 razy
Pomógł: 16 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: Bran »

VanHezz pisze: 11 sie 2021, o 23:51 No to ja sobie tym problemem "poradziłem" właśnie tak, że tę jedną czwartą przepisałem sobie na bok, wiedząc już, że licznik jest podzielny przez cztery, i znowu dostałem iloczyn dwóch liczba parzystych w liczniku, który jest podzielny przez \(\displaystyle{ 2}\)...

\(\displaystyle{ k = \frac{1}{4} \cdot \frac{(p+3)(p-3)}{2} -1}\)

Tylko właśnie czuję, że taki myk jest jakiś wątpliwy.
Wyjąłeś z tego iloczynu dwie dwójki, a potem skorzystałeś z tego, że one nadal tam są. Może są jakieś inne, ale tego trzeba było jeszcze dowieść.

De facto zrobiłeś coś takiego: \(\displaystyle{ 20}\) jest podzielne przez \(\displaystyle{ 8}\), bo jest podzielne przez \(\displaystyle{ 4}\) i przez \(\displaystyle{ 2}\). Spróbuj odpowiedzieć na pytanie - dlaczego to nie działa i będziesz wiedział, dlaczego Twój myk nie działa.
VanHezz
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 22 wrz 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Międzyrzecz
Podziękował: 34 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: VanHezz »

Już rozumiem. Dzięki wielkie za pomoc :wink:

Dodano po 1 dniu 10 godzinach 15 minutach 14 sekundach:
Mam jeszcze jedno zadanie. Jestem ciekaw, czy moje rozwiązanie jest poprawne. Mam też problem, bo zawsze tak przesadnie rozwlekle piszę, a pewnie można to zapisać w trzech linijkach symbolami. Ma ktoś jakiś pomysł, jak to rozwiązanie uzgrabnić?

Wykaż, że jeśli \(\displaystyle{ p}\) jest liczbą pierwszą i \(\displaystyle{ p \ge 7}\), to liczba \(\displaystyle{ ( p^{2}-1 )( p^{2}-4 )}\) jest podzielna przez \(\displaystyle{ 120}\).

Założenia:
\(\displaystyle{ p}\) - liczba pierwsza
\(\displaystyle{ p \ge 7}\)

Teza:
\(\displaystyle{ 120|( p^{2}-1 )( p^{2}-4 )}\)

Dowód:

\(\displaystyle{ ( p^{2}-1 )( p^{2}-4 ) = (p-2)(p-1)(p+1)(p+2)}\)

Liczba jest podzielna przez \(\displaystyle{ 120}\), gdy jest podzielna przez \(\displaystyle{ 3}\), \(\displaystyle{ 5}\) i \(\displaystyle{ 8}\) (\(\displaystyle{ NWW(3,5,8)=1}\))

Wiemy, że iloczyn \(\displaystyle{ (p-1)(p+1)}\) jest podzielny przez \(\displaystyle{ 8}\). Czynniki są bowiem dwiema kolejnymi liczbami parzystymi (\(\displaystyle{ p}\)-liczba nieparzysta), więc jedna z nich jest podzielna przez \(\displaystyle{ 2}\), a druga musi być podzielna przez \(\displaystyle{ 4}\).


Ponieważ
\(\displaystyle{ (p-2)(p-1)p}\) i \(\displaystyle{ p(p+1)(p+2)}\) to iloczyny trzech kolejnych liczb naturalnych, to któraś z nich musi być podzielna przez \(\displaystyle{ 3}\) i nie jest to \(\displaystyle{ p}\), bo \(\displaystyle{ p \ge 7}\). Podzielny przez \(\displaystyle{ 3}\) musi być więc któryś czynnik iloczynu \(\displaystyle{ (p-2)(p-1)(p+1)(p+2)}\).

Podobnie ponieważ
\(\displaystyle{ (p-2)(p-1)p(p+1)(p+2)}\) to iloczyn pięciu kolejnych liczb naturalnych, to któraś z nich musi być podzielna przez \(\displaystyle{ 5}\) i nie jest to \(\displaystyle{ p}\), bo \(\displaystyle{ p \ge 7}\). Podzielny przez \(\displaystyle{ 5}\) musi być więc któryś czynnik iloczynu \(\displaystyle{ (p-2)(p-1)(p+1)(p+2)}\).

Ostatecznie
\(\displaystyle{ (p-2)(p-1)(p+1)(p+2)}\)= \(\displaystyle{ 2s \cdot 4k \cdot 3t \cdot 5u=120 \cdot kstu}\), gdzie \(\displaystyle{ k, s, t, u \in Z}\).

Zatem skoro \(\displaystyle{ (p-2)(p-1)(p+1)(p+2)=( p^{2}-1 )( p^{2}-4 ) }\), to \(\displaystyle{ 120|( p^{2}-1 )( p^{2}-4 ) }\). c.n.u.
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: Dasio11 »

VanHezz pisze: 13 sie 2021, o 18:18Ostatecznie
\(\displaystyle{ (p-2)(p-1)(p+1)(p+2)= 2s \cdot 4k \cdot 3t \cdot 5u=120 \cdot kstu}\), gdzie \(\displaystyle{ k, s, t, u \in Z}\).
Wyłączając to przejście, Twój dowód jest podręcznikowy.
VanHezz
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 22 wrz 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Międzyrzecz
Podziękował: 34 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: VanHezz »

Ah, tak coś czułem. A jak by to inaczej zapisać?
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: Dasio11 »

Usunąć przejście. ;>
VanHezz
Użytkownik
Użytkownik
Posty: 245
Rejestracja: 22 wrz 2012, o 11:20
Płeć: Mężczyzna
Lokalizacja: Międzyrzecz
Podziękował: 34 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: VanHezz »

No tak ale wypadałoby zrobić jakieś podsumowanie tych dzielników. Co z tym przejściem jest w zasadzie nie tak?
a4karo
Użytkownik
Użytkownik
Posty: 22175
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: dowód podzielności z liczbą pierwszą

Post autor: a4karo »

Bran pisze: 11 sie 2021, o 18:04 Myślę, że najpilniejszą sprawą do omówienia w tym rozumowaniu jest fragment:
VanHezz pisze: 11 sie 2021, o 17:32 Iloczyn w liczniku jest więc podzielny przez \(\displaystyle{ 4}\) (jako że każdy czynnik z osobna jest podzielny przez \(\displaystyle{ 2}\)), jak i przez \(\displaystyle{ 2}\) (bo iloczyn dwóch liczb parzystych jest podzielny przez \(\displaystyle{ 2}\)). Zatem iloczyn w liczniku jest podzielny przez \(\displaystyle{ 8}\).
Zgodzę się, że jest podzielny przez \(\displaystyle{ 4}\), bo \(\displaystyle{ 2 \mid (p-3)}\) i \(\displaystyle{ 2 \mid (p+3).}\) Tylko, że potem pozbywasz się tych dwójek dzieląc przez \(\displaystyle{ 4}\). Nie mamy pewności, że to co zostanie nadal jest parzyste.

Zobacz na przykład:
\(\displaystyle{ 10 \cdot 10}\) dzieli się przez \(\displaystyle{ 4}\), bo każdy z czynników ma przynajmniej jedną dwójkę w rozkładzie. Jako dwie liczby parzyste daje liczbę podzielną przez \(\displaystyle{ 2.}\)
Tylko czy to znaczy, że \(\displaystyle{ 10 \cdot 10}\) jest podzielne przez \(\displaystyle{ 8}\)?

Innymi słowy: Podzielność przez \(\displaystyle{ 2}\) i przez \(\displaystyle{ 4}\) nie jest cechą podzielności przez \(\displaystyle{ 8}\).
To wszystko prawda, ale wystarczy zauważyć, że spośród dwóch liczb parzystych odległych o `6` jedna z nich jest podzielna przez `4`. Zatem iloczyn jest podzielny przez `8` i po kłopocie.
ODPOWIEDZ