Applications of modular arithmetic in programming

[manasij7479]

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)

[GReaper]

A youtube video has recently raised my attention to the correlation between the fibonacci sequence and modulo.
Pisano period

[Mario F.]

Since prime numbers are so ubiquitous in the field of cryptography, and since modular arithmetic is still today the only reliable way to obtain prime numbers, it is hard to ignore cryptography as one field where you can apply modular arithmetic. But I guess you know that already...

So, for other alternatives:

- Modulus is a most useful operator in dealing with cyclic data (dates and time, some kinds of trees, RNGs, et cetera), but also instrumental in defining your own cyclic data types on languages that don't have one.

- One of the difficulties in traditional tabular data representation in database engines is that it -- along with SQL -- makes it hard to store and extract data organized in an hierarchic manner. There are methods for solving this (see Celko's Trees and Hierarchies in SQL), but which require some unusual table structures. But until I got bored of it, I was successfully working in a personal project that made extensive use of modular arithmetic to transform back and forth between tabular data and hierarchical data. It was an engine that allowed me to store data in traditional tabular format and transform it into hierarchical data according to pre-defined set of rules and constraints. What I was aiming for was for less clutter in the database, and all data transformations to be done programmatically outside of SQL.