gcd(M,0,M).
gcd(M,N,D) :- N > 0, R is M mod N, gcd(N,R,D).