How to generate two integers with a predefined greatest common divisor

Use this method when you want students to compute the greatest common divisor (GCD) of two integers and ensure that the result is a specific controlled value.

Following this guide, you will generate two integers whose GCD is guaranteed to match a predefined target value, allowing you to control the correct answer while keeping the numbers random.

See it in action: Watch how this logic is implemented inside Nubric:

Before you begin

Requirements

• Basic knowledge of how to create a Nubric question.
• Familiarity with adding an algorithm to generate random variables.

Steps

Select a target GCD.

target_gcd = random(2,10)

This determines the exact GCD that students must compute.

Generate coprime base integers.

repeat
  m = random(2,10)
  n = random([2,10]/[m])
until gcd(m, n) == 1

This loop guarantees that m and n are coprime, meaning their GCD is 1.

Scale both integers.

x = m * target_gcd
y = n * target_gcd

By multiplying both numbers by target_gcd, the resulting integers will have exactly that GCD.

Define the solution.

solution = target_gcd

This value can be used directly for grading.

Verify it worked

• Preview the question multiple times.
• Compute the GCD of the generated values manually.
• Confirm the result always matches target_gcd
• Ensure no unexpected shared factors appear.

Full algorithm (copy-paste version)

Use the complete version below if you want to copy the logic directly into your question algorithm:

# Randomly select target GCD between 2 and 10
target_gcd = random(2,10)

# Select two random integers that are coprime (so gcd=1)
repeat
  m = random(2,10)
  n = random([2,10]/[m])
until gcd(m, n) == 1

# Generate integers ensuring exact GCD is target_gcd
x = m * target_gcd
y = n * target_gcd

solution = target_gcd

Options and variations

• If you want larger numbers, you can increase the random interval for m and n, but test performance to avoid long regeneration loops.
• If you want to avoid trivial cases, you can increase the minimum value of target_gcd (e.g., random(3,15)).
• If you want students to factor instead of compute GCD directly, you can use larger intervals to encourage prime factorization strategies.

Common errors

Generated numbers are not coprime in the repeat loop.
Ensure the condition gcd(m, n) == 1 is correctly written.

Unexpected GCD value.
Check that x and y are both multiplied by target_gcd

Infinite regeneration loop.
Broaden the interval for m and n if the constraint is too restrictive

Related

• Understanding Advanced Logic in Nubric
• Common Patterns and Best Practices
• Glossary of Commands