Modular congruence

Two numbers a,b are congruent modulo a third number n if their values are equal when integer multiples of n are added or subtracted from them such that they both lie in the range 0<=x<n (an operation denoted with the % symbol). A function returning the value of x modulo n is given in most programming languages with the % operator (ie. x%n), and according to the C specification (followed by languages like Python), modulo has the same precedence as multiplication and division, and expressions involving multiple of the same precedence adjacent without brackets will be evaluated left-to-right.

Such equalities under the modulo operation are denoted as a≡b (mod n). For instance, 5≡8 (mod 3), because both of them (after multiples of 3 are subtracted) evaluate to 2. Alternatively (for integer modulo bases n), x%n is equivalent to taking x's expansion in base n and truncating the digits with greater place value than 1. Modular arithmetic is generally concerned with the behaviour of operations under the modulo operation with a fixed base.

Additional arithmetic rules allow manipulation of expressions involving modulo operations, such as that x*y%n=(x%n)*(y%n)%n, with which many computations involving modulo operators can be evaluated more efficiently than explicitly, such as modular exponentiation, where calculating x**p%n allows you to "unravel" the exponentiation into a series of multiplications, and modulo the result by n with each successive multiplication.

Beginning with integers n and x (such that 0<=x<n) and recursively adding an integer k to x and modulo'ing by n (ie. setting x=(x+k)%n) will cause x's value to oscillate with period n/gcd(n,k) (equivalently lcm(n,k)/k).

For a modulo base n and period p, for there to exist any integers k such that recursive addition of k has period p, p must be a factor of n (meaning n%p=0). These integers k are then the set of those 0<k<p coprime to p, each multiplied by n/p. The number of such values k is then given by phi(p), where phi is Euler's totient function,  A000010.

There is no similar such statement about modular integer multiplication by a constant, because unlike addition of a constant, the structure of its mapping is not invariant across all inputs. Due to this, similarly to cellular automata in finite planes as functions on the set of states, recursively applying a multiplication will cause integers to eventually enter one of several cycles, upon which the period depends. Implementations of modular exponentiation to large powers with small modulo bases can be further optimised by detecting the length of the cycle that an exponentiation process enters and finding the phase that it ends in by taking the remaining exponent (upon entry to the cycle) modulo this length, and using it as the index in the cycle.

Relationship with bitwise operators

In programming, where x,n are integer (as is usually necessary for bitwise operators) and n is known to be a power of 2, because it corresponds with truncating x's n-ary expansion to the last digit, and its binary expansion to the last log_2(n) digits, x%n=x&n-1, the latter of which can be more efficient to compute. The Stanford bit-twiddling hacks explain division by 1 less than a power of 2.

Notable congruences

These provide algebraic reduction steps for forms that can arise generally in modular arithmetic problems.

• Fermat's little theorem states that for a prime p and other integer c, c**p≡c (mod p).
• Wilson's theorem states that for an integer n, (n-1)! ≡ -1 (mod n).

See also

• Pólya enumeration theorem (through application of a corollary of which, the theorems above can be proven)

Further reading

• Conway's Game of Life: Mathematics and Construction, Appendix A.1 Modular Congruence
• Combinatorics I, the first chapter of Adam P. Goucher's book, Mathematical Olympiad Dark Arts (that explains a great deal more about modular arithmetic than this)