GCD and Coprime Numbers

Problem A number-theory problem built around GCD and coprimality: given two numbers, determine whether they are coprime (GCD == 1), or count how many numbers in a range are coprime to a given number.

Input / Output

• Input: two integers a and b for the coprimality check; an integer n (and optionally a range) for the counting variant
• Output: boolean for the coprimality check; an integer count for the counting variant

Constraints

• Inputs large enough that trial-division factorisation is too slow — expect an O(log(min(a,b))) GCD
• Values may be up to 10^9; the counting variant may span a range of up to 10^6
• Define the edge case: gcd(a, 0) = a, and 1 is coprime to everything

Example

• a = 8, b = 15 → gcd(8,15) = 1 → coprime
• a = 12, b = 18 → gcd = 6 → not coprime
• Counting variant: numbers in [1, 9] coprime to 9 → {1,2,4,5,7,8} → 6, which is φ(9)