Modular congruence

Let p%q = p-⌊pq⌋*q ("p modulo q"), ie. adding or subtracting integer multiples of q to p such that it lies in the range 0 ≤ x < q.

Two numbers a,b are congruent modulo a third number n iff a%n = b%n.

Such congruences are denoted as a ≡ b (mod n). For instance, 5 ≡ 8 (mod 3), because 5%3 = 5-3 = 8%3 = 8-6 = 2. Alternatively (for integer modulo bases n), x%n is equivalent to taking x's expansion in base n and removing all but the last digit. Modular arithmetic is generally concerned with the behaviour of operations under modulo by a fixed base.

Given fixed integers k,x ≠ 0, the sequence a(i) = i*k % n oscillates, with period ngcd(n,k) = lcm(n,k)k.

For a modulo base n and period p, for there to exist any integers k with sequences of period p, p must be a divisor of n (written p|n). The number of k whose addition has period p is

#({k: k ∈ ℕ and k<n and ngcd(n,k)=p}) = { φ(p) . p|n0 . . .else

where φ(p) is Euler's totient function, the number of 1 ≤ k < p such that gcd(p,k)=0 (A000010).

Modular multiplication

Two numbers a,b are called multiplicative inverses modulo n if a*b ≡ 1 (mod n), and b is then occasionally written a^-1.

If gcd(n,a) ≠ 1, gcd(n,a) will divide any number of the form a*b % n, which as such cannot equal 1, so a does not have a multiplicative inverse. However, the set S = {k: k ∈ ℕ and k<n and k|n} form a group under multiplication, meaning that for all integers c ∈ S, {c*k%n: k ∈ S} = S (ie. mapping a multiplication over the set permutes it), and every member has an inverse in the set (findable using the extended Euclid's algorithm).

There is no similarly simple statement for fixed n and p, enumerating the k such that the period of multiplication by k (modulo n) is p. Multiplication by numbers not coprime to n is neither

• injective (such that all numbers 0 ≤ x < n produce distinct values under multiplication by k modulo n), since there are only ngcd(n,k) destinations they can be mapped to, nor
• surjective (such that for given n,k, every value y can have an x found such that k*x ≡ y (mod n)), since x would generally have to equal y*k^-1.

Due to this, similarly to cellular automata in spaces with finitely many states, recursively applying a multiplication will cause integers to eventually enter one of several cycles, across which the period varies. 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.

The Chinese remainder theorem states that an unknown x's value (mod n) can be determined uniquely from a set of congruences of the form x ≡ c_i (mod m_i) for ∏.m_i ∈ m(m_i) = n, where all pairs of indexes i ≠ j have gcd(m_i,m_j).

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).

It is also given as c^p-1 ≡ 1 (mod p), however this pertains only for coprime c,p, whereas c^p ≡ n (mod p) is irrespective

• 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 (preventing any number partway through the computation from exceeding (n-1)*x)
• Euler's theorem: For coprime x,m 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

see also exponentiation by squaring

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)

Notes

Let f=λ n,k: ' '*(len(str(n))-len(str(k)))+str(k)

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)