Wykład 8
Potęgowanie
8.1 Funkcja Eulera
Definicja 8.1. Dla każdej liczby naturalnej m > 1 oznaczmy przez Õ(m) liczbÄ™ liczb
naturalnych mniejszych od m i względnie pierwszych z m, czyli
Õ(m) = rank ZÄ„" = |ZÄ„"|.
m m
Poza tym przyjmijmy, że Õ(1) = 1. Tak okreÅ›lonÄ… funkcjÄ™ Õ : N N nazywamy funkcjÄ…
Eulera.
Przykład 8.1.
Õ(1) = 1, Õ(2) = 2, Õ(3) = 2, Õ(4) = 2, Õ(5) = 4,
Õ(6) = 2, Õ(7) = 6, Õ(8) = 4, Õ(9) = 6, Õ(10) = 4.
Twierdzenie 8.1. Niech p będzie liczbą pierwszą i k  liczbą naturalną. Wtedy

1
Õ(pk) = pk - pk-1 = pk 1 - .
p
W szczególnoÅ›ci, Õ(p) = p - 1.
Twierdzenie 8.2. Jeżeli m, n są względnie pierwszymi liczbami naturalnymi, to
Õ(mn) = Õ(m)Õ(n).
Uwaga 8.1. WÅ‚asność funkcji Õ, o której mówi ostatnie twierdzenie, nazywamy mul-
typlikatywnością. Ogólnie, funkcję f : N N nazywamy multyplikatywną, jeżeli dla
dowolnych liczb aĄ"b zachodzi równość f(ab) = f(a)f(b).
24
Wniosek 8.1. Dla n " N oznaczmy Dn = {p " P : p|n}. Wówczas


1
Õ(n) = n 1 - .
p
p"Dn
Przykład 8.2.

1 1 1
Õ(105) = Õ(3 · 5 · 7) = 105 · 1 - 1 - 1 - = 2 · 4 · 6 = 48.
3 5 7
8.2 Twierdzenia Eulera i Fermata
Twierdzenie 8.3 (Eulera). Jeżeli a, m są wzglednie pierwszymi liczbami naturalny-
mi, to
aÕ(m) a" 1 (mod m).
Twierdzenie 8.4 (małe twierdzenie Fermata). Niech p " P i a " N. Wtedy
(a) spełniona jest kongruencja ap a" a (mod p),
(b) jeżeli liczba a nie jest podzielna przez p, to spełniona jest kongruencja
ap-1 a" 1 (mod p).
Wniosek 8.2. Jeżeli aÄ„"m, to a-1 mod m = aÕ(m)-1 MOD m. W szczególnoÅ›ci, jeżeli
p " P, to a-1 mod p = ap-2 MOD m.
Wniosek 8.3. Jeżeli aÄ„"m i r = n MOD Õ(m), to an a" ar (mod m).
8.3 Szybkie potęgowanie modulo m
Algorytm potęgowania modulo m
Dane: Liczby naturalne b, m, n, gdzie b < m, oraz zapis binarny liczby n:
k-1

n = (nk-1nk-2 . . . n1n0)2 = ni2i, ni " {0, 1}.
i=0
Szukane: bn MOD m.
Zmienne pomocnicze: Liczba naturalna a.
Start
a := 1;
dla i = 0, 1, . . . , k - 1 wykonuj
jeżeli ni = 1, to a := a · b MOD m;
b := b2 MOD m;
zwróć a
Stop
25