Euclidean Algorithm for GCD of Two Numbers in Java

In this article, you are about to learn the implementation of the Euclidean Algorithm for finding the GCD of two given numbers in Java.

The Euclidean Algorithm for finding the greatest common divisor has been in use from ancient times. It is named after the ancient Greek mathematician Euclid, who included the description of this algorithm in his book The Elements.

The Euclidean Algorithm to find GCD depends on the following lemma.
Lemma 1: Let a = b*q + r, where a, b, q and r are integers. Then, GCD(a,b) = GCD(b,r).

There is no proof for this lemma in this article, but you can verify it with an example.

Let’s take an example of two numbers, say, 414 and 662 and perform the Euclidean Algorithm on them.

We all know about Euclid’s Division Lemma. That is, a = b*q + r, where 0≤r<b. Using it, we will perform successive divisions on 414 and 662.

a: The greatest number among the two numbers. In this case, 662.
b: The smallest number. Here, it is 414.

Writing in the form of Euclid’s Division Lemma,

662 = 414*1 + 248

We will assign b to a and r to b in every step of the successive divisions until r = 0. Along with that, we will apply Lemma 1 in every step.

662 = 414*1 + 248  ; GCD(662, 414) = GCD(414, 248)
414 = 248*1 + 166  ; GCD(414, 248) = GCD(248, 166)
248 = 166*1 + 82  ; GCD(248, 166) = GCD(166, 82)
166 = 82*2 + 2  ; GCD(166, 82) = GCD(82, 2)
82 = 2*41 + 0  ; GCD(82, 2) = GCD(2, 0)

From the above steps we can infer that,
GCD(662, 414) = GCD(414, 248) = GCD(248, 166) = GCD(166, 82) = GCD(82, 2) = GCD(2, 0)

That implies, GCD(662, 414) = GCD(2, 0). Since GCD of a number and 0 is the number itself, GCD(662, 414) = 2.

Successive divisions using Euclid’s Division Lemma and applying Lemma 1 complete the Euclidean Algorithm for GCD of two numbers.

Now it’s time to write some code!

Algorithm:
Step 1: Start
Step 2: Scan two numbers a and b
Step 3: Assign r = a mod b
Step 4: Let a = b and b =r
Step 5: Repeat steps 3 & 4 until r = 0
Step 6: Print b as GCD
Step 7: Stop

Code:

Below is our Java code for the Euclidean Algorithm to find the GCD of Two Numbers:

import java.util.*;
class GCD{
  public static void main(String args[]){
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter the first number: ");
    int a = sc.nextInt();
    System.out.println("Enter the second number: ");
    int b = sc.nextInt();
    System.out.println("The GCD of "+a+" and "+b+" is: "+EuclideanAlgo(a,b));
  }
  static int EuclideanAlgo(int a, int b){
    int r = 0;
    if(b==0) return a;
    else{
      while(a%b > 0){
      r = a%b;
      a = b;
      b = r;
      }
    }
    return b;
  }
}

Output: