you are here->home->Computer Science->Class 12->GCD Subtraction Method
GCD Subtraction Method

 

Our Objective

To implement a program to find the Greatest Common Divisor (GCD) between two positive integer numbers using subtraction method. 

 

The Theory

The GCD (Greatest Common Divisor) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. There are many ways to find the GCD of two numbers, including the Subtraction Method.

The Subtraction Method is a simple and iterative algorithm for finding the GCD of two numbers. The basic idea is to subtract the smaller number from the larger number until both numbers become equal. The resulting number is the GCD of the original two numbers.

Here is the step-by-step process for finding the GCD of two numbers using the Subtraction Method:

  1. Take two numbers "a" and "b", where "a" is greater than or equal to "b".
  2. Subtract "b" from "a". If the result is greater than or equal to "b", replace "a" with the result and go back to step 2. Otherwise, let "a" be the smaller number and let "b" be the difference.
  3. Repeat step 2 until both numbers are equal.
  4. The resulting number is the GCD of the original two numbers.

For example, let's find the GCD of 42 and 28 using the Subtraction Method:

a = 42 and b = 28.

Subtract "b" from "a": 42 - 28 = 14. Since 14 is less than 28, let "a = 28" and "b = 14".

Subtract "b" from "a": 28 - 14 = 14. Since both numbers are equal, stop.

The GCD of 42 and 28 is 14.

The Subtraction Method is a simple and easy-to-understand algorithm for finding the GCD of two numbers. However, it can be inefficient for large numbers or when the numbers are relatively prime (have no common factors). Other algorithms, such as the Euclidean Algorithm, are more efficient for these cases.

 

Learning Outcomes 

  • Understanding of basic arithmetic concepts: Using the Subtraction Method to find the GCD of two numbers requires knowledge of arithmetic operations such as subtraction, division, and remainders.
  • Development of problem-solving skills: Using the Subtraction Method requires breaking down the problem of finding the GCD of two numbers into smaller, more manageable steps. This can help individuals develop their problem-solving skills.
  • Improved logical thinking: The Subtraction Method involves creating a logical sequence of steps to find the GCD of two numbers. This can help individuals improve their logical thinking skills.
  • Understanding of number theory: The Subtraction Method is one of several algorithms for finding the GCD of two numbers. Learning about different algorithms for finding the GCD can help individuals develop a deeper understanding of number theory.
  • Practice with calculation and computation: Using the Subtraction Method to find the GCD of two numbers requires practice with calculation and computation. This can help individuals develop their math skills.