Cel mai bun răspuns
Mai întâi, trebuie să ne uităm la modul (sau la numărul pe care „încercăm să îl împărțim la). În acest caz, acesta este 1818. Apoi, introduceți 1818 în funcția totient a lui Euler , pentru a obține ϕ (18) ϕ (18). În special, pentru toate numerele întregi nn, avem
ϕ (n) = n∏p | n (1−1p), ϕ (n) = n∏p | n (1−1p),
unde produsul traversează toți unici factori primi ai lui nn. Deci, în acest caz,
ϕ (18) = (18) (1/2) (2/3) = 6.ϕ (18) = (18) (1/2) (2/3) = 6.
Ok, deci următorul pas este teorema lui Euler , care spune că pentru orice alt număr întreg aa care este relativ prim la nn, avem că aa la puterea ϕ (n) ϕ (n) lasă un rest de 11 atunci când este împărțit la nn. Adică,
aϕ (n) ≡1 (modn) .aϕ (n) ≡1 (modn).
Deoarece 1717 este într-adevăr relativ primar până la 1818, știm 176176 frunze un memento de 1. Aceasta înseamnă că putem continua să împărțim 176176 din 1720017200 fără a schimba restul. Un alt mod de a spune acest lucru este că 17 pentru orice putere care „un multiplu de 6 va lăsa restul de 1. Deci, în cele din urmă, deoarece 200 este cu 2 mai mult decât un multiplu de 6, știm că
17200≡172 (mod18) .17200≡172 (mod18).
Acest lucru face problema mult mai simplă – aproape că suntem acolo! O scurtătură aici pentru a termina problema este să ne dăm seama că 1717 lasă un rest de -1 -1 când este împărțit la 1818 (adică 17≡ − 1 (mod18) 17≡ − 1 (mod18)), deci 172172 lasă un rest de (- 1) 2 = 1. (- 1) 2 = 1.
Deci răspunsul nostru este 1 . Data viitoare când aveți o problemă care implică restul de o putere mare, puteți utiliza această soluție generalizată drăguță și sună inteligent în același timp :). Dacă nu ați mai văzut notația modmod înainte, consultați Aritmetica modulară .
PS Este posibil să fi auzit de un caz special al acestei teoreme numită mica teoremă a lui Fermat , care funcționează atunci când aveți un modul care „este un număr prim (nu este cazul aici). Teorema spune că pentru orice pp prim și întregul aa care nu este multiplu de pp,
ap − 1≡1 (modp) .ap − 1≡1 (modp).
Acesta este un truc interesant, dar practic același cu ceea ce „s mai sus deoarece since (p) = p − 1ϕ (p) = p − 1 pentru orice pp prim. Acest tip de întrebări devin cu adevărat simple dacă înțelegeți conceptul de resturi negative . Încercați întotdeauna și reduceți dividendul la 1 sau -1.
Rem [17 ^ 200/18] = Rem [(-1) ^ 200/18] = Rem [1/18] = 1
Răspuns
Context important necesar pentru rezolvarea problemei :
Știm că restul obținut atunci când r divide pq este produsul resturilor obținut atunci când r divide p și qseparately. Aceasta se numește lemma pe resturi. O puteți demonstra prin teorema divizării lui Euclid.
Soluția
17 atunci când este împărțit la 18 frunze rămase -1 (este convenabil să lucrați cu -1 decât 17)
Aplicând restul lemei la 17 × 17 × 17 … × 17 (2000 de ori) când este împărțit la 18 va fi restul obținut atunci când resturile individuale sunt înmulțite, adică -1 × -1 .. × -1 (2000 de ori), adică restul este 1 \ blacksquare
Dacă s-ar ridica 17 la un număr impar, restul ar fi -1 sau 17 .