{"record":{"id":"79ae993c80313c47","repo":"TheAlgorithms/C-Sharp","slug":"the-gcd-of-n-i-listofns-i-and-n-j-listofns-j-equals-gcd-and","errorCode":null,"errorMessage":"The GCD of n_{i} = {listOfNs[i]} and n_{j} = {listOfNs[j]} equals {gcd} and thus these values aren't coprime.","messagePattern":"The GCD of n_(.+?) = (.+?) and n_(.+?) = (.+?) equals (.+?) and thus these values aren't coprime\\.","errorType":"exception","errorClass":"ArgumentException","httpStatus":null,"severity":"error","filePath":"Algorithms/ModularArithmetic/ChineseRemainderTheorem.cs","lineNumber":145,"sourceCode":"        if (listOfNs.Any(x => x <= 1))\n        {\n            throw new ArgumentException($\"The value {listOfNs.First(x => x <= 1)} for some n_i is smaller than or equal to 1.\");\n        }\n\n        if (listOfAs.Any(x => x < 0))\n        {\n            throw new ArgumentException($\"The value {listOfAs.First(x => x < 0)} for some a_i is smaller than 0.\");\n        }\n\n        // Check if all pairs of (n_i, n_j) are coprime:\n        for (var i = 0; i < listOfNs.Count; i++)\n        {\n            for (var j = i + 1; j < listOfNs.Count; j++)\n            {\n                long gcd;\n                if ((gcd = ExtendedEuclideanAlgorithm.Compute(listOfNs[i], listOfNs[j]).Gcd) != 1L)\n                {\n                    throw new ArgumentException($\"The GCD of n_{i} = {listOfNs[i]} and n_{j} = {listOfNs[j]} equals {gcd} and thus these values aren't coprime.\");\n                }\n            }\n        }\n    }\n\n    /// <summary>\n    /// Checks the requirements for the algorithm and throws an ArgumentException if they are not being met.\n    /// </summary>\n    /// <param name=\"listOfAs\">An ordered list of a_0, a_1, ..., a_k.</param>\n    /// <param name=\"listOfNs\">An ordered list of n_0, n_1, ..., n_k.</param>\n    /// <exception cref=\"ArgumentException\">If any of the requirements is not fulfilled.</exception>\n    private static void CheckRequirements(List<BigInteger> listOfAs, List<BigInteger> listOfNs)\n    {\n        if (listOfAs == null || listOfNs == null || listOfAs.Count != listOfNs.Count)\n        {\n            throw new ArgumentException(\"The parameters 'listOfAs' and 'listOfNs' must not be null and have to be of equal length!\");\n        }\n","sourceCodeStart":127,"sourceCodeEnd":163,"githubUrl":"https://github.com/TheAlgorithms/C-Sharp/blob/96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c/Algorithms/ModularArithmetic/ChineseRemainderTheorem.cs#L127-L163","documentation":"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.","triggerScenarios":"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.","commonSituations":"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).","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."],"exampleFix":"// before\nChineseRemainderTheorem.Compute(new List<long> { 2, 2 }, new List<long> { 3, 6 }); // gcd(3,6)=3\n\n// after\nChineseRemainderTheorem.Compute(new List<long> { 2, 2 }, new List<long> { 3, 5 }); // pairwise coprime","handlingStrategy":"validation","validationCode":"for (int i = 0; i < listOfNs.Count; i++)\n    for (int j = i + 1; j < listOfNs.Count; j++)\n        if (Gcd(listOfNs[i], listOfNs[j]) != 1)\n            throw new ArgumentException($\"Moduli {listOfNs[i]} and {listOfNs[j]} are not coprime.\");\nChineseRemainderTheorem.Compute(listOfAs, listOfNs);","typeGuard":"static bool ArePairwiseCoprime(List<long> ns) =>\n    ns.SelectMany((n, i) => ns.Skip(i + 1), (n, m) => Gcd(n, m)).All(g => g == 1);","tryCatchPattern":"try\n{\n    var result = ChineseRemainderTheorem.Compute(listOfAs, listOfNs);\n}\ncatch (ArgumentException ex) when (ex.Message.Contains(\"aren't coprime\"))\n{\n    logger.LogError(\"CRT moduli not pairwise coprime: {Msg}\", ex.Message);\n    throw;\n}","preventionTips":["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."],"tags":["math","modular-arithmetic","invalid-argument-value","csharp"],"backgroundTag":"invalid-argument-value","analyzedSha":"96e2905cab7bc6b33ac0a34ee5bb82ddccbcbb6c","analyzedAt":"2026-09-13T17:04:01.438Z","contentChangedAt":"2026-09-13T17:04:01.438Z","schemaVersion":2},"datasetVersion":"2026-09-16T04:17:20.429Z"}