skip to content

A window offset must satisfy a*x = b (mod n) - when does such an x exist, and how many are there modulo n?

level: seniorimportance: should knowfreq 46%

answer

  1. solvable only sometimes
  2. the gcd has to divide the target
  3. not always a unique answer
  4. exactly gcd(a, n) solutions modulo n
  5. spaced n/g apart

basics

~10 s

With g = gcd(a, n), the congruence a*x = b (mod n) is solvable exactly when g divides b. It then has exactly g solutions modulo n, spaced n/g apart, not one.

solid answer

~50 s

Let `g = gcd(a, n)`. Every value `a*x` can take modulo `n` is a multiple of `g`, so the congruence is **solvable if and only if `g` divides `b`**. When it does, divide the whole congruence through by `g`: `(a/g)*x = (b/g) (mod n/g)`. Now the coefficient is coprime to the reduced modulus, so it has an inverse and there is exactly **one** solution `x0` modulo `n/g`. Lifting back to the original modulus, that single class splits into `g` classes: `x0, x0 + n/g, x0 + 2n/g, ...` up to `x0 + (g-1)*n/g`. So the answer count is `g`, and the spacing between neighbouring solutions is `n/g` - two different numbers that are easy to swap. Only when `a` and `n` are coprime does the familiar "multiply by the inverse, get one answer" shortcut apply.

go deeper

for a junior

Remember that a*x = b (mod n) is not always solvable: the gcd of a and n must divide b. Only when that gcd is 1 do you get the single answer from multiplying by an inverse.

for a middle

Explain the reduction: divide the congruence by g to get a coprime coefficient modulo n/g, solve uniquely there, then lift back to g solutions spaced n/g apart.

for a senior

In running code this is a three-branch function - no solution, one solution, several - and the several case needs a stated policy for which offset the system means.

for a principal

The design decision is upstream: pick a modulus coprime to everything that will be divided out, and the multi-solution and no-solution branches stop existing across every caller.

## The three-part rule For the linear congruence `a*x = b (mod n)`, set `g = gcd(a, n)`. Everything follows from `g`: 1. **Solvable exactly when `g` divides `b`.** If `g` does not divide `b`, there is no solution at all. 2. **If solvable, there are exactly `g` solutions modulo `n`** - not one, and not `n`. 3. **Those solutions are spaced `n/g` apart**, forming a single arithmetic progression inside the residue range. The special case everyone remembers is `g = 1`: one solution, obtained by multiplying both sides by the inverse of `a`. That is the case, not the rule. ## Why the gcd has to divide b Write `a = g*a'` and `n = g*n'`. Any candidate solution means `a*x - b` is a multiple of `n`, that is `b = a*x - k*n = g*(a'*x - k*n')` for some integer `k`. The right-hand side is a multiple of `g`, so `b` must be one too. Contrapositively, if `g` does not divide `b`, no `x` and no `k` can make the equation hold - the congruence is not "hard", it is empty. ## A worked pair **Solvable:** `6*x = 9 (mod 15)`. Here `g = gcd(6, 15) = 3`, and 3 divides 9, so solutions exist and there should be three of them. - Divide through by 3: `2*x = 3 (mod 5)`. - The inverse of 2 modulo 5 is 3, since `2*3 = 6 = 1 (mod 5)`. - So `x = 3*3 = 9 = 4 (mod 5)`. - Lift to modulus 15 by adding multiples of `n/g = 5`: **x = 4, 9, 14**. Checking all three: `6*4 = 24 = 15 + 9`; `6*9 = 54 = 45 + 9`; `6*14 = 84 = 75 + 9`. All three reduce to 9 modulo 15. **Unsolvable:** `6*x = 8 (mod 15)`. Same `g = 3`, but 3 does not divide 8. Every value of `6*x` modulo 15 lies in `{0, 3, 6, 9, 12}`, and 8 is not among them. No amount of searching finds a solution. ## The same statement as a linear Diophantine equation `a*x = b (mod n)` is the equation `a*x + n*y = b` in integers with the `y` discarded, and the solvability rule is the same one: **`a*x + b*y = c` has an integer solution exactly when `gcd(a, b)` divides `c`**. That is the form the question takes when it arrives as a packing problem - assembling an exact payload size out of two fixed frame sizes, say 12 bytes and 20 bytes. `gcd(12, 20) = 4`, so only multiples of 4 are reachable at all. One caveat separates the mathematics from the implementation: the identity allows **negative** coefficients, and you cannot send a negative number of frames. With non-negative counts of 12 and 20, the reachable totals are 0, 12, 20, 24, 32, 36, 40, 44, and every multiple of 4 from 32 upward - so 4, 8, 16 and 28 are multiples of 4 that are still impossible. "Divisible by the gcd" is necessary; it is sufficient only when negative counts are allowed. ## Count versus spacing | quantity | value for a*x = b (mod n) | for 6*x = 9 (mod 15) | |---|---|---| | gcd `g` | gcd(a, n) | 3 | | solvable? | only if `g` divides `b` | yes, 3 divides 9 | | number of solutions mod n | `g` | 3 | | spacing between solutions | `n/g` | 5 | | reduced modulus solved first | `n/g` | 5 | The last two rows share a value, which is exactly why they get confused. The reduced problem lives modulo `n/g` and has one answer there; the original problem lives modulo `n` and has `g` answers, which happen to sit `n/g` apart. ## What this changes in a real system - **"Solve for the offset" is not a total function.** Code that computes a modular quotient needs a no-solution branch, not just a happy path. - **Multiple answers are a policy question.** When `g > 1` the system has `g` valid offsets and must decide which one it means - smallest, or the one satisfying a second constraint - rather than silently taking whichever the routine returns first. - **Forcing `g = 1` removes the whole problem.** Choosing a modulus coprime to every coefficient that will ever be divided out - a prime modulus being the blunt instrument - turns the three-part rule back into the one-solution shortcut.

  • Frames come in exactly 12 and 20 bytes - which exact payload sizes can be assembled?
    As integers, a*x + b*y = c is solvable exactly when gcd(a, b) divides c, and gcd(12, 20) = 4, so only multiples of 4 are candidates. Physical assembly also forbids negative counts, and with non-negative counts 4, 8, 16 and 28 remain unreachable while every multiple of 4 from 32 upward is buildable. Divisibility by the gcd is necessary, not sufficient.
  • Why is the solution count the gcd rather than always one?
    Dividing through by g shrinks the modulus to n/g, where the coefficient is coprime and the answer is unique. Lifting back to modulus n, each residue class modulo n/g splits into g classes modulo n, all of which satisfy the original congruence. The uniqueness is real - it just lives at the reduced modulus.
  • How do you find all solutions once you have one?
    Add multiples of n/g. If x0 solves it, so do x0 + k*(n/g) for k = 0 up to g-1, and after that the values repeat modulo n. Adding multiples of n instead finds only the one class you already had, which is the usual way code under-reports the solution set.

saying these in an interview costs you the question

  • Assumes every linear congruence has exactly one solution
  • Multiplies by an inverse without checking one exists
  • Reports n/g solutions instead of g
  • Thinks an unsolvable congruence just needs a bigger search
  • Treats divisibility by the gcd as enough for non-negative counts