Java Program to find GCD , LCM of two numbers

Greatest common divisor (gcd)

---

The greatest common divisor (gcd)( also known as the greatest common factor (gcf), or highest common factor(hcf)) of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.
For example, the GCD of 8 and 12 is 4.


Euclid's algorithm 

Euclid's algorithm uses a division algorithm such as long division in combination with the observation that the gcd of two numbers also divides their difference.
Formally the algorithm can be described as,

  gcd(a,0) = a (1)
gcd(a,b) = gcd(b, a mod b) (2)
Example application of these equaition:

gcd(42,35) = gcd (42, 7)           .. applying (2)
                = gcd (7,0)              .. again (2)
gcd(42,35) = 7                          .. applying (1)

Least common multiple (lcm)

---

The least common multiple (also called as the lowest common multiple or smallest common multiple) of two integers a and b,is the smallest positive integer that is divisible by both a and b.

lcm(a,b) = a*b / gcd(a,b)         (3)

Example application of these equaition:

lcm (21,28) = 21* 28/ gcd (21,28)    .. applying (3)
                = 21*28/7
lcm (21,28) = 84

Based on these equations following is Java code that computes GCD and LCM.

public class GcdLcm {

 public static void main(String[] args) {
  System.out.println("GCD = " + gcd(42,35));
  System.out.println("LCM = " + lcm (21,28));
 }

 public static int gcd(int a, int b){

  if(b==0) 
   return a;
  else
   return gcd(b,a%b); 
 }
 
 public static int lcm(int a,int b){
  return (a*b)/ gcd(a,b);
 }
 
}