GCD Tutorial

gcd_tutorial.md

GCD & LCM: Practice

• Review
• Problems
• Solutions

Review: Key Formulas and Theorems

Basic definitions

• gcd(a, b) is the largest integer dividing both a and b.
  • a % gcd(a, b) = 0 and b % gcd(a, b) = 0
  • gcd(a, b) <= a and gcd(a, b) <= b (Important and useful!)
  • Example: gcd(18, 24) = 6, gcd(10, 15) = 5
• lcm(a, b) is the smallest positive integer divisible by both a and b.
  • lcm(a, b) % a = 0 and lcm(a, b) % b = 0
  • lcm(a, b) >= a and lcm(a, b) >= b (Important and useful!)
  • Example: lcm(2, 3) = 6, lcm(18, 24) = 72, lcm(10, 15) = 30

Core identities

• gcd(a, 0) = a
• gcd(a, b) = gcd(b, a mod b) (Euclidean algorithm)
• gcd(a, b) * lcm(a, b) = a * b, so lcm(a, b) = a * b / gcd(a, b)
• gcd(k*a, k*b) = k * gcd(a, b) for any positive integer k
• gcd(a, a + b) = gcd(a, b)
• Extending to arrays: gcd(a, b, c) = gcd(gcd(a, b), c), and the same associativity holds for lcm.

Coprimality

• a and b are coprime if gcd(a, b) = 1.
  • Example: gcd(5, 7) = 1 and gcd(14, 15) = 1
• If a and b are coprime, lcm(a, b) = a * b.

Bezout's identity and linear Diophantine equations

For any integers a, b (not both zero), there exist integers x, y such that a*x + b*y = gcd(a, b). This is Bezout's identity, and gcd(a, b) is the smallest positive value that any integer combination a*x + b*y can produce. Any other reachable value is a multiple of gcd(a, b).

Step 1: finding one solution with the Extended Euclidean Algorithm

The idea is to run the normal Euclidean algorithm forward to get the sequence of divisions, then substitute back from the bottom up to express the gcd as a combination of the original a and b.

Worked example: find x, y such that 99*x + 78*y = gcd(99, 78).

Run the Euclidean algorithm forward:

99 = 1*78 + 21
78 = 3*21 + 15
21 = 1*15 + 6
15 = 2*6  + 3
6  = 2*3  + 0        -> gcd(99, 78) = 3

Now substitute back starting from the second-to-last line (the last remainder before hitting 0):

3  = 15 - 2*6
6  = 21 - 1*15               ->  3 = 15 - 2*(21 - 1*15)      = 3*15 - 2*21
15 = 78 - 3*21               ->  3 = 3*(78 - 3*21) - 2*21    = 3*78 - 11*21
21 = 99 - 1*78               ->  3 = 3*78 - 11*(99 - 1*78)   = 14*78 - 11*99

So -11*99 + 14*78 = 3, meaning x = -11, y = 14. Check: -11*99 = -1089, 14*78 = 1092, and -1089 + 1092 = 3. Correct.

In code this back-substitution is exactly what the recursive ext_gcd function does automatically (see Problem 5's solution).

Step 2: the general solution

Once one solution (x0, y0) to a*x + b*y = g is known (with g = gcd(a, b)), every integer solution has the form:

x = x0 + k * (b / g)
y = y0 - k * (a / g)        for any integer k

This works because shifting x by b/g and y by -a/g changes a*x + b*y by a*(b/g) - b*(a/g) = 0, so the total stays equal to g.

Step 3: solving a*x + b*y = c for a general target c

This equation has an integer solution if and only if gcd(a, b) divides c. If it does, scale the base solution:

scale = c / g
x0 = x0 * scale
y0 = y0 * scale

and then (x0, y0) satisfies a*x0 + b*y0 = c. Combine with Step 2 to get every solution, or to isolate the one with the smallest non-negative x:

step = b / g
x = x0 mod step        (in Python, % already gives a non-negative result when step > 0)
y = (c - a*x) / b

Worked example: solve 6*x + 9*y = 12.

• g = gcd(6, 9) = 3, and 3 divides 12, so a solution exists.
• A base solution to 6*x + 9*y = 3 is x0 = -1, y0 = 1 (check: 6*(-1) + 9*1 = 3).
• Scale by c / g = 12 / 3 = 4: x0 = -4, y0 = 4 (check: 6*(-4) + 9*4 = -24 + 36 = 12).
• step = b / g = 3, so the smallest non-negative x is -4 mod 3 = 2.
• Then y = (12 - 6*2) / 9 = 0. Final answer: x = 2, y = 0, and indeed 6*2 + 9*0 = 12. Worked example with no solution: 4*x + 6*y = 7. Here g = gcd(4, 6) = 2, and 2 does not divide 7, so no integer x, y can satisfy this equation, no matter how large or negative they are.

Useful structural facts for array problems

• The array [gcd(a_1), gcd(a_1,a_2), gcd(a_1,a_2,a_3), ...] (prefix gcd) is non-increasing and every value divides the previous one. Because each value at least halves whenever it changes, there are at most O(log(max(a_i))) distinct values in it.
• This log bound is the key trick behind many "gcd of subarrays" problems: you can track the small set of distinct gcd values ending at each index instead of recomputing from scratch.
• The largest divisor of n smaller than n is n / p, where p is the smallest prime factor of n.

Useful structural facts for array problems

• The array [gcd(a_1), gcd(a_1,a_2), gcd(a_1,a_2,a_3), ...] (prefix gcd) is non-increasing and every value divides the previous one. Because each value at least halves whenever it changes, there are at most O(log(max(a_i))) distinct values in it.
• This log bound is the key trick behind many "gcd of subarrays" problems: you can track the small set of distinct gcd values ending at each index instead of recomputing from scratch.
• The largest divisor of n smaller than n is n / p, where p is the smallest prime factor of n.

---

Problems

1. GCD & LCM Basics

Given two integers a and b, print gcd(a, b) and lcm(a, b). Don't use the built-in math.gcd and math.lcm functions.

Input: Two integers a, b (1 ≤ a, b ≤ 10^9) Output: Two integers: the gcd and the lcm.

---

2. GCD of an Array

Given an array of n integers, print the gcd of all of them.

Input: n, followed by n integers (1 ≤ a_i ≤ 10^9) Output: A single integer, the gcd of the array.

---

3. LCM of an Array

Given an array of n integers, print the lcm of all of them, modulo 10^9+7 (the true lcm may be huge).

Input: n, followed by n integers (1 ≤ a_i ≤ 10^6) Output: The lcm of the array, modulo 10^9+7.

---

4. Reduce the Fraction

Given a fraction p/q, print it in lowest terms. Example: 6/8 becomes 3/2, 15/10 becomes 3/2.

Input: Two integers p, q (1 ≤ p, q ≤ 10^18) Output: Two integers: the reduced numerator and denominator.

---

5. Two Runners Meeting Point

Two runners start at the same point on a circular track. Runner 1 completes a lap every a seconds, runner 2 every b seconds. Both start moving in the same direction at time 0. Find the earliest time t > 0 at which both runners are again exactly at the starting point simultaneously.

Input: Two integers a, b (1 ≤ a, b ≤ 10^9) Output: The earliest such time t.

---

6. Removable Element

Given an array of n integers, for each index i determine whether removing a_i changes the gcd of the remaining n-1 elements (compared to the gcd of the full array). Print "YES" if the gcd changes, "NO" otherwise, for each index.

Input: n, followed by n integers (2 ≤ n ≤ 3*10^5, 1 ≤ a_i ≤ 10^9) Output: n lines, each "YES" or "NO".

---

7. Maximize GCD with Fixed Sum

Given n, split it into two positive integers a + b = n such that gcd(a, b) is as large as possible. Print that maximum gcd.

Input: One integer n (2 ≤ n ≤ 10^12) Output: The maximum possible gcd(a, b).

---

8. Maximum Pairwise GCD

Given an array of n distinct integers, find the maximum value of gcd(a_i, a_j) over all pairs i ≠ j.

Input: n, followed by n integers (2 ≤ n ≤ 10^6, 1 ≤ a_i ≤ 10^6) Output: The maximum pairwise gcd.

---

9. Extended GCD Equation

Given integers a and b, find any integers x, y such that a*x + b*y = gcd(a, b).

Input: Two integers a, b (1 ≤ a, b ≤ 10^9) Output: Three integers: g, x, y where g = gcd(a, b) and ax + by = g.

---

10. Linear Diophantine Solver

Given integers a, b, c, determine whether a*x + b*y = c has an integer solution. If it does, print the solution with the smallest non-negative x. If no solution exists, print -1.

Input: Three integers a, b, c (1 ≤ a, b ≤ 10^9, 0 ≤ c ≤ 10^9) Output: "x y" for the smallest non-negative x, or -1 if no solution exists.

---

Solutions (Python)

1. GCD & LCM Basics

import math

def solve():
    a, b = map(int, input().split())
    g = math.gcd(a, b)
    l = a * b // g
    print(g, l)

solve()

2. GCD of an Array

import math

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    # Fold gcd across the array using the associativity property
    result = arr[0]
    for x in arr[1:]:
        result = math.gcd(result, x)
    print(result)

solve()

3. LCM of an Array

import math

MOD = 10**9 + 7

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    # lcm accumulates the same way gcd does, one element at a time
    result = 1
    for x in arr:
        g = math.gcd(result, x)
        result = (result // g) * x % MOD
    print(result)

solve()

4. Reduce the Fraction

import math

def solve():
    p, q = map(int, input().split())
    g = math.gcd(p, q)
    print(p // g, q // g)

solve()

5. Two Runners Meeting Point

import math

def solve():
    a, b = map(int, input().split())
    # Both runners return to the start at multiples of their own lap time,
    # so the first shared moment is the lcm of the two lap times
    g = math.gcd(a, b)
    print(a * b // g)

solve()

6. Removable Element

import math

def solve():
    n = int(input())
    arr = list(map(int, input().split()))

    # Prefix gcd: prefix[i] = gcd(arr[0..i-1])
    # Suffix gcd: suffix[i] = gcd(arr[i..n-1])
    prefix = [0] * (n + 1)
    suffix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = math.gcd(prefix[i], arr[i])
    for i in range(n - 1, -1, -1):
        suffix[i] = math.gcd(suffix[i + 1], arr[i])

    full_gcd = prefix[n]
    out = []
    for i in range(n):
        # gcd of everything except index i
        without_i = math.gcd(prefix[i], suffix[i + 1])
        out.append("YES" if without_i != full_gcd else "NO")

    print("\n".join(out))

solve()

7. Maximize GCD with Fixed Sum

def solve():
    n = int(input())
    # The best split uses the smallest prime factor p of n:
    # a = n - n/p, b = n/p, giving gcd(a,b) = n/p
    if n % 2 == 0:
        print(n // 2)
        return

    p = 3
    spf = n
    while p * p <= n:
        if n % p == 0:
            spf = p
            break
        p += 2

    print(n // spf)

solve()

8. Maximum Pairwise GCD

def solve():
    n = int(input())
    arr = list(map(int, input().split()))
    m = max(arr)
    present = [False] * (m + 1)
    for x in arr:
        present[x] = True

    # For each candidate gcd value g from high to low, count multiples of g
    # present in the array. If two or more exist, g is achievable.
    answer = 1
    for g in range(m, 0, -1):
        count = 0
        multiple = g
        while multiple <= m:
            if present[multiple]:
                count += 1
                if count >= 2:
                    break
            multiple += g
        if count >= 2:
            answer = g
            break

    print(answer)

solve()

9. Extended GCD Equation

def ext_gcd(a, b):
    # Returns (g, x, y) such that a*x + b*y = g = gcd(a, b)
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    x, y = y1, x1 - (a // b) * y1
    return g, x, y

def solve():
    a, b = map(int, input().split())
    g, x, y = ext_gcd(a, b)
    print(g, x, y)

solve()

10. Linear Diophantine Solver

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    g, x1, y1 = ext_gcd(b, a % b)
    x, y = y1, x1 - (a // b) * y1
    return g, x, y

def solve():
    a, b, c = map(int, input().split())
    g, x0, y0 = ext_gcd(a, b)

    if c % g != 0:
        print(-1)
        return

    # Scale the base solution to match c
    scale = c // g
    x0 *= scale
    y0 *= scale

    # General solution: x = x0 + k*(b/g) for any integer k
    # Python's % on a positive divisor already gives the smallest non-negative value
    step = b // g
    x = x0 % step
    y = (c - a * x) // b

    print(x, y)

solve()