Question

3) ( [8 ) points] Traee the algorithm here to find ged ( (18,30) ). Show all steps, and state clearly the value that is returned procedure ged(a, b: nonacgative integers with

Answer 1

To find the gcd of two non-negative integers, such as gcd(18,30), use the Euclidean algorithm, which involves dividing the larger number by the smaller number and finding the remainder.

Step-by-step explanation:

To find the great common divisor (gcd) of two non-negative integers, such as gcd(18,30), we can use the Euclidean algorithm. Here are the steps:

1. Divide the larger number (30) by the smaller number (18), and find the remainder. In this case, 30 divided by 18 equals 1 with a remainder of 12.
2. Now, divide the previous divisor (18) by the remainder (12), and find the new remainder. In this case, 18 divided by 12 equals 1 with a remainder of 6.
3. Repeat the previous step until the remainder is 0. In this case, 12 divided by 6 equals 2 with a remainder of 0.
4. The final divisor (6) is the gcd of 18 and 30.

Therefore, the gcd of 18 and 30 is 6.