{"record":{"id":"c46e2a4408a5b7ee","repo":"TheAlgorithms/Python","slug":"a-and-n-must-be-coprime-gcd-a-n-1","errorCode":null,"errorMessage":"a and n must be coprime (gcd(a, n) = 1)","messagePattern":"a and n must be coprime \\(gcd\\(a, n\\) = 1\\)","errorType":"exception","errorClass":"ValueError","httpStatus":null,"severity":"error","filePath":"maths/modular_division.py","lineNumber":36,"sourceCode":"    This find x = b*a^(-1) mod n\n    Uses ExtendedEuclid to find the inverse of a\n\n    >>> modular_division(4,8,5)\n    2\n\n    >>> modular_division(3,8,5)\n    1\n\n    >>> modular_division(4, 11, 5)\n    4\n\n    \"\"\"\n    if n <= 1:\n        raise ValueError(\"Modulus n must be greater than 1\")\n    if a <= 0:\n        raise ValueError(\"Divisor a must be a positive integer\")\n    if greatest_common_divisor(a, n) != 1:\n        raise ValueError(\"a and n must be coprime (gcd(a, n) = 1)\")\n\n    (_d, _t, s) = extended_gcd(n, a)  # Implemented below\n    x = (b * s) % n\n    return x\n\n\ndef invert_modulo(a: int, n: int) -> int:\n    \"\"\"\n    This function find the inverses of a i.e., a^(-1)\n\n    >>> invert_modulo(2, 5)\n    3\n\n    >>> invert_modulo(8,7)\n    1\n\n    \"\"\"\n    (b, _x) = extended_euclid(a, n)  # Implemented below","sourceCodeStart":18,"sourceCodeEnd":54,"githubUrl":"https://github.com/TheAlgorithms/Python/blob/f5988cc09713315817df6a7e327e258013a94440/maths/modular_division.py#L18-L54","documentation":"Raised by modular_division() in maths/modular_division.py when gcd(a, n) != 1. Modular division b/a mod n is defined as b * a^(-1) mod n, and the inverse of a exists only when a and n share no common factor; when they are not coprime the equation has no unique solution and the function refuses to proceed.","triggerScenarios":"modular_division(10, 8, 5) with gcd(10,5)=5, modular_division(6, 8, 4) with gcd(6,4)=2 — any (a, n) sharing a prime factor.","commonSituations":"Using a composite modulus like 12 with a divisor like 8, or choosing a=2 with an even modulus; also results of reducing a mod n into a value that shares a factor with n.","solutions":["Pick a coprime to n — e.g. any a coprime to a prime n works (a in 1..n-1).","Check coprimality first: from math import gcd; if gcd(a, n) != 1: choose a different divisor or modulus.","If your protocol demands this division, switch to a prime modulus so every non-zero a is invertible."],"exampleFix":"# before\nmodular_division(6, 8, 4)  # gcd(6, 4) = 2\n\n# after\nfrom math import gcd\nassert gcd(6, 5) == 1\nmodular_division(6, 8, 5)","handlingStrategy":"validation","validationCode":"from math import gcd\nif gcd(a, n) != 1:\n    raise ValueError(f'{a} has no inverse mod {n}: gcd is {gcd(a, n)}')","typeGuard":null,"tryCatchPattern":null,"preventionTips":["Prefer prime moduli so every non-zero a is invertible.","Check gcd before dividing in modular arithmetic code paths."],"tags":["math","number-theory","valueerror","modular-arithmetic","coprimality"],"backgroundTag":null,"analyzedSha":"f5988cc09713315817df6a7e327e258013a94440","analyzedAt":"2026-08-14T17:30:07.041Z","schemaVersion":2},"datasetVersion":"2026-08-15T17:31:12.345Z"}