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

⊥
m

= |Z

⊥
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

ϕ

(p

k

) = p

k

− p

k−

1

= p

k

1 −

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 D

n

= {p ∈ P : p|n}. Wówczas

ϕ

(n) = n

Y

p∈D

n

1 −

1
p

!

.

Przykład 8.2.

ϕ

(105) = ϕ(3 · 5 · 7) = 105 ·



1 −

1
3

 

1 −

1
5

 

1 −

1
7



= 2 · 4 · 6 = 48.

8.2

Twierdzenia Eulera i Fermata

Twierdzenie 8.3 (Eulera). Jeżeli a, m są wzglednie pierwszymi liczbami naturalny-

mi, to

a

ϕ

(m)

≡ 1 (mod m).

Twierdzenie 8.4 (małe twierdzenie Fermata). Niech p ∈ P i a ∈ N. Wtedy

(a) spełniona jest kongruencja a

p

≡ a (mod p),

(b) jeżeli liczba a nie jest podzielna przez p, to spełniona jest kongruencja

a

p−

1

≡ 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 = a

p−

2

MOD m.

Wniosek 8.3. Jeżeli a⊥m i r = n MOD ϕ(m), to a

n

≡ a

r

(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:

n

= (n

k−

1

n

k−

2

. . . n

1

n

0

)

2

=

k−

1

X

i

=0

n

i

2

i

,

n

i

∈ {0, 1}.

Szukane: b

n

MOD m.

Zmienne pomocnicze: Liczba naturalna a.

Start

a

:= 1;

dla i = 0, 1, . . . , k − 1 wykonuj

jeżeli n

i

= 1, to a := a · b MOD m;

b

:= b

2

MOD m;

zwróć a

Stop

25