20687 Str025 (2)

46 I. Kilku zngflfthlpń cienieni nruej toorii llcfti

Przykłady

1.    Rozłóżmy na czynniki liczbę 2^{l 1} - 1    2047. Jeśli />|2'¹ • 1, to z ostat

niego twierdzenia wynika, że musi być p » 1 (mod 22). Zatem sprawdzamy p ** 23, 67, 89,... (w rzeczywistości nic musimy sprawdzać liczb większych od ^2047 *45,...). Rozkład na czynniki otrzymujemy natychmiast: 2047 =* 23 • 89. W podobny sposób możemy szybko przekonać się, że 2¹³ ~ I - 8191 jest liczbą pierwszą. Liczbę pierwszą postaci 2" - 1 nazywamy liczbą pierwszą Mcrscnne’a.

2.    Rozłóżmy na czynniki liczbę 3*² - 1 = 531440. Zgodnie z powyższym twierdzeniem sprawdzamy czynniki znacznie mniejszych liczb 3¹ — 1, 3² — 1, 3³ - 1, 3⁴ - 1 oraz czynniki liczby 3⁶ - 1 = (3³ - 1)(3³ + 1), które nic wystąpiły jeszcze w rozkładzie 3³ — 1. To daje nam czynniki 2* • 5 • 7 • 13. Ponieważ 531440/(2* -5*7* 13) = 73 oraz 73 jest liczbą pierwszą, więc mamy cały rozkład na czynniki. Zauważmy, że zgodnie z oczekiwaniem każdy czynnik pierwszy, który nie wystąpił w rozkładzie ¥ - 1 dla właściwych dzielników d liczby 12 (w naszym przypadku liczba 73), przystaje do 1 modulo 12.

3.    Rozłóżmy na czynniki liczbę 2³⁵ — 1 = 34359738367. Po pierwsze rozważmy czynniki liczb 2⁴ - 1 dla d = 1, 5,7. To daje nam czynniki pierwsze 31 i 127. Teraz (2^3S — 1)/(31 • 127) = 8727391. Zgodnie z ostatnim twierdzeniem każdy następny czynnik pierwszy musi przystawać do 1 modulo 70. Zatem sprawdzamy 71, 211, 281, ..., szukając dzielników liczby 8727391. W pierwszej chwili możemy obawiać się, że będziemy musieli sprawdzać wszystkie takie liczby pierwsze mniejsze od >/8727391 = 2954,.... Jednakże natychmiast stwierdzimy, że 8727391 = 71 • 122921 i pozostaje sprawdzić tylko liczby mniejsze od >/l22921 = 350, .... Stwierdzimy, że liczba 122921 jest pierwsza. Zatem 2^3S — 1 = 31 *71 • 127 • 122921 jest szukanym rozkładem na czynniki pierwsze.

Uwaga. W jaki sposób można przeprowadzić obliczenia w przykładzie 3 za pomocą kalkulatora, który wyświetla np. 8 cyfr dziesiętnych? Po prostu rozbijamy liczby na części. Przykładowo, kiedy obliczamy 2³⁵, dochodzimy do końca zakresu naszego kalkulatora po obliczeniu 2²⁶ = 67108864. Jeśli chcemy pomnożyć tę liczbę przez 2⁹ = 512, to piszemy

2³⁵ = 512 • (67108 • 1000 + 864) = 34359296 • 1000 + 442368 =

= 34359738368.

3937

Potem, kiedy dzielimy 2³⁵ — 1 przez 31 • 127 = 3937, najpierw dzielimy 34359738 przez 3937 i bierzemy część całkowitą ilorazu:    - = 8727.

Następnie piszemy 34359738 = 3937 • 8727 + 1539. Wtedy

(3937 • 8727 + 1539) 1000 + 367 3937

34359738^67 ~~ 3937

* 8727000

1539367

3937

8727391

Ćwiczenia

1.    Przeprowadź dwa różne dowody tego, że jeśli liczba n jest nieparzysta, to h" + 1 = (b + 1 )(6"“¹ - ó"^_z +... + b¹ - b + 1). W jednym dowodzie skorzystaj z tożsamości dla wielomianów. W drugim zastosuj system pozycyjny o podstawie b.

2.    Udowodnij, że jeśli liczba 2" - 1 jest pierwsza, to liczba n jest pierwsza, i jeśli liczba 2" + 1 jest pierwsza, to n jest potęgą liczby 2. Liczby pierwszego rodzaju są nazywane liczbami pierwszymi Mersenne’a, jak już wspomnieliśmy wcześniej, a liczby drugiego rodzaju są nazywane liczbami pierwszymi Fermata. Kilka początkowych liczb pierwszych Mersenne’a to 3,7, 31,127; początkowymi liczbami pierwszymi Fermata są 3, 5, 17,257.

3.    Przypuśćmy, że liczba b jest względnie pierwsza z liczbą m, gdzie m > 2 oraz a i c są liczbami całkowitymi dodatnimi. Udowodnij, że jeśli tf = — 1 (mod ni), łf = ±\ (mod m) oraz d — NWD(a, c), to b¹ = — 1 (mod m) i liczba a/d jest nieparzysta.

4.    Udowodnij, że jeśli p\łf + 1, to albo (i) p\b* + 1 dla pewnego właściwego dzielnika d liczby n takiego, że n/d jest liczbą nieparzystą, albo (ii) p = 1 (mod In).

5.    Niech m = 2²⁴ + 1 = 16777217.

(a)    Znajdź liczbę pierwszą Fermata dzielącą liczbę m.

(b)    Udowodnij, że każdy inny dzielnik pierwszy liczby m przystaje do 1 modulo 48.

(c)    Znajdź rozkład liczby m na czynniki pierwsze.

6.    Rozłóż    na czynniki liczby    3¹⁵ - 1 i 3²⁴ - 1.

7.    Rozłóż    na czynniki liczbę    5¹² — 1.

8.    Rozłóż    na czynniki liczby    10^s — 1,10* — li 10⁸ —    1.

9.    Rozłóż    na czynniki liczby    2³³ — li 2^2ł — 1.

10.    Rozłóż    na czynniki liczby    2¹⁵ - 1, 2³⁰ - 1 i 2⁶⁰ -    1.

11.    (a) Udowodnij, że jeśli d = NWD (m, n) i a > 1 jest dowolną liczbą cał

kowitą, to NWD(fl^m - 1, fl" - I) = a⁴ - 1.

(b) Przypuśćmy, że chcemy pomnożyć przez siebie dwie ś>bitowe liczby całkowite a i b, przy czym k jest bardzo duże. Niech / będzie ustaloną liczbą całkowitą, znacznie mniejszą niż k. Wybierzmy liczby m,, 1 < i < r, takie że //2 < m, < / dla wszystkich i oraz NWD(m_h ntj) - 1 dla i j. Niech r = [4k/łJ + 1. Załóżmy, że duża liczba całkowita, taka jak a, jest zapamiętywana jako ciąg r liczb (a_it ...» a_r), gdzie a, jest resztą z dzielenia a przez 2"' - 1. Udowodnij, że liczby a, b i ab są