TheAlgorithms/C-Sharp · error · ArgumentException

The GCD of n_ = and n_ = equals and thus these values…

Error message

The GCD of n_{i} = {listOfNs[i]} and n_{j} = {listOfNs[j]} equals {gcd} and thus these values aren't coprime.

What it means

The Chinese Remainder Theorem only guarantees a unique solution when all moduli are pairwise coprime. CheckRequirements computes the GCD of every pair (n_i, n_j) via ExtendedEuclideanAlgorithm and throws ArgumentException when any pair's GCD is not 1, including the offending values in the message.

Solutions

Choose moduli that are pairwise coprime (e.g. distinct primes or prime powers).
Pre-check all pairs with a GCD function before calling Compute and report the bad pair.
If the moduli cannot change, decompose the system into prime-power sub-moduli or use a generalized CRT solver that handles non-coprime moduli.

Example fix

// before
ChineseRemainderTheorem.Compute(new List<long> { 2, 2 }, new List<long> { 3, 6 }); // gcd(3,6)=3

// after
ChineseRemainderTheorem.Compute(new List<long> { 2, 2 }, new List<long> { 3, 5 }); // pairwise coprime

Defensive patterns

Strategy: validation

Validate before calling

for (int i = 0; i < listOfNs.Count; i++)
    for (int j = i + 1; j < listOfNs.Count; j++)
        if (Gcd(listOfNs[i], listOfNs[j]) != 1)
            throw new ArgumentException($"Moduli {listOfNs[i]} and {listOfNs[j]} are not coprime.");
ChineseRemainderTheorem.Compute(listOfAs, listOfNs);

Type guard

static bool ArePairwiseCoprime(List<long> ns) =>
    ns.SelectMany((n, i) => ns.Skip(i + 1), (n, m) => Gcd(n, m)).All(g => g == 1);

Try / catch

try
{
    var result = ChineseRemainderTheorem.Compute(listOfAs, listOfNs);
}
catch (ArgumentException ex) when (ex.Message.Contains("aren't coprime"))
{
    logger.LogError("CRT moduli not pairwise coprime: {Msg}", ex.Message);
    throw;
}

Prevention

Pick moduli as distinct primes (or prime powers) to guarantee coprimality.
Run a pairwise GCD check during input validation, before calling Compute.
Reject duplicate moduli, since gcd(n, n) = n != 1 for n > 1.

When it happens

Trigger: Calling Compute with moduli that share a common factor, e.g. n = {3, 6, 5} where gcd(3,6)=3, or {4, 8, 9} where gcd(4,8)=4.

Common situations: Hand-picked moduli that look unrelated but share a factor; generating moduli from products of primes without checking pairwise coprimality; repeated moduli (gcd(n,n)=n).

Understand the failure class

Background: "Must be a positive integer", "Invalid value", "Unsupported": the invalid-argument-value error family, when a library rejects the value you pass — this error's family across 35 libraries.

Related errors

AI-assisted analysis of TheAlgorithms/C-Sharp@96e2905cab (2026-09-13). Data as JSON: /api/errors/79ae993c80313c47. Report an issue: GitHub.

Appendix: source

Thrown at Algorithms/ModularArithmetic/ChineseRemainderTheorem.cs:145

        if (listOfNs.Any(x => x <= 1))
        {
            throw new ArgumentException($"The value {listOfNs.First(x => x <= 1)} for some n_i is smaller than or equal to 1.");
        }

        if (listOfAs.Any(x => x < 0))
        {
            throw new ArgumentException($"The value {listOfAs.First(x => x < 0)} for some a_i is smaller than 0.");
        }

        // Check if all pairs of (n_i, n_j) are coprime:
        for (var i = 0; i < listOfNs.Count; i++)
        {
            for (var j = i + 1; j < listOfNs.Count; j++)
            {
                long gcd;
                if ((gcd = ExtendedEuclideanAlgorithm.Compute(listOfNs[i], listOfNs[j]).Gcd) != 1L)
                {
                    throw new ArgumentException($"The GCD of n_{i} = {listOfNs[i]} and n_{j} = {listOfNs[j]} equals {gcd} and thus these values aren't coprime.");
                }
            }
        }
    }

    /// <summary>
    /// Checks the requirements for the algorithm and throws an ArgumentException if they are not being met.
    /// </summary>
    /// <param name="listOfAs">An ordered list of a_0, a_1, ..., a_k.</param>
    /// <param name="listOfNs">An ordered list of n_0, n_1, ..., n_k.</param>
    /// <exception cref="ArgumentException">If any of the requirements is not fulfilled.</exception>
    private static void CheckRequirements(List<BigInteger> listOfAs, List<BigInteger> listOfNs)
    {
        if (listOfAs == null || listOfNs == null || listOfAs.Count != listOfNs.Count)
        {
            throw new ArgumentException("The parameters 'listOfAs' and 'listOfNs' must not be null and have to be of equal length!");
        }

View on GitHub (pinned to 96e2905cab)