First we must know that the problem of computing the gcd is well-defined. This means we need to know enough algebra to know that every integer has a unique factorization into a product of powers of primes and that from the representations for m and n the gcd of m and n can be extracted. Then we must know that the algorithm is correct. Now divisibility properties of integers imply that any integer x which divides m and n must also divide r. So the algorithm is well-defined and correct.
Efficiency is also diifficult to measure.
For Euclid's algorithm given above a. Give an example of values m,n for which this time is achieved.