Complete Solutions and Cycle Reachability

What this concept is

For ax ≡ b (mod m) with m>0, let g=gcd(a,m). A solution exists exactly when g divides b. When it does, divide a,b,m by g, solve the reduced coprime equation, and lift its single residue to g distinct representatives in [0,m).

Why it matters here

A schedule or cyclic probe can have no reachable target, one solution or many. Returning one verified witness does not establish a complete answer.

Concrete example

Solve 6x ≡ 8 (mod 14). Here g=2 divides 8, so reduce to 3x ≡ 4 (mod 7). The inverse of 3 is 5; the first representative is 20 mod 7 = 6. Lift by the reduced modulus 7 to obtain [6,13]. Both verify in the original equation.

Necessity follows because ax-b is a multiple of m and g divides both a and m, so g divides b. For sufficiency, invert the reduced coefficient. Every original solution must have the reduced residue x0 modulo m/g; the g representatives x0 + k*(m/g) for 0 ≤ k < g are distinct and fill exactly that class within [0,m).

If a=0, every residue solves the equation when m divides b, otherwise none does. If m=1, the sole canonical representative is 0. Handle these using the theorem rather than an inverse modulo 1.

Common confusion / misconception

Dividing the coefficient without dividing the modulus changes the problem. Testing returned witnesses alone misses omitted answers. A list-returning API may require time proportional to the number of solutions, even if finding its first representative uses few arithmetic operations.

How to use it

For a cycle of m slots starting at zero and step a, the target b is reachable iff gcd(a,m) divides b. The first return to zero takes m/gcd(a,m) steps. Use the same computation to explain a stride that visits only part of a ring; this is relevant to probe sequences, not a guarantee of good hash distribution.

Check yourself

With step 12 around 20 slots, can you reach slot 8 or slot 7? Answers: 8 is reachable with canonical times [4,9,14,19]; 7 is not. The cycle repeats after 5 steps.

Mini drill or application

Find all solutions of 8x ≡ 4 (mod 12). Then change the target to 3 and explain infeasibility. Show completeness without relying only on exhaustive testing.

Read this only if stuck

Source backbone: Mathematics for Computer Science reference. For the freely available original, use MIT’s 2015 Chapter 8 readings. See the reading guide for topic selection; chapter numbering can differ across editions.