Bash Script to Find GCD of Two Numbers

Use Euclid's algorithm in Bash with a loop: while [ $b -ne 0 ]; do temp=$b; b=$((a % b)); a=$temp; done; echo $a to find the GCD of two numbers.

Examples

Inputa=12, b=8

Output4

Inputa=100, b=25

Output25

Inputa=17, b=13

Output1

How to Think About It

To find the GCD, repeatedly replace the larger number by the remainder of dividing the larger by the smaller until the remainder is zero. The last non-zero remainder is the GCD.

Algorithm

1

Get two numbers as input.

2

While the second number is not zero:

3

Replace the first number with the second number.

4

Replace the second number with the remainder of the first number divided by the second.

5

When the second number becomes zero, the first number is the GCD.

6

Return the first number.

Code

bash

#!/bin/bash
read -p "Enter first number: " a
read -p "Enter second number: " b
while [ $b -ne 0 ]; do
  temp=$b
  b=$((a % b))
  a=$temp
done
echo "GCD is $a"

Output

Enter first number: 12
Enter second number: 8
GCD is 4

Dry Run

Let's trace the input a=12, b=8 through the code

1

Initial values

a=12, b=8

2

First loop iteration

temp=8, b=12 % 8 = 4, a=8

3

Second loop iteration

temp=4, b=8 % 4 = 0, a=4

a	b	temp	b after modulo
12	8
8	4	8	4
4	0	4	0

Why This Works

Step 1: Using Euclid's algorithm

The algorithm uses the fact that the GCD of two numbers also divides their remainder.

Step 2: Loop until remainder zero

We keep replacing numbers until the remainder is zero, which means the divisor is the GCD.

Step 3: Final GCD output

When the loop ends, the first number holds the GCD, which we print.

Alternative Approaches

Recursive function

bash

#!/bin/bash
function gcd() {
  if [ $2 -eq 0 ]; then
    echo $1
  else
    gcd $2 $(( $1 % $2 ))
  fi
}
read -p "Enter first number: " a
read -p "Enter second number: " b
echo "GCD is $(gcd $a $b)"

Uses recursion for clarity but may be less efficient for very large inputs.

Using bc command

bash

#!/bin/bash
read -p "Enter first number: " a
read -p "Enter second number: " b
result=$(echo "define gcd(a,b) { if (b == 0) return a; return gcd(b, a%b); } gcd($a,$b)" | bc)
echo "GCD is $result"

Uses bc calculator with recursion, requires bc installed.

Complexity: O(log(min(a,b))) time, O(1) space

Time Complexity

Euclid's algorithm runs in logarithmic time relative to the smaller input because each step reduces the problem size significantly.

Space Complexity

The algorithm uses constant extra space, only a few variables for swapping and remainder.

Which Approach is Fastest?

The iterative loop approach is generally fastest and simplest; recursion adds overhead, and using external tools like bc depends on system calls.

Approach	Time	Space	Best For
Iterative loop	O(log(min(a,b)))	O(1)	Simple and efficient for all inputs
Recursive function	O(log(min(a,b)))	O(log(min(a,b)))	Clear code but uses call stack
bc command	Depends on bc	Depends on bc	When bc is preferred or for complex math