The greatest common divisor (gcd) of two natural numbers is the largest number that evenly divides both. For instance *gcd(8, 12)* is 4. There are many clever and efficient ways to calculate the gcd of two numbers on a Linux machine. The method presented here is not among them.

#!/bin/bash

gcd(){ comm -12 --nocheck-order <(factor $1|sed 's/^[^ ]*/1/;s/ /\n/g') <(factor $2|sed 's/^[^ ]*/1/;s/ /\n/g')|tr '\n' \*|sed 's/.$/\n/'|bc;}

gcd $1 $2

(Contrived) example:

gcd.sh 24691357802469135780246913578 61728394506172839450617283945

12345678901234567890123456789

Which breaks down as:

prime factors of 24691357802469135780246913578 |
prime factors of 61728394506172839450617283945 |

2 | |

3 | 3 |

3 | 3 |

3 | 3 |

5 | |

7 | 7 |

13 | 13 |

31 | 31 |

37 | 37 |

211 | 211 |

241 | 241 |

2161 | 2161 |

3607 | 3607 |

3803 | 3803 |

2906161 | 2906161 |

Multiply the factors common to both:

3 × 3 × 3 × 7 × 13 × 31 × 37 × 211 × 241 × 2161 × 3607 × 3803 × 2906161 = 12345678901234567890123456789

I’m sure someone else has used the output of factor and comm in this way before. The hard part was getting coprime numbers to output 1.

This doesn’t quite work: try

gcd 5652 8478

and it returns 18. Both 5652 & 8478 have 157 as a factor, so something’s wrong here.