I've been studying Number Theory recently and modular arithmetic seems to have many beautiful results (and applications).

For example, to find the last k digits of factorial n, I need not compute the factorial but compute the modulo at every step instead.

I want some ideas about some novel and interesting things that you can do with modular arithmetic (close topics in number theory are fine too.)

(With links or brief explanation of the theory if it not obvious, please)