6161619780

„Małe” twierdzenie Fermata:

Niech p będzie liczbą pierwszą, wtedy: Va e    p :    a¹”’

= 1 (mod p)

Wnioski z „małego ” twierdzenia Fermata :

•    a^p =a (modp)

•    n = m (modp -1) =>a ⁿ=a ^m (modp)

Przykład zastosowania:

Znaleźć ostatnią cyfrę liczby 21000000 _w systemie zapisu liczb całkowitych o podstawie 7.

p = 7

p -1 = 6

1000000 = 4 (mod 6)

21000000 = (24 = 16) =2(mod 7)

a zatem ostatnią cyfrą reprezentacji liczby 21000000 _w systemie zapisu o podstawie 7 jest cyfra 2.

Łącznie oba twierdzenia są znane jako twierdzenie Fermata-Eulera, zaś jedną z ich konsekwencji jest zależność:

a -l=a *(n)-l (mod n)

Rzędem liczby a e $ „ jest najmniejsza liczba naturalna t = ord(a) taka, że:

a t = I (mod n)

Ważna zależność:    ord(a) I <j>(n)

Wynika ona z implikacji: _as =j (_mod_n) => _ord(_a) I s