15403 Str015 (2)
26 J. Kilku zagadnień elementarnej teorii licrh
16. Niech n będzie bardzo dużą liczbą zapisaną w systemie dwójkowym. Znajdź prosty algorytm obliczający [y/n ] za pomocą O (log3 z/) operacji na bitach ( [ ] oznacza tu część całkowitą liczby rzeczywistej).
1.2. Podzielność i algorytm Euklidesa
Dzielniki i podzielność. Dla danych liczb całkowitych a i b mówimy, że liczba a dzieli liczbę b (lub że liczba b jest podzielna przez liczbę a) i piszemy a \b, jeżeli istnieje taka liczba całkowita d, że b = ad. W takim przypadku liczbę a nazywamy dzielnikiem liczby b. Każda liczba b > 1 ma co najmniej dwa dzielniki dodatnie: 1 i b. Właściwym dzielnikiem liczby b nazywamy dzielnik dodatni różny od samej liczby b, a dzielnikiem nietrywialnym liczby b - dzielnik dodatni różny od I i od b. Liczba pierwsza, z definicji, to liczba większa od 1, nie mająca innych dzielników dodatnich niż 1 i ona sama; liczba całkowita jest liczbą złożoną, jeśli ma co najmniej jeden nietrywialny dzielnik. Następujące własności relacji podzielności są łatwe do sprawdzenia bezpośrednio z definicji:
1. Jeśli a|ó i c jest dowolną liczbą całkowitą, to a\bc.
2. Jeśli a\b i 6|c, to a|c.
3. Jeśli a|ó i a|c, to a\b± c.
Jeśli p jest liczbą pierwszą i a jest nieujemną liczbą całkowitą, to używamy oznaczenia /7“||ó, gdy pa jest najwyższą potęgą p dzielącą b, tzn. gdy f |ó oraz p*+1Xb. W takim przypadku mówimy, że pa jest dzielnikiem dokładnym liczby b.
Zasadnicze twierdzenie arytmetyki^ mówi, że każda liczba naturalna n może być przedstawiona jednoznacznie (z dokładnością do kolejności czynników) jako iloczyn liczb pierwszych. Zazwyczaj zapisujemy ten rozkład na czynniki jako iloczyn odpowiednich potęg różnych liczb pierwszych, wymieniając liczby pierwsze w kolejności rosnącej. Na przykład 4200 = 23 • 3 • 52 • 7.
Dwie następujące własności relacji podzielności są wnioskami z twierdzenia o rozkładzie na czynniki pierwsze (a nawet są stwierdzeniami równoważnymi z tym twierdzeniem):
4. Jeśli liczba pierwsza p dzieli ab, to p\a lub p\b.
5. Jeśli m\a i n\a oraz m i n nie mają wspólnych dzielników większych od 1, to mn\a.
Inną konsekwencją jednoznaczności rozkładu jest to, że daje ona systematyczną metodę szukania wszystkich dzielników liczby n, gdy znany jest
f) W polskiej terminologii to twierdzenie na ogół jest nazywane twierdzeniem o rozkładzie na czynniki pierwsze i tak będzie ono dalej nazywane. Zasadniczym twierdzeniem arytmetyki często nazywa się twierdzenie mówiące, że jeżeli liczby a i b są względnie pierwsze oraz a\bc, to a\c (przyp. tłum.).
rozkład n na czynniki pierwsze. Mianowicie, każdy dzielnik n musi być iloczynem tych samych liczb pierwszych podniesionych do potęg nie przekraczają-cych potęg, które są dzielnikami dokładnymi liczby n. To znaczy, że jeśli jf\\n, to fP\\d dla pewnego p spełniającego nierówności 0 < p <c i. Aby na przykład znaleźć dzielniki liczby 4200, bierzemy liczbę 2 podniesioną do potęgi zerowej, pierwszej, drugiej lub trzeciej, mnożymy ją przez liczbę 3 podniesioną do potęgi zerowej lub pierwszej, mnożymy przez liczbę 5 podniesioną do potęgi zerowej, pierwszej lub drugiej i mnożymy przez liczbę 7 podniesioną do potęgi zerowej lub pierwszej. Liczba możliwych dzielników jest zatem iloczynem liczb możliwości dla każdej potęgi liczby pierwszej, czyli 2+1. A więc liczba n ~ P\l Pi3 ••• Pt*na («! + 1)(«2 + 1)*••(«, + 1) różnych dzielników. Na przykład liczba 4200 ma 48 dzielników.
Dla danych dwóch liczb całkowitych a i b, nie będących równocześnie zerami, ich największy wspólny dzielnik, oznaczany NWD(a, b) (lub czasami prościej {a, b)), jest to największa liczba całkowita d będąca dzielnikiem zarówno a, jak i b. Nietrudno pokazać, że równoważną definicją NWDia, b) jest: największym wspólnym dzielnikiem liczb a i b jest jedyna liczba dodatnia d, która dzieli a i b i jest podzielna przez każdy inny wspólny dzielnik liczb a i b.
Jeśli znamy rozkłady liczb a i b na czynniki pierwsze, to bardzo łatwo możemy znaleźć NWD(a, b). Po prostu bierzemy wszystkie liczby pierwsze występujące w obu rozkładach podniesione do potęgi o mniejszym wykładniku. Porównując na przykład rozkład 10780 = 22 • 5 • 72 • 11 z powyższym rozkładem liczby 4200, otrzymujemy NWD(4200, 10780) = 22 • 5 • 7 = 140.
Czasami używamy najmniejszej wspólnej wielokrotności liczb a i b, oznaczanej przez NWW(a, b). Jest to najmniejsza dodatnia liczba całkowita, którą dzielą a i b. Jeśli znamy rozkłady liczb a i b na czynniki pierwsze, to liczbę NWW{a, b) znajdujemy, biorąc wszystkie liczby pierwsze występujące w którymkolwiek rozkładzie podniesione do potęgi o większym wykładniku. Łatwo dowieść, że NWW(a, b) = | ab \/NWD(a, b).
Algorytm Euklidesa. Jeżeli mamy do czynienia z bardzo dużymi liczbami, to prawdopodobnie nie będziemy znali rozkładu tych liczb na czynniki pierwsze. W rzeczywistości ważną dziedziną badań w teorii liczb jest poszukiwanie szybkich metod rozkładu liczb na czynniki. Na szczęście istnieje dość szybka metoda znajdowania NWD(a, b) nawet wtedy, gdy nie mamy pojęcia
0 tym, jakie czynniki pierwsze mają liczby a i b. Jest to algorytm Euklidesa.
Algorytm Euklidesa działa w następujący sposób. Aby znaleźć NWD(a, b), gdzie a >b, najpierw dzielimy a przez b i zapisujemy iloraz qt
1 resztę r{: a~ + rv Następnie wykonujemy drugie dzielenie, w którym b gra rolę a i rx gra rolę b: b — q2r{ + r2. Następnie dzielimy rx przez r,: ri = #3r2 + r3- Kontynuujemy to postępowanie, za każdym razem dzieląc przedostatnią resztę przez ostatnią, otrzymując nowy iloraz i nową resztę. Gdy wreszcie otrzymamy resztę, która dzieli poprzednią, kończymy dzielenie: ostatnia niezerowa reszta jest największym wspólnym dzielnikiem liczb a i b.
Wyszukiwarka
Podobne podstrony:
Str026 (2) 48 I Kilka zagadnień elementarnej teorii licrh wyznaczone jednoznacznie prze?, odpowiadaj
69398 Str008 (2) 1Kilka zagadnień elementarnej teorii liczb Większość tematów omawianych w tym rozdz
zagadnienia egzaminacyjne z teorii literatury (16) u_^. i^AvuJ&>XibA— }. p Voc-^— ^ &n
DSC08568 Przenośniki łańcuchowe płytkowe (członowe) bardzo duża liczba produkowanych seryjnie elemen
a, i , gdzie ai, .... aisądowolnymi elementami zbioru A, zaś/f/, ..., me Z />/;/.- Niech H będzie
1.1. Podstawowe definicje i przykłady 7 Własność 1.1.9 (element odwracalne a dzielniki zera). Niech
459 § 5. Elementarne funkcje zmiennej zespolonej Niech będzie 0<0<tc. Ponieważ dla r = 1 szere
zwykle istotne zagadnienie, a mianowicie koncentrację mediów. Wydaje nam się, że duża liczba mediów
zagadnienia egzaminacyjne z teorii literatury (64) rozumienia: elementarne (psychologiczne) i wyższa
Salomonowicz (26) 98 i jego elementów, ale co do zagadnienia winy doktryna francuska nie znalazła po
więcej podobnych podstron