259^33mod100 Ala: Hej, czy moglby mi ktos pokazac jak szybko rozwiazac: 259³³mod100? (wynik to 79)

Adamm: https://matematykaszkolna.pl/forum/355567.html

Ala: Niestety nadal nie rozumiem, mozna prosic o jakis przyklad?

Ala: Nie byloby problemu gdyby zamiast 100 bylaby liczba mniejsza niz potega... Ale tutaj tak nie jest i szukam SZYBKIEGO sposobu na obliczenie modulo

Adamm: 259³³≡(−1)³³≡3 mod 4 to jest dosyć proste 259³³≡9³³ mod 25 to też φ(25)=20 9³³≡3⁶⁶≡3⁶≡27²≡4 mod 25 x≡3 mod 4 x≡4 mod 25 z drugiego mamy x≡4, 29, 54, 79 mod 100 to są nasi kandydaci a z drugiego x≡79 mod 100, i to nasz wynik

Mila: Skorzystaj z dwumianu Newtona 259³³=(300−41)³3=

	33 1		33 2		33 1
=30033−		*30032*41+		*30031*41+.....+		*3001*4132−4133=

każdy składnik oprócz ostatniego jest liczbą podzielną przez 100⇔ =k*100−41³³, k∊N 41³³=(40+1)³³=

	33 1		33 32
=4033+		*4032+......+		*401+1=

każdy składnik oprócz dwóch ostatnich jest liczbą podzielną przez 100 33*40+1=1321=1300+21 259³³=m*100−21=−21(mod100)=79(mod100)