Wpis z mikrobloga

@Grigorian: ach dyskretna <3. Małe tw Fermata.

21= 3 * 7; z tw. 2^2 mod 3 = 1, 2^6 mod 7 = 1;
2^32643=2^32642 * 2=2^32640 * 2^3.
Oczywiście jak 2^k mod n = 1, to 2^(ak) mod n też równa się 1.
Zatem 2^32642 mod 2 = 1, 2^32640 mod 7 = 1, więc

2^32643 mod 2 = 1*2^1 mod 3 = 2
2^32643 mod 7 = 1*2^3 mod 7
@Grigorian:
Można też korzystać z faktu, że kolejne potęgi dwójki będą okresowo dawać te same reszty z dzielenia przez 21 :)
2^(6k) daje resztę 1
2^(6k+1) daje resztę 2
2^(6k+2) daje resztę 4
2^(6k+3) daje resztę 8
2^(6k+4) daje resztę 16
2^(6k+5) daje resztę 15
A istotnie 32643 = 3 (mod 6), więc 2^(32643) = 8 (mod 21)