Skip to main content
$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}{\| #1 \|}$$ $$\newcommand{\inner}{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$

# 4.1 Greatest Common Divisor

• • Contributed by Pamini Thangarajah
• Associate Professor (Mathematics & Computing) at Mount Royal University

$$\newcommand{\vecs}{\overset { \rightharpoonup} {\mathbf{#1}} }$$

$$\newcommand{\vecd}{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}}$$

Think out loud

We want to tile a 253 ft by 123 ft (a=253 and b=123, with $$a, b \in \mathbb{Z} )$$ floor with identical square tiles. What is the largest square tile we can use?

Definition

The greatest common divisor of two integers $$a$$ and $$b$$, also known as GCD of $$a$$ and $$b$$, is the greatest positive integer that divides the two integers. We will use the following notation in this class: $$\gcd (a,b)$$.

Example $$\PageIndex{1}$$:

What is the GCD of $$15$$ and $$20$$?

A process to find the solution:
List all positive divisors of $$15$$ and $$20$$.
The positive divisors of $$15$$ are $$1, 3, 5,$$ and $$15$$.
The positive divisors of $$20$$ are $$1, 2, 4, 5, 10,$$ and $$20$$.
The common positive divisors are $$1, 5$$.
As you can see from the list the GCD of $$15$$ and $$20$$ is $$5.$$ That is, the $$\gcd(15, 20)=5.$$

Example $$\PageIndex{2}$$:

An elementary gym teacher has $$3$$ grade $$4$$ gym classes with $$21, 35$$ and $$28$$ students in them. The teacher wants to order some equipment that can be used by equal-sized groups in each class. What is the largest group size that will work for all $$3$$ classes?

Solution:
You will need to find the GCD of all $$3$$ classes.
Firstly, you will find the GCD of $$21$$ and $$35.$$
The positive divisors of $$21$$ are $$1, 3, 7,$$ and $$21$$.
The positive divisors of $$35$$ are $$1, 5, 7,$$ and $$35$$.
The GCD of $$21$$ and $$35$$ is $$7.$$

Since $$7 \mid 28$$ you will now find the GCD of $$7$$ and $$28$$, which turns out to be 7.
Therefore the GCD of $$21, 35$$ and $$28$$ is $$7.$$
Thus, the largest number students in a group for each class will be $$7.$$

Properties:

Let $$a,b,c \in \mathbb{Z}$$. In this section, we have introduced a binary operation on $$\mathbb{Z}$$.

Then:

1. $$\gcd(a, a)=|a|, a\ne 0.$$
2. $$\gcd(a, b)=\gcd(b, a)$$.
3. $$\gcd (\gcd(a, b), c)=\gcd (a, \gcd(b, c))$$.
4. $$\gcd(a, 0)=a$$.
5. $$\gcd(0, 0)$$ is undefined.

In the next section, we will learn an algorithm to calculate GCD.

Practical Uses:

There are many different real-world applications for learning the greatest common divisor (gcd).

• Fractions
• Algebra
• Foundational word problem skills
• Ratios
• Recipes
• Group arrangements