69398 Str008 (2)

1

Kilka zagadnień elementarnej teorii liczb

Większość tematów omawianych w tym rozdziale jest prawdopodobnie dobrze znana wielu czytelnikom. Celem tego rozdziału jest przypomnienie oznaczeń i faktów z elementarnej teorii liczb, których będziemy na bieżąco potrzebowali w naszej przyszłej pracy. Większość dowodów pominięto, ponieważ można je znaleźć w prawie każdym podstawowym podręczniku teorii liczb. Jeden temat, który będzie odgrywał kluczową rolę w dalszym ciągu - szacowanie liczby operacji na bitach potrzebnych do wykonania różnych zadań teorioliczbowych za pomocą komputera - nie znajduje się jeszcze w elementarnych podręcznikach teorii liczb. Zajmiemy się tym problemem bardziej szczegółowo, zwłaszcza w podrozdziale 1.1.

1.1. Oszacowanie czasu wykonywania działań arytmetycznych

Liczby w różnych systemach pozycyjnych. Nieujemną liczbę całkowitą n zapisujemy przy podstawie b w postaci (d*_ ₁d^>ft-₂-.d₁d^r0)_ft, gdzie d_k- _lt d_k-₂, du d₀ są cyframi, tzn. symbolami dla liczb całkowitych zawartych między 0 i b — 1; ten zapis oznacza, że n — d_k-_ktf~^l + d_k-₂b^k~^z +... + d_tb + d₀. Jeśli pierwsza cyfra d_k-₁ nie jest zerem, to liczbę n nazywamy liczbą k-cyfrową w systemie pozycyjnym o podstawie b. Każda liczba zawarta między ¹ i 6* jest liczbą Ar-cyfrową w systemie o podstawie b. Opuszczamy nawiasy i indeks w przypadku zwyczajnego systemu dziesiętnego (b = 10) oraz niekiedy także w innych przypadkach, jeśli wybór podstawy jasno wynika z kontekstu, zwłaszcza gdy używamy systemu dwójkowego (b = 2). Ponieważ czasem wygodnie jest używać podstaw innych niż 10, warto przyzwyczaić się do wykonywania działań arytmetycznych przy dowolnej podstawie i do przechodzenia od jednej podstawy do drugiej. Obejrzymy to teraz na kilku przykładach.

Uwagi:

(1) Ułamki też można rozwijać przy dowolnej podstawie, tzn. mogą one być przedstawiane w postaci (d_k-\d_k.₂'‘'dyd₀, d_yd_₂-)b-