What Are Coprime Numbers? The GCD=1 Property Behind Interview Problems

You have the array [3, 5]. Pick any integers, multiply each element by one of them, add the results. Can you land exactly on 1?

Yes: 3 × 2 + 5 × (-1) = 1.

Now try [6, 10]. Multiply, scale, add however you like. You can never hit 1. The difference between these two arrays is one number: their GCD. Two integers are coprime when that GCD is 1, and a surprising range of coding problems hinge on whether or not it is.

If you read the rest of this post and nothing else, congrats: you just learned the whole topic.

The Definition Is Literally Just GCD = 1

Two integers a and b are coprime, also called relatively prime, when they share no common factor greater than 1. The entire definition is gcd(a, b) = 1. That's it. The whole field. Go home.

from math import gcd

def are_coprime(a: int, b: int) -> bool:
    return gcd(a, b) == 1

Some pairs to anchor the intuition:

a	b	gcd	Coprime?
8	15	1	Yes
14	15	1	Yes
12	8	4	No
100	37	1	Yes
100	25	25	No

Notice that (14, 15) are coprime even though neither is prime. 14 = 2 × 7. 15 = 3 × 5. No shared prime factors, so gcd = 1. Coprimality is about overlap in factorizations, not about being prime yourself. You don't have to be prime to be coprime. Very relatable.

You Already Know How to Check This

The Euclidean algorithm runs in O(log min(a, b)) and uses O(1) space. If you know how to compute a GCD, you already know how to check coprimality. No new tools required.

def gcd(a: int, b: int) -> int:
    while b:
        a, b = b, a % b
    return a

def are_coprime(a: int, b: int) -> bool:
    return gcd(a, b) == 1

For an entire array, fold GCDs together. This gives the GCD of all elements in O(n log V), where V is the maximum value:

from math import gcd
from functools import reduce

def array_gcd(nums: list[int]) -> int:
    return reduce(gcd, nums)

Checking coprimality before learning that gcd() exists.

Three Properties Interviewers Actually Test

Consecutive integers are always coprime

gcd(n, n+1) = 1, guaranteed. Any common divisor d divides both n and n+1, so it divides (n+1) - n = 1, which forces d = 1. This means you can skip the GCD call entirely whenever two numbers are adjacent integers. The universe hands you this one for free.

This comes up in sliding window bounds, two-pointer logic, and any time the problem implicitly hands you consecutive values. You do not need to compute anything. Just know it.

Modular inverse exists only when gcd(a, n) = 1

The modular inverse of a (mod n) is an integer x such that (a × x) % n = 1. It exists if and only if a and n are coprime. This matters in counting problems where you need to divide under a modulus. Dividing by q (mod MOD) means multiplying by q's inverse, and that inverse only exists when gcd(q, MOD) = 1.

Since MOD = 10^9 + 7 is prime, it is coprime with every integer from 1 to MOD-1. That is part of why counting problems use that specific modulus. It was not an accident. Somebody was thinking ahead.

def mod_inverse(a: int, mod: int) -> int:
    return pow(a, mod - 2, mod)  # Fermat's little theorem

Bezout's identity: ax + by = 1 has solutions when gcd(a, b) = 1

If gcd(a, b) = 1, integers x and y exist satisfying ax + by = 1. Back to the opening: 3 × 2 + 5 × (-1) = 1 is exactly this, with a = 3, b = 5, x = 2, y = -1. The extended Euclidean algorithm finds those x and y explicitly.

The identity extends inductively to any set of numbers: their linear combination can produce 1 if and only if their overall GCD is 1. That one fact powers the interview problem below.

Four Problems, Same Underlying Check

Four problems. One check. You will start seeing it everywhere once you know to look.

The "Good Array" Problem (LeetCode 1250)

You are given an array of positive integers. You can pick any subset, multiply each element by any integer, and sum the results. Can you produce exactly 1?

The answer is yes if and only if the GCD of the entire array equals 1. Bezout's identity proves the two-element case directly. The general case follows by induction: gcd(a, b, c) = gcd(gcd(a, b), c), so you reduce pairwise until you get the global GCD.

from math import gcd
from functools import reduce

def is_good_array(nums: list[int]) -> bool:
    return reduce(gcd, nums) == 1

Time: O(n log V). Space: O(1). A problem that looks combinatorial collapses into a single pass once you recognize the invariant.

Does Your Step Visit Every Position?

You have a circular array of size n. You start at index 0 and jump by step k each time. Will you visit every element exactly once before looping back?

Only when gcd(n, k) = 1.

If gcd(n, k) = g > 1, you visit exactly n/g distinct positions and cycle. With n = 6 and k = 2, gcd = 2, so you hit only {0, 2, 4} and miss the others entirely. n = 6, k = 1, gcd = 1: all six. The diagram below shows exactly why the cycle traps you.

from math import gcd

def visits_all_elements(n: int, k: int) -> bool:
    return gcd(n, k) == 1

This is not just circular array trivia. Open-addressing hash tables use probe sequences to find empty slots, and those sequences only guarantee a full traversal if the step is coprime with the table size. Some implementations choose a power-of-two table size specifically so any odd step is automatically coprime with it. Any question framed as "does this cycle have length n?" is asking the same thing.

Tree of Coprimes (LeetCode 1766)

You are given a tree where each node's value is between 1 and 50. For each node, find its nearest ancestor with a coprime value.

The naive approach scans all ancestors for each node. The key observation: values are bounded at 50. Precompute all coprime pairs for values 1..50 once, then during DFS maintain a stack of ancestors per value index.

from math import gcd

coprime_map: dict[int, list[int]] = {v: [] for v in range(1, 51)}
for i in range(1, 51):
    for j in range(1, 51):
        if gcd(i, j) == 1:
            coprime_map[i].append(j)

The per-node DFS cost drops from O(depth) with a full scan to O(50) with the precomputed map. This bounded-value trick shows up in many number theory tree problems and is worth keeping in your toolkit.

Splitting Arrays on Coprime Products (LeetCode 2584)

Find an index where the product of the left subarray and the product of the right subarray are coprime. Two products are coprime when they share no prime factor.

Computing actual products overflows immediately. Work with prime factorizations instead. Track which primes have appeared on the left side. When a prime that appeared on the left also appears on the right, the split is invalid. When no prime is shared across the split, the products are coprime.

Avoid computing the large numbers. Reason about their prime factors directly. This is a move that generalizes across a lot of number-theory-flavored problems.

These Two Conditions Are Not the Same

Modular arithmetic used in the Chinese Remainder Theorem requires pairwise coprimality. The "good array" question only requires that the overall GCD is 1. These are different conditions, and mixing them up in an interview will cost you the problem.

Consider (3, 5, 6). The overall GCD is 1, so you can form 1 as a linear combination. But gcd(3, 6) = 3, so 3 and 6 are not pairwise coprime. Two different things. Read the problem statement carefully.

from math import gcd

def all_pairs_coprime(nums: list[int]) -> bool:
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if gcd(nums[i], nums[j]) != 1:
                return False
    return True

Pairwise coprime is the stricter condition. If the problem says CRT applies, you need every pair. If it says "can you produce 1 as a linear combination," you just need the global GCD.

How to Spot Coprime Problems Before You Code

Coprimality problems share a shape. A question about whether certain integers can combine to produce 1. Whether a traversal covers all positions. Whether a modular operation is valid. When you see "shares no factor" or "reaches every position" or "divide under modulus," check whether gcd = 1 is the key invariant.

The bounded-value trick is worth keeping in your toolkit too. When problem constraints cap values at 50 or 100, precompute the full coprime graph once. Per-query GCD calls become O(1) lookups, and the precomputation is a small constant you can justify out loud without hesitation.

Explaining gcd = 1 reasoning out loud, under time pressure, while an interviewer is watching, is a different skill than understanding it on paper. If you want to practice that specifically, SpaceComplexity runs voice mock interviews with rubric-based feedback on number theory and algorithm problems like these.

Further Reading

• Coprime Integers on Wikipedia
• GeeksforGeeks: Check if Two Numbers Are Co-prime
• GeeksforGeeks: Euclidean Algorithms (Basic and Extended)
• LeetCode 1250: Check If It Is a Good Array
• LeetCode 1766: Tree of Coprimes