skip to content

Modular Arithmetic

14 roadmaps15 questions

Congruence classes and residue arithmetic, modular inverses from the extended Euclidean identity, Euler's totient and the Chinese remainder theorem. Interviewers probe it behind hashing and keys.

part ofComputer science fundamentalsoverview, primer and where to startread it →
on this pageshow

explore

questions

15

Given ac congruent to bc modulo n, when may you cancel c and conclude that a is congruent to b modulo n?

level: middleimportance: must knowfreq 48%

answer

  1. the shared factor is the trap
  2. a product can vanish without either factor
  3. gcd of factor and modulus
  4. coprime means cancel freely
  5. otherwise the modulus shrinks too

basics

~20 s

Only when c and n share no common factor, that is when their greatest common divisor is 1. Otherwise the honest conclusion is a congruent to b modulo n divided by that greatest common divisor, which is weaker.

solid answer

~50 s

Cancellation is the one schoolbook move that does not transfer. From `ac = bc (mod n)` all you know is that `n` divides `c(a - b)`, and `n` can be satisfied by the factor `c` rather than by `a - b`. If `gcd(c, n) = 1`, then `n` must divide `a - b` and cancelling is legitimate. If `g = gcd(c, n)` is bigger than 1, the correct statement is `a = b (mod n/g)` - the same congruence on a **shrunken modulus**. The standard counterexample: `2 * 3 = 6` and `2 * 8 = 16` are congruent modulo `10`, yet `3` and `8` are not congruent modulo `10`; with `g = 2` they are congruent modulo `5`, and indeed both leave remainder `3`. A prime modulus removes the trap entirely for any factor it does not divide.

go deeper

for a junior

Remember the rule as a checkable condition: you may cancel a factor from both sides of a congruence only when that factor shares no divisor with the modulus.

for a middle

Explain the mechanism - the modulus divides a product, and a composite modulus can be satisfied by the factor instead of by the difference, which is why coprimality is what repairs it.

for a senior

Spot the move in review when it is disguised as a simplification, and say what it costs: the surviving claim lives on a smaller modulus and therefore accepts more values than the original check did.

for a principal

Treat modulus choice as a design decision - a prime modulus buys cancellation for every non-vanishing factor and removes a whole class of subtle validation bugs before anyone can write one.

## Why the step is unsafe at all Addition, subtraction and multiplication are well defined on residue classes, so people reasonably assume the inverse moves are too. They are not. Unwinding `ac = bc (mod n)` gives exactly one fact: `n` divides `c(a - b)`. Divisibility of a **product** does not force divisibility of a chosen **factor**. The modulus can be satisfied by `c` alone, leaving `a - b` free to be anything. That is the whole failure in one sentence, and it is why the condition that repairs it is a statement about `c` and `n` rather than about `a` and `b`. ## The condition, stated in the direction it is used - **Safe:** if `gcd(c, n) = 1` then `ac = bc (mod n)` implies `a = b (mod n)`. Because `c` contributes none of the factors of `n`, every one of them must come from `a - b`. - **General:** let `g = gcd(c, n)`. Then `ac = bc (mod n)` implies `a = b (mod n/g)` - true always, and the strongest thing you may say. - **Not implied:** `a = b (mod n)` itself, whenever `g > 1`. Asserting it is over-claiming, not a rounding error. The general form follows in three steps. Write `n = g * n'` and `c = g * c'`, where `gcd(c', n') = 1` by construction. From `n | c(a - b)` we get `g n' | g c' (a - b)`, so `n' | c'(a - b)`, and since `c'` shares nothing with `n'`, `n' | (a - b)`. That is `a = b (mod n/g)`. ## A worked case to carry Take `n = 10` and `c = 2`: 1. `2 * 3 = 6` and `2 * 8 = 16`; both leave remainder `6` modulo `10`, so `2*3 = 2*8 (mod 10)`. 2. Naive cancellation would claim `3 = 8 (mod 10)`. False - the remainders are `3` and `8`. 3. The correct conclusion uses `g = gcd(2, 10) = 2`: `3 = 8 (mod 5)`. True - both leave remainder `3`. The modulus lost a factor of `2` in the cancellation, and that factor is exactly the information the shared divisor absorbed. ## Which moduli make the trap disappear | modulus | cancellable factors | what can still hide | |---|---|---| | a prime `p` | every `c` not divisible by `p` | only the degenerate case `c = 0 (mod p)` | | a prime power `p^k` | every `c` not divisible by `p` | factors carrying `p`, which shrink the modulus | | a general composite `n` | only `c` with `gcd(c, n) = 1` | every factor sharing a divisor with `n` | This is the structural reason prime moduli are preferred whenever residue arithmetic has to behave like ordinary arithmetic: modulo a prime there are **no zero divisors**, meaning no pair of non-zero classes multiplies to zero, so a product that vanishes forces one of its factors to vanish. Modulo a composite there are zero divisors - `2` and `5` modulo `10` are the smallest example, since `2 * 5 = 10` is congruent to `0` - and a vanishing product proves nothing about either factor. ## How the mistake shows up in practice It rarely appears as a literal division. It appears as a simplification: a validation rule that divides a weighted total and its target by a shared factor before comparing, a derivation that strikes the same coefficient from both sides of a congruence, a reduction of a scale factor to make two totals comparable. Each is the same move, and each silently widens the set of values accepted, because a congruence on the shrunken modulus `n/g` holds for `g` times as many residues as one on `n`. The practical discipline is short. Before cancelling anything from a congruence, compute the greatest common divisor of the factor and the modulus. If it is `1`, cancel freely. If it is not, either keep the factor in place or divide the modulus by the same amount and remember that you now have a weaker claim than the one you started with. Note that the weaker claim is still a genuine claim - the mistake is asserting the original modulus, not supposing that nothing at all survives.

  • Why does a prime modulus make cancellation safe for every factor it does not divide?
    Modulo a prime `p`, any `c` that `p` does not divide has `gcd(c, p) = 1`, so the coprimality condition is automatic. Equivalently there are no zero divisors: a product congruent to zero forces one factor to be congruent to zero, so a vanishing difference must come from `a - b`.
  • In 2*3 congruent to 2*8 modulo 10, what is the correct conclusion once the factor 2 is removed?
    `gcd(2, 10) = 2`, so the conclusion is `3 = 8 (mod 5)`, which is true because both leave remainder `3`. The stronger claim `3 = 8 (mod 10)` is false, and the gap between the two is exactly the factor absorbed by the shared divisor.
  • Does a failed cancellation mean nothing at all can be said about a and b?
    No, and treating it that way discards a real fact. The congruence on the reduced modulus `n/g` always holds; it simply admits `g` times as many residues as a congruence on `n` would. It is a weaker constraint, not an absent one.

saying these in an interview costs you the question

  • Cancelling a shared factor as if the congruence were ordinary integer equality
  • Believing cancellation always works whenever the modulus is odd
  • Keeping the original modulus after dividing both sides by a shared factor
  • Blaming the mismatch on overflow or remainder sign rather than structure
  • Claiming nothing follows at all once the factor shares a divisor with the modulus
open as a page

Bucketing keys by remainder modulo n collapses integers into residue classes: what exactly does that collapse preserve?

level: middleimportance: must knowfreq 62%

basics

~10 s

Addition, subtraction and multiplication survive: the class of a sum or product depends only on the input classes, never on which representatives you picked. Order, cancellation and the exponent position do not survive.

open as a page

A multiplicative inverse of a modulo n does not always exist - for which a does it exist, and why?

level: middleimportance: must knowfreq 62%

basics

~20 s

A value a has a multiplicative inverse modulo n exactly when gcd(a, n) = 1. If they share a factor g > 1, every product a*x reduced modulo n is a multiple of g, and 1 never is.

open as a page

How does the extended Euclidean algorithm turn gcd(a, n) = 1 into an actual inverse of a modulo n?

level: middleimportance: must knowfreq 55%

basics

~20 s

It returns integers x and y with ax + ny = gcd(a, n), by carrying those two coefficients alongside the remainders. When the gcd is 1, reducing modulo n drops the n*y term, so x is the inverse of a.

open as a page

Euler's theorem shrinks a huge exponent: when computing g^k mod n, what licenses replacing k with k mod phi(n)?

level: seniorimportance: must knowfreq 58%

basics

~20 s

Euler's theorem gives g^phi(n) congruent to 1 mod n whenever gcd(g, n) = 1, so the powers of g cycle with a period dividing phi(n) and only k mod phi(n) matters. Without that coprimality the reduction is simply invalid.

open as a page

Under the Chinese remainder theorem, why do a record's remainders under two coprime moduli pin exactly one value below their product?

level: seniorimportance: must knowfreq 55%

basics

~20 s

Two values with the same pair of remainders differ by a multiple of both moduli, and for coprime moduli that forces a multiple of their product, so at most one such value lies below the product. Counting shows every pair occurs.

open as a page

A validator tests divisibility by nine by summing a number's decimal digits: which congruence makes that legitimate?

level: middleimportance: should knowfreq 38%

basics

~20 s

Ten is congruent to 1 modulo 9, so every power of ten is congruent to 1 as well, which makes any number congruent to the sum of its digits modulo 9. The digit test is that congruence, not a decimal coincidence.

open as a page

Euler's totient phi(n) counts the integers up to n that are coprime to it - why can you read it off n's prime factorization?

level: middleimportance: should knowfreq 42%

basics

~20 s

Euler's totient is multiplicative across coprime factors, so phi(n) is the product of phi over n's prime powers, and phi(p^k) = p^k - p^(k-1) because within a prime power only the multiples of p are excluded.

open as a page

A counter changes only in steps of two, so its residue modulo 2 never changes: what does an odd reading prove?

level: seniorimportance: should knowfreq 34%

basics

~20 s

An odd reading proves the counter was not produced by those steps alone: either it started odd, or a write outside the listed operations touched it. A preserved residue converts an impossible value into a search filter.

open as a page

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%

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.

open as a page

When a fingerprinting service must undo multiplications modulo n, how does a prime modulus differ from a power-of-two one?

level: principalimportance: should knowfreq 36%

basics

~20 s

Modulo a power of two only the odd residues are invertible, so half of every possible base is unusable and the lowest fingerprint bit degenerates into a parity. Modulo a prime every nonzero residue is invertible, which is what makes a collision bound provable.

open as a page

You must choose two moduli for a two-coordinate placement scheme over a fixed identifier range - what decides the pair?

level: principalimportance: should knowfreq 32%

basics

~20 s

Coprimality and size decide it: coprime moduli make the two coordinates independent and reach all of their product, while the product must cover the identifier range or collisions are forced. A shared factor shrinks the reachable space to the least common multiple.

open as a page

Modulo a prime p, why does raising a to the power p-2 act as its inverse, and when does that route fail?

level: seniorimportance: nice to knowfreq 34%

basics

~20 s

Fermat's little theorem says a^(p-1) = 1 (mod p) for a prime p and any a not divisible by p. Multiplying that by the inverse of a leaves a^(p-2) as the inverse. It fails for a composite modulus and for a divisible by p.

open as a page

Two placement coordinates use the moduli 8 and 12 - what does sharing the factor 4 cost that scheme?

level: seniorimportance: nice to knowfreq 28%

basics

~20 s

Only 24 of the 96 remainder pairs ever occur, because both coordinates must agree modulo the gcd 4, and each pair that does occur is shared by four values below 96. Addressing is unique only modulo the lcm 24, not the product.

open as a page

You are choosing the modulus and the weights for an account-number check digit: what does the modulus decide?

level: principalimportance: nice to knowfreq 26%

basics

~20 s

The modulus decides which mistakes can hide. A prime modulus above the digit range has no zero divisors, so with weights that differ by position no single-digit change and no adjacent transposition can leave the weighted sum's class unchanged.

open as a page