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:
Base Case: $\gcd(X, 0) = X$ (any number divides $0$).
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!
gcd(X, 0, X). gcd(X, Y, G) :- Y > 0, R is X mod Y, gcd(Y, R, G). reduce(N, D, Nred, Dred) :- gcd(N, D, G), Nred is N // G, Dred is D // G. goal: reduce(24, 36, N, D).
Move the mouse over a dotted box for more information.
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$.
Now you try. Change the goal to reduce reduce(45, 60, N, D) and hit Run.
Type your code here:
See your results here:
The code has ???? where numerator and denominator are divided by GCD G. Replace ???? with G, then click Run to let Prolog reduce 4/36$ to /3 ($\gcd(24, 36) = 12$) and reduce $24/36$ to $2/3$!
Try changing the goal to other fractions: