TheAlgorithms/Python · error · ValueError

a and n must be coprime (gcd(a, n) = 1)

Error message

a and n must be coprime (gcd(a, n) = 1)

What it means

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.

Source

Thrown at maths/modular_division.py:36

    This find x = b*a^(-1) mod n
    Uses ExtendedEuclid to find the inverse of a

    >>> modular_division(4,8,5)
    2

    >>> modular_division(3,8,5)
    1

    >>> modular_division(4, 11, 5)
    4

    """
    if n <= 1:
        raise ValueError("Modulus n must be greater than 1")
    if a <= 0:
        raise ValueError("Divisor a must be a positive integer")
    if greatest_common_divisor(a, n) != 1:
        raise ValueError("a and n must be coprime (gcd(a, n) = 1)")

    (_d, _t, s) = extended_gcd(n, a)  # Implemented below
    x = (b * s) % n
    return x


def invert_modulo(a: int, n: int) -> int:
    """
    This function find the inverses of a i.e., a^(-1)

    >>> invert_modulo(2, 5)
    3

    >>> invert_modulo(8,7)
    1

    """
    (b, _x) = extended_euclid(a, n)  # Implemented below

View on GitHub (pinned to f5988cc097)

Solutions

1. Pick a coprime to n — e.g. any a coprime to a prime n works (a in 1..n-1).
2. Check coprimality first: from math import gcd; if gcd(a, n) != 1: choose a different divisor or modulus.
3. If your protocol demands this division, switch to a prime modulus so every non-zero a is invertible.

Example fix

# before
modular_division(6, 8, 4)  # gcd(6, 4) = 2

# after
from math import gcd
assert gcd(6, 5) == 1
modular_division(6, 8, 5)

from math import gcd
if gcd(a, n) != 1:
    raise ValueError(f'{a} has no inverse mod {n}: gcd is {gcd(a, n)}')

When it happens

Trigger: 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.

Common situations: 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.

Related errors

• Modulus n must be greater than 1
• Divisor a must be a positive integer
• Input must be a positive integer
• mod inverse of {a!r} and {m!r} does not exist
• Input must be an integer

AI-assisted analysis of TheAlgorithms/Python@f5988cc097 (2026-08-14). Data as JSON: /api/errors/c46e2a4408a5b7ee. Report an issue: GitHub.