FAILURE MAP
← Case archive

FA-14381 / Numerics / Open access

Linear congruence solutions: coset spacing · case 01

The exact linear congruence solutions result violates the stated contract at coset spacing.

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

ROOT CAUSE

The coset spacing step uses r+k instead of r+k*q.

VERIFIED REPAIR

Use r+k*q at the coset spacing step.

Unsuccessful approach: The partial repair (r+k*q)%q still violates the coset spacing 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//g
    r=((b//g)*pow(a//g,-1,q))%q if q>1 else 0
    return sorted(r+k for k in range(g))
def check(label, actual, expected):
    observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[([2, -6, 4], [1, 3]), ([2, -6, 2], [0, 1]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -6, 2], [0]), ([1, -6, 3], [0]), ([1, -6, 4], [2]), ([1, -6, 5], [4])], [([2, -6, 6], [0, 3]), ([2, -6, 8], [1, 5]), ([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, 8], [1, 5]), ([2, -4, 2], [0, 1]), ([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, 10], [2, 7]), ([2, -4, 8], [2, 6]), ([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, 12], [3, 9]), ([2, -2, 2], [0, 1]), ([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, 2][1, 3]Failed
explicit oracle 1[0, 1][0, 1]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[2][2]Passed
explicit oracle 7[4][4]Passed

SHA-256 / 0d147554a0b2cb897fe47564b37118deec372930a5f5ac481e7cb1abdfd07400

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=m//g
    r=((b//g)*pow(a//g,-1,q))%q if q>1 else 0
    return sorted((r+k*q)%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, 4], [1, 3]), ([2, -6, 2], [0, 1]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -6, 2], [0]), ([1, -6, 3], [0]), ([1, -6, 4], [2]), ([1, -6, 5], [4])], [([2, -6, 6], [0, 3]), ([2, -6, 8], [1, 5]), ([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, 8], [1, 5]), ([2, -4, 2], [0, 1]), ([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, 10], [2, 7]), ([2, -4, 8], [2, 6]), ([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, 12], [3, 9]), ([2, -2, 2], [0, 1]), ([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, 1][1, 3]Failed
explicit oracle 1[0, 0][0, 1]Failed
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[2][2]Passed
explicit oracle 7[4][4]Passed

SHA-256 / 14480777f497aec93e531873a1084b5a02d40380ffd91c8d9d651b0ffea9cddc

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, 4], [1, 3]), ([2, -6, 2], [0, 1]), ([1, -6, 1], [0]), ([11, 6, 12], [6]), ([1, -6, 2], [0]), ([1, -6, 3], [0]), ([1, -6, 4], [2]), ([1, -6, 5], [4])], [([2, -6, 6], [0, 3]), ([2, -6, 8], [1, 5]), ([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, 8], [1, 5]), ([2, -4, 2], [0, 1]), ([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, 10], [2, 7]), ([2, -4, 8], [2, 6]), ([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, 12], [3, 9]), ([2, -2, 2], [0, 1]), ([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][1, 3]Passed
explicit oracle 1[0, 1][0, 1]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[2][2]Passed
explicit oracle 7[4][4]Passed

SHA-256 / 92ef44b06310b28afe4106b66f0a86879efce9bb2806c2a9c0ce85bd594852e0

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.398135+00:00.

Case digest / 5aa5cb42dd50ac5741af48f3ca158b73cc3584f316025d42c2f30f6a4977bede