In an earlier lesson on adding fractions in Prolog, we wrote rules to compute $N_1/D_1 + N_2/D_2$. But if you add $1/6 + 1/6$, the answer is $2/6$ — it is not simplified to lowest terms ($1/3$)!

To reduce any fraction $N/D$ to lowest terms, we must divide both the numerator $N$ and the denominator $D$ by their Greatest Common Divisor (GCD): $$G = \gcd(N, D) \implies N_{\text{reduced}} = \frac{N}{G}, \quad D_{\text{reduced}} = \frac{D}{G}$$ Over 2,300 years ago, the Greek mathematician Euclid of Alexandria described an algorithm in his Elements (Book VII, Proposition 2) based on a simple observation: If a number divides both $X$ and $Y$, it must also divide their remainder $(X \pmod Y)$.

Euclid's Algorithm:

1. Base Case: $\gcd(X, 0) = X$ (any number divides $0$).
2. Recursive Step: If $Y > 0$, then $\gcd(X, Y) = \gcd(Y, X \pmod Y)$.

In Prolog, this recursive definition translates into two lines of pure, elegant logic!

• Integer Division: In Prolog, // performs integer division (e.g., 24 // 12 is 2), while mod gives the integer remainder (e.g., 24 mod 7 is 3).
• Termination: Because the remainder $R = X \pmod Y$ is always strictly less than $Y$, the numbers get smaller with every recursive step until the remainder reaches $0$.
• Coprime Numbers: Two integers $A$ and $B$ are called coprime (or relatively prime) if $\gcd(A, B) = 1$.