. Trivial: Zadanko dla chętnych. Oblicz resztę z dzielenia 2013²⁰⁸⁰ : 13

Timmy: Czy wynik to 3?

Basia: tak samo mi wyszło; 3

Vizer: Nie zabierałem się za to, ale mam pytanie, czy bez znajomości kongruencji można sobie jakoś dać z tym radę?

Godzio: Można

Basia: można a/b = c reszta d a = (c*b+d) aⁿ = (c*b+d)ⁿ dwumian Newtona wszystkie składniki oprócz ostatniego są podzielne przez b czyli teraz badamy dⁿ i tak krok po kroku

Basia: 2013 = 154*13+11 czyli badamy 11²⁰⁸⁰ = 11^2*1040 = 121¹⁰⁴⁰ i tak dalej

Trivial: Można to rozwiązać sposobem Basi, ale jest sposób by uciąć połowę obliczeń. Przez r oznaczam resztę z dzielenia. Definiuję mod jako a mod n = r (reszta z dzielenia a przez n) Najpierw parę własności. 1. ab mod n = (a mod n)*(b mod n) mod n. 2. a^x+y mod n = (a^x*a^y) mod n = (a^x mod n)(a^y mod n) mod n 3. a² mod n = (a mod n)² mod n 2013²⁰⁸⁰ mod 13 = 2013^{2048 + 32} mod 13 = = (2013²¹¹ mod 13)*(2013²⁵ mod 13) mod 13 = u 2013 mod 13 = 11 2013² mod 13 = 11² mod 13 = 121 mod 13 = 4 2013⁴ mod 13 = 16 mod 13 = 3 2013⁸ mod 13 = 9 mod 13 = 9 2013¹⁶ mod 13 = 81 mod 13 = 3 ... 2013²ⁿ mod 13 = 3 dla n parzystego, 9 dla nieparzystego. n > 1 u = (9*9) mod 13 = 81 mod 13 = 3.

b.: rachunki są chyba łatwiejsze, jak sie zauważy (*), że 2013¹² mod 13 = 1 ponieważ 2080 = 12k + 4, więc 2013²⁰⁸⁰ = (2013¹²)^k * 2013⁴ = 1 * 3 = 3 (mod 13) (*) można też uniknąć tych rachunków, jeśli się zna małe twierdzenie Fermata

Trivial: Fajny sposób, b.