FAILURE MAP
← Case archive

FA-14371 / Numerics / Open access

Linear congruence solutions: quotient modulus · case 01

The exact linear congruence solutions result violates the stated contract at quotient modulus.

Verified by executionVariant 1 · 8 checks per implementationDownload source bundle ↓JSON ↗

ROOT CAUSE

The quotient modulus step uses m instead of m//g.

VERIFIED REPAIR

Use m//g at the quotient modulus step.

Unsuccessful approach: The partial repair g still violates the quotient modulus invariant.

Case contract

Input [a,b,m], m>0; sorted all x in [0,m) with a*x congruent b modulo m.

Why this case matters

Exact discrete arithmetic with observable algorithmic state; no floating point approximation is used.

1 / The failure

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a,b,m=x
    g=math.gcd(a,m)
    if b%g != 0: return []
    q=m
    r=((b//g)*pow(a//g,-1,q))%q if q>1 else 0
    return sorted(r+k*q for k in range(g))
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, -6, 2], [0, 1]), ([1, -6, 4], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -6, 2], [0]), ([1, -6, 3], [0]), ([1, -6, 5], [4]), ([1, -6, 6], [0])], [([2, -6, 4], [1, 3]), ([1, -6, 8], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -5, 6], [1]), ([1, -5, 7], [2]), ([1, -5, 8], [3]), ([1, -5, 9], [4])], [([2, -6, 6], [0, 3]), ([1, -6, 11], [5]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -4, 11], [7]), ([1, -4, 12], [8]), ([1, -3, 1], [0]), ([1, -3, 2], [1])], [([2, -6, 8], [1, 5]), ([1, -5, 3], [1]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -2, 4], [2]), ([1, -2, 5], [3]), ([1, -2, 6], [4]), ([1, -2, 7], [5])], [([2, -6, 10], [2, 7]), ([1, -5, 7], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -1, 9], [8]), ([1, -1, 10], [9]), ([1, -1, 11], [10]), ([1, -1, 12], [11])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
explicit oracle 0[1, 3][0, 1]Failed
explicit oracle 1[2][2]Passed
explicit oracle 2[0][0]Passed
explicit oracle 3[6][6]Passed
explicit oracle 4[0][0]Passed
explicit oracle 5[0][0]Passed
explicit oracle 6[4][4]Passed
explicit oracle 7[0][0]Passed

SHA-256 / 77a86e8215f427bdd0af48b1397f08cb0ae4980ee64f821c3d5b285ae387cab0

2 / The unsuccessful fix

Exit 1
"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a,b,m=x
    g=math.gcd(a,m)
    if b%g != 0: return []
    q=g
    r=((b//g)*pow(a//g,-1,q))%q if q>1 else 0
    return sorted(r+k*q for k in range(g))
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, -6, 2], [0, 1]), ([1, -6, 4], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -6, 2], [0]), ([1, -6, 3], [0]), ([1, -6, 5], [4]), ([1, -6, 6], [0])], [([2, -6, 4], [1, 3]), ([1, -6, 8], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -5, 6], [1]), ([1, -5, 7], [2]), ([1, -5, 8], [3]), ([1, -5, 9], [4])], [([2, -6, 6], [0, 3]), ([1, -6, 11], [5]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -4, 11], [7]), ([1, -4, 12], [8]), ([1, -3, 1], [0]), ([1, -3, 2], [1])], [([2, -6, 8], [1, 5]), ([1, -5, 3], [1]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -2, 4], [2]), ([1, -2, 5], [3]), ([1, -2, 6], [4]), ([1, -2, 7], [5])], [([2, -6, 10], [2, 7]), ([1, -5, 7], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -1, 9], [8]), ([1, -1, 10], [9]), ([1, -1, 11], [10]), ([1, -1, 12], [11])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
explicit oracle 0[1, 3][0, 1]Failed
explicit oracle 1[0][2]Failed
explicit oracle 2[0][0]Passed
explicit oracle 3[0][6]Failed
explicit oracle 4[0][0]Passed
explicit oracle 5[0][0]Passed
explicit oracle 6[0][4]Failed
explicit oracle 7[0][0]Passed

SHA-256 / d8b2d5648048c1efb90e1c7c7fa41c547046825ffc1855dfc2934c23f1892055

3 / The verified repair

Exit 0
"""Failure Map reference implementation. Python standard library only."""
import json
import math
import itertools
from fractions import Fraction
N = 1
observations = []
def solve(x):
    a,b,m=x
    g=math.gcd(a,m)
    if b%g != 0: return []
    q=m//g
    r=((b//g)*pow(a//g,-1,q))%q if q>1 else 0
    return sorted(r+k*q for k in range(g))
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, -6, 2], [0, 1]), ([1, -6, 4], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -6, 2], [0]), ([1, -6, 3], [0]), ([1, -6, 5], [4]), ([1, -6, 6], [0])], [([2, -6, 4], [1, 3]), ([1, -6, 8], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -5, 6], [1]), ([1, -5, 7], [2]), ([1, -5, 8], [3]), ([1, -5, 9], [4])], [([2, -6, 6], [0, 3]), ([1, -6, 11], [5]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -4, 11], [7]), ([1, -4, 12], [8]), ([1, -3, 1], [0]), ([1, -3, 2], [1])], [([2, -6, 8], [1, 5]), ([1, -5, 3], [1]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -2, 4], [2]), ([1, -2, 5], [3]), ([1, -2, 6], [4]), ([1, -2, 7], [5])], [([2, -6, 10], [2, 7]), ([1, -5, 7], [2]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -1, 9], [8]), ([1, -1, 10], [9]), ([1, -1, 11], [10]), ([1, -1, 12], [11])]]
for i, (args, expected) in enumerate(fixtures[N-1]):
    check("explicit oracle %d" % i, solve(args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
Boundary fixtureActualExpectedOutcome
explicit oracle 0[0, 1][0, 1]Passed
explicit oracle 1[2][2]Passed
explicit oracle 2[0][0]Passed
explicit oracle 3[6][6]Passed
explicit oracle 4[0][0]Passed
explicit oracle 5[0][0]Passed
explicit oracle 6[4][4]Passed
explicit oracle 7[0][0]Passed

SHA-256 / 22c7634e9c3b3822aa61a5e5387bf1f45b465b7942ce70b8aba4edab6f17e951

Verification & scope

A deterministic bounded teaching model. Inputs are restricted to the explicit contract; this is not a production algebra library. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.

Observations recorded using Python 3.12.14 at 2026-09-29T14:39:16.225512+00:00.

Case digest / 41edac582f141c2b30b4db7205b928523159ef506ab104b3b60b91e8c2bc0479