Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

4.1: Greatest Common Divisor

( \newcommand{\kernel}{\mathrm{null}\,}\)

Think out loud

We want to tile a 253 ft by 123 ft (a=253 and b=123, with a,bZ) floor with identical square tiles. What is the largest square tile we can use?

Definition: Greatest Common Divisor

Let a,bZ, where a,b not both zero.

Then, we say that an integer d=gcd(a,b)Z+., greatest common divisor if it satisfies the following conditions:

  1. d|a and d|b, Note: d must divide both numbers

If cZ, c|a and c|b then cd. Note: d is the greatest number that divides both.

Thus 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. This class will use the following notation: gcd(a,b).

Example 4.1.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 4.1.2:

An elementary gym teacher has 3 grade 4 gym classes with 21,35 and 28 students in them. The teacher wants to order equipment that equal-sized groups can use 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 728 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 of students in a group for each class will be 7.

Properties:

Let a,b,cZ. This section introduces a binary operation on Z.

Then:

  1. gcd(a,a)=|a|,a0.
  2. gcd(a,b)=gcd(b,a).
  3. gcd(a,b,c)=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 real-world applications for learning the greatest common divisor (gcd).

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

This page titled 4.1: Greatest Common Divisor is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by Pamini Thangarajah.

Support Center

How can we help?