How to generate two integers with a predefined greatest common divisor

When to use this: 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.

What you'll achieve: 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 LearningLemur:

Before you begin

Requirements:

• Basic knowledge of how to create a LearningLemur 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 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 LearningLemur
• Common Patterns and Best Practices
• Glossary of Commands