Lesson goal: Contest Number Theory: GCD and LCM (AMC 10A Problem 7)

Previous: Contest Diophantine: Repeating Decimals | Home | Next: Contest Sequences: Arithmetic and Geometric

In the 2022 AMC 10A competition, Problem #7 tests prime factor constraints through greatest common divisors and least common multiples:

Contest Problem Statement:
"The least common multiple of a positive integer $n$ and $18$ is $180$, and the greatest common divisor of $n$ and $45$ is $15$. What is the sum of the digits of $n$?"

Prime Factor Analysis

Let's look at the prime factorizations of the given numbers:
  • $18 = 2^1 \times 3^2$
  • $180 = 2^2 \times 3^2 \times 5^1$
  • $45 = 3^2 \times 5^1$
  • $15 = 3^1 \times 5^1$
Now consider what each condition tells us about the prime factors of $n$:
  1. $\text{lcm}(n, 18) = 180$: The power of $2$ in $180$ is $2^2$. Since $18$ only contributes $2^1$, $n$ must supply $2^2 = 4$. Furthermore, $180$ has a factor of $5$, which $18$ does not have, so $5$ must also divide $n$.
  2. $\gcd(n, 45) = 15$: The greatest common divisor has $3^1$, but $45$ has $3^2$. This means $n$ cannot have more than one factor of $3$ (otherwise $\gcd$ would be divisible by $9$). Therefore, the power of $3$ in $n$ must be exactly $3^1$!
Combining these factors:
$$n = 2^2 \times 3^1 \times 5^1 = 4 \times 3 \times 5 = 60$$
Let's double-check:
  • $\text{lcm}(60, 18) = \frac{60 \times 18}{\gcd(60, 18)} = \frac{1080}{6} = 180$ — correct!
  • $\gcd(60, 45) = 15$ — correct!
The sum of the digits of $n$ is $6 + 0 = 6$.

Solving Number Theory Relations in Prolog

In Prolog, we can express the Euclidean algorithm for GCD and the relation $\text{lcm}(a, b) = (a \times b) / \gcd(a, b)$ directly as rules. Then Prolog searches for the positive integer $n$ that simultaneously satisfies both relations!
gcd(A, B, G), lcm(A, B, L) :- gcd(A, 0, A) :- A > 0.
gcd(A, B, G) :- B > 0, R is A mod B, gcd(B, R, G).
lcm(A, B, L) :- gcd(A, B, G), % LCM formula LCM(A, B) = (A * B) // GCD(A, B): Replace ???? with G L is (A * B) // ???? .
Move the mouse over a dotted box for more information.

By declaring these fundamental number-theoretic properties, Prolog can search and verify solutions across any range of integers.

Now you try. Replace ???? with G and click Run to find = 60$ and digit sum $. Then check Example 1 to test GCD and LCM queries directly in the interpreter!

Type your code here:


See your results here: