FA-14376 / Numerics / Open access

Linear congruence solutions: reduced residue · case 01

The exact linear congruence solutions result violates the stated contract at reduced residue.

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

ROOT CAUSE

The reduced residue step uses (bpow(a//g,-1,q))%q if q>1 else 0 instead of ((b//g)pow(a//g,-1,q))%q if q>1 else 0.

VERIFIED REPAIR

Use ((b//g)*pow(a//g,-1,q))%q if q>1 else 0 at the reduced residue step.

Unsuccessful approach: The partial repair (b//g)%q if q>1 else 0 still violates the reduced residue 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*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, 5], [2]), ([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, 8], [1, 5]), ([2, -6, 11], [8]), ([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, 10], [2, 7]), ([2, -5, 9], [2]), ([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, 12], [3, 9]), ([2, -4, 5], [3]), ([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, -4, 6], [1, 4]), ([2, -4, 11], [9]), ([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 fixture	Actual	Expected	Outcome
explicit oracle 0	`[0, 2]`	`[1, 3]`	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	`[2]`	`[2]`	Passed
explicit oracle 7	`[4]`	`[4]`	Passed

SHA-256 / 0520b3eb9677052a7a783ef760340b590028d4103620b72e7df81e8752f2c814

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)%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, 5], [2]), ([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, 8], [1, 5]), ([2, -6, 11], [8]), ([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, 10], [2, 7]), ([2, -5, 9], [2]), ([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, 12], [3, 9]), ([2, -4, 5], [3]), ([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, -4, 6], [1, 4]), ([2, -4, 11], [9]), ([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 fixture	Actual	Expected	Outcome
explicit oracle 0	`[1, 3]`	`[1, 3]`	Passed
explicit oracle 1	`[4]`	`[2]`	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 / c6cba10acc21b40d7096883e766280f8e24b48c0ff5b7b154b3a7a83c510106b

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

SHA-256 / 15fd6e62c6886b7804ed5f5ef1a0deea85335ed935c34ddba4959149f917d4c9

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

Case digest / ff6826efbf86e5bb38de0a88b99e688ceda7b3203f17357675d2cd6a46e5750b