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.

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 ngcd(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 ≡ 0 (mod p)). These integers k are then the set of those 0<k<p coprime to p, each multiplied by np. The number of such values k is then given by φ(p), where φ 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), because it corresponds with truncating x's base-2ⁿ expansion to the last digit, and its binary expansion to the last n bits, x % 2ⁿ = x & 2ⁿ-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) if n is prime, otherwise (n-1)! ≡ 0 (mod n) unless n = 4, in which case it is congruent instead to 2.
• Lucas's theorem : (nk) ≡ ∏∞i=0(n_ik_i) (mod b), where n_i is the ith base-b digit of n.

for modular exponentiation computation

• x*y ≡ (x%n)*(y%n) (mod n), so x^p%n can be calculated as (( ... (((x%n)*x)%n)* ... )*x)%n
• Euler's theorem : x^φ(m) ≡ 1 (mod m), so xⁿ ≡ x^n%φ(m) (mod m).

• If n is computed from its factorisation, n%φ(m) can be computed efficiently also
• Note that Fermat's little theorem is the special case of Euler's theorem, since for primes p, φ(p) = p-1

Uses in Conway's Game of Life

• Colour is mod 2.
• Trombone slides are mod 8.
• Filters for glider streams require certain characteristics, e.g. 8 mod 16 for Rich's p16 and 5 mod 15 or 10 mod 15 for Karel's p15.
• Phase shifters make use of modular arithmetic, e.g. 28P7.1 phase shifts once when the overall period is 1 mod 7.
• Pentadecathlon phase shifters work when the overall period is 6, 9, or 14 mod 15, depending on the mechanism. 6 corresponds to the monoicosathlon, 9 to one modification of the p54 shuttle, and 14 to the p44 pi-heptomino hassler.
• Many of the smallest known oscillators of a period that are part of infinite families rely on modular arithmetic, such as 6 bits being 45 mod 120 and the number of gliders required in a rectifier being dependent on period mod 8 and the existence of a working 22hd reflector requiring the period being 4 mod 8.

See also

• Pólya enumeration theorem (the enumeration equations must return integers, so the division in the averaging is equivalent to floordiv, meaning the output of the equivalent modulo must be 0, through 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)
• Wikipedia articles:

• Chinese remainder theorem : Compute n (mod a*b) in terms of n (mod a) and n (mod b) with the extended Euclidean algorithm