How to make an MDC algorithm with addition and subtraction?

Without comparison operations, it does not even have to stop the algorithm, so I assume that other arithmetic operations are prohibited, not prohibiting comparison operations. Okay?

To begin with, you usually use positive integers, so I'll consider this condition and if arguments outside of these conditions you should make the appropriate adaptations.

Second, if one could use Euclidean remainder calculation (usually the symbol % ) could be calculated by means of the following recursion: mdc(a,b)=( b=0 ? a : mdc(b,a%b) ) .

There is an algorithm for calculating the remainder of positive integer division that follows the a%b=( a<b ? a : (a-b)%b ) recursion. It can also be implemented without recursion as well.

resto( a , b )
    enquanto( a>=b )faça
        a <--- a-b
    retorna a

This means that you can calculate division remainder with only subtractions loop, not using the division operator. Thus mdc calculation can change the division by loop of subtractions.

With this, the recursion of mdc becomes mdc(a,b)=( b=0 ? a : mdc(b,resto(a,b)) ) . Refining the mdc algorithm, it looks like this.

mdc( a , b )
    enquanto( b>0 )faça
        enquanto( a>b )faça
            a <--- a-b
        b <-> a
    retorna( a )

Do you have any questions?