Question: find gcd389298 36685 with the help of the euclids algorithm...
Question details

Find gcd(389298, 36685) with the help of the Euclid’s algorithm.

Estimate approximately how many times faster it will be to find gcd(389298, 36685) with the help of the Euclid’s algorithm compared with the algorithm based on checking consecutive integers from min{m, n} down to gcd(m, n) (see the algorithm #2 from the handout). You are allowed to count only the number of modulus divisions of the largest integer by different divisors.