Pewien niezrozumiały przykład z działu liczby naturalne

[Arystoteles1989]

Witam

Natrafiłem w mojej książce do matematyki (książka do średniej szkoły) na pewien przykład którego nie potrafię zrozumieć, jeżeli jest ktoś kto potrafi odpowiedzieć na pytanie które zadam po podaniu treści owego przykładu, będę mu wdzięczny za pomoc.

„Przykład:

Która z podanych liczb jest liczbą pierwszą: 209, 211? (Wystarczy sprawdzić, czy dzielą się one przez 2, 3, 5, 7, 11, 13 gdyż następna liczba pierwsza- 17- podniesiona do kwadratu jest większa od największej liczby w zadaniu).

209 nie jest liczbą pierwszą gdyż 209=11x19. Liczba 211 musi być liczbą pierwszą, gdyż nie dzieli się przez żadną z liczb: 2, 3, 5, 7, 13.”

Czego nie rozumiem?

Dlaczego wyeliminowano liczbą 17? „ponieważ podniesiona do kwadratu jest większa od największej liczby w zadaniu”

Tylko co z tego? Przecież np. 3 podniesione do kwadratu również jest większe niż 6 a mimo tego dzieli ono tę liczbę.

[miki999]

Może powiem tak a*b=b*a czyli podczas sprawdzania dzielników nie ma sensu wychodzić poza zakres pierwiastak z danej liczby.
np. 36 możemy dzielić na 2,3..(6) a zauważmy, że kolejne dzielniki wypływają z tych poprzednich, bo 36 podzielone na 2 = 18, 36/3=12, 36/4=9, 36/6=6. Czyli dzielniki znajdujące się za pierwiastkiem badanej liczby mozna powiedzieć, że wynikają z tych występujących do niego.
A ta 3 podniesiona do 2 jest większa od 6, ale wynika ona z tego, że liczba jest podzielna przez 2, co podniesione do kwadratu jest mniejsze od 6.

Można to odnieść do algorytmu szukania liczb pierwszych za pomocą sita eratostenesa.

Trochę namotałem

[Qń]

Stosowne twierdzenie (jeśli to nie nazbyt szumna nazwa) brzmi: żeby sprawdzić czy \(\displaystyle{ n}\) jest liczbą pierwszą, wystarczy sprawdzić czy dzieli się ona przez liczby pierwsze nie większe niż \(\displaystyle{ \sqrt{n}}\).

Dowód: oczywiście jeśli dzieli się przez którą z nich, to liczba \(\displaystyle{ n}\) nie jest pierwsza. Jeśli zaś nie dzieli się przez żadną liczbę pierwszą \(\displaystyle{ p \leq \sqrt{n}}\), to jeśli nie byłaby pierwsza, to rozkładałaby się na iloczyn \(\displaystyle{ n=ab}\), gdzie \(\displaystyle{ a,b > \sqrt{n}}\), co jest oczywistą sprzecznością.

Ergo: rozumowanie przez Ciebie przytoczone ma sens, a Twój kontrprzykład z trójką i szóstką go nie obala.

Q.

[Arystoteles1989]

Pozwolę sobie głośno pomyśleć... nie podoba mi się to twierdzenie. Zgodnie z nim chcąc sprawdzić czy liczba 6 jest liczbą pierwszą wyciągamy z niej pierwiastek i otrzymujemy wynik= 2,4. Myślimy sobie, no dobra w takim razie musimy sprawdzić czy dwójka podzieli naszą szóstkę i wszystko będzie jasne 6/2=3. Wniosek: liczba 6 jest liczbą złożoną., a więc wniosek oczywiście prawidłowy. Hmm... spodobało mi się to 'twierdzenie' skoro jest twierdzeniem nie może się mylić, więc nabiorę do niego zaufania. Dziękuję za pomoc, uwolniła ona moje myśli.

[Rogal]

To nawet można powiedzieć, nie jest twierdzenie, a po prostu taka zwyczajna 'obserwacja' czy 'przemyślenie' .
Dodam też, że takie rzeczy zauważa się, gdy w szkole podstawowej uczą rozkładu na czynniki pierwsze liczby. Wystarczy "nie ufać nikomu" i wszystko sprawdzać na własnej skórze, by być stuprocentowo pewnym, że jakieś tam 'twierdzenie' jest dobre : )

[DEXiu]

I taka mała rada: nie ucz się "twierdzeń" takich jak to na pamięć, tylko postaraj się je zrozumieć. Zawartą w tym twierdzeniu prawidłowość dość łatwo sobie zobrazować:

Weź dowolną liczbę (najlepiej NIE pierwszą). Wypisz wszystkie dzielniki tej liczby w rzędzie (w porządku rosnącym). Zauważ, że "idąc" jednocześnie z obu końców tego rzędu do środka natrafiamy na kolejne pary liczb, które przemnożone przez siebie dają liczbę wyjściową (dla przykładu rozpisując 12 dostaniemy rząd: 1, 2, 3, 4, 6, 12 i kolejno pary 1*12=2*6=3*4). Zauważmy również, że "w środku" tego rzędu będzie znajdować się albo pojedyncza liczba (bez pary) - będzie to pierwiastek kwadratowy z liczby wyjściowej (który - zgodnie z naszą powyższą zasadą - przemnożony sam przez siebie (swoją "parę") da nam wyjściową liczbę), albo będzie to "przestrzeń" pomiędzy dwoma liczbami z ostatniej pary. I teraz ostatnie - najważniejsze - spostrzeżenie: zauważmy, że wszystkie liczby na prawo od tej "przestrzeni" są większe od pierwiastka z liczby wyjściowej, a wszystkie na lewo - mniejsze (ponieważ dzielniki były uporządkowane rosnąco).

WNIOSEK:
Dla każdej liczby naturalnej jej dzielniki możemy połączyć w pary postaci \(\displaystyle{ (a,\frac{n}{a})}\) (gdzie \(\displaystyle{ a}\) jest mniejszym dzielnikiem, a \(\displaystyle{ n}\) wyjściową liczbą), w których pierwszy element będzie mniejszy (lub równy) od \(\displaystyle{ \sqrt{n}}\), a drugi większy (lub równy) od \(\displaystyle{ \sqrt{n}}\) oraz każdemu dzielnikowi \(\displaystyle{ a}\) mniejszemu od \(\displaystyle{ \sqrt{n}}\) odpowiada dokładnie jeden dzielnik większy od \(\displaystyle{ \sqrt{n}}\) (równy \(\displaystyle{ \frac{n}{a}}\)).
Innymi słowy: dzielników "po obu stronach" \(\displaystyle{ \sqrt{n}}\) jest tyle samo i łatwo znaleźć dla każdego "parę" - z powyższego wzoru)

A skoro dla każdego dzielnika większego od \(\displaystyle{ \sqrt{n}}\) istnieje jego odpowiednik mniejszy od \(\displaystyle{ \sqrt{n}}\), to wystarczy przeszukać tylko te mniejsze (nie może istnieć jakiś dzielnik większy od \(\displaystyle{ \sqrt{n}}\) bez swojej "pary")