The Euclidean algorithm for the GCD (greatest common divisor) of two positive in

ID: 3550851 • Letter: T

Question

The Euclidean algorithm for the GCD (greatest common divisor) of two

positive integers is the world's oldest surviving non-trivial algorithm. It

has many theoretical and practical applications. For example, it is used in

the public key encryption system that is used to secure electronic commerce.

It has a short recursive implementation based on the following two facts.

gcd(a; b) = {a if b = 0;

{gcd(b; a%b) otherwise.

Use the above fact to write a recursive method in Java that computes and

returns the gcd of two positive integers.

int gcd(int m,int n) { if(n==0) return m; else if(n>m) return gcd(n,m); else return gcd(n,m%n); }

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.