małe tw. Fermata bartmanxxx: Oblicz" (a) 14 do potęgi 20 mod 17; (b) 11 do potegi 99 mod 13; Znajdz resztę z dzielenia liczby "3 do potęgi 80" + "7 do potęgi 80" przez 10. Wykaż że 31|(50 do potęgi 31 − 20 do potęgi 31 − 30 do potęgi 31).

Krzysiek: 14²⁰ ≡ 14⁴ ≡ 38416 ≡ 13 mod 17 11⁹⁹ ≡ 11³ ≡ 1331 ≡ 5 mod 13 3⁸⁰ + 7⁸⁰ ≡ 3⁰ + 7⁰ ≡ 2 mod 10 50³¹ − 20³¹ − 30³¹ ≡ 50¹ − 20¹ − 30¹ ≡ 0 mod 31

bartmanxxx: Krzysiek, rozpiszesz mi te przykłady bardziej? Szczególnie pierwszy i trzeci dlaczego tak jest...

Krzysiek: A drugi nie?

bartmanxxx: w sumie też... nie umiem sobie tego uzmysłowic... prosze

Krzysiek: 14²⁰ = 14¹⁶ * 14⁴ Z MTF 14¹⁶ ≡ 1 mod 17, więc 14²⁰ ≡ 14^{20 mod 16} ≡ 14⁴ ≡ 14² * 14² ≡ 9 * 9 ≡ 81 ≡ 13 mod 17

bartmanxxx: i pozostałe przykłady są na podobnej zasadzie, tak?

Krzysiek: 11⁹⁹ ≡ 11^{99 mod 12} ≡ 11³ ≡ 5 mod 13

Krzysiek: Wiesz co to funkcja eulera?

bartmanxxx: okey... już rozumiem wszystko dziekuje bardzo

Krzysiek: W trzecim przykładzie, 10 nie jest liczbą pierwszą.. Trzeba skorzystać z twierdzenia Eulera, które mówi, że jeśli liczby a i m są względnie pierwsze to a^φ(m) ≡ 1 mod m gdzie φ(m) oznacza funkcję Eulera, tzn. liczbę liczb względnie pierwszych z m z zakresu [0;m). Jest to uogólnione MTF, φ(p) = p−1.. gdzie p to liczba pierwsza