Podnoszenie liczby do wysokiej potęgi

n3ons · Post autor: **n3ons** » 29 paź 2007, o 16:00

jestem w tym momencie w Algebrze...i mamy dział "stryktury dwuzdaniowe" (ciała, pierscienie itp). i koleś dał nam zadanie:

napisz program który obliczy resztę z dzielenia (234^762 podzielone na 18). i teraz bajer polega na tym tak aby nie podnosić 234 do tej dużej potęgi...niestety ja nie wiem jak to zrobić...ma ktoś jakiś pomysł?

Post autor: **Szemek** » 29 paź 2007, o 17:12

\(\displaystyle{ 234=18 13}\)

n3ons · Post autor: **n3ons** » 29 paź 2007, o 17:21

sory ale :
a)co ja mam z tym zrobic? bo chyba nie wiele mi to daje...
b)co jesli beda liczby ktorych sie nie da tak rozpisac...;/

Post autor: **Emiel Regis** » 29 paź 2007, o 17:27

\(\displaystyle{ 234^{762} \ mod \ 18=(234 \ mod \ 18)^{512+128+64+32+16+8+2} \ mod \ 18=...}\)
Czyli najpierw samą liczbę dzielisz modulo 18. Potem stopniowo podnosisz ją do coraz większych potęg dwójki dzieląc za każdym razem modulo 18. Troche pomysłowości i powinno sprawnie Ci to pójść.

Aha. Nastepne swoje posty pisz już w texu.