Mennyit ad maradékul (2^2014) / 2011?

Mivel 2011 prímszám, ezért (Kis Fermat):

2^(p-1) mod p = 1 , vagyis

2^2010 mod 2011 = 1 , ez szorozva 2^4 -nel -> 16

Általánosságban, ha a^b mod (p)-t kell meghatározni (a "kicsi", b és p "nagy"), akkor keressünk olyan j,k,l-t, hogy

a^j=k*p+l, ahol l "kicsi". Ekkor a^b mod (p)=(a^j)^([b/j])*a^(b mod j) mod (p)=l^([b/j])*a^(b mod j) mod (p).

Ezt aztán el lehet játszani a létrejövő szorzat tagjaival is, a kitevők egyre kisebbek lesznek, a fenti számhármas pedig megválasztható úgy, hogy l nem legyen "túl nagy".

"Mivel 2011 prímszám..."

Ez nem látszik azonnal, de lehet sejteni, mert ránézésre nem osztója: 2, 3, 5, 7, 11.

Még 9 osztással - 13, 17, ..., 43 (45*45=2025>2011) - bizonyítható.