Divisibility, GCF, and LCM
Sofia's phone PIN has the form $7X2Y$. She only remembers that the number is divisible by $4$ and by $9$. How can she find every possible PIN without testing all 100 combinations of $X$ and $Y$? Divisibility rules, prime factors, and a little organization will do it. The same tools also solve problems about flashing lights, gears, and equal groups.
Multiples and factors
Let's start with the vocabulary. If $a = b \times k$ for some whole number $k$, then $a$ is a multiple of $b$, and $b$ is a factor (or divisor) of $a$. We also say $a$ is divisible by $b$: dividing leaves no remainder.
For example, $42 = 6 \times 7$. So $42$ is a multiple of $6$, $6$ is a factor of $42$, and $42$ is divisible by $6$.
To list multiples, skip count: the multiples of $8$ are $8, 16, 24, 32, \ldots$ There are infinitely many.
To list factors, look for pairs that multiply to the number, working upward from $1$. Stop when the pairs meet in the middle. There are only a few factors, and the largest is the number itself.
On a streaming platform, series are grouped into seasons. If a series has a total of $42$ episodes, state which of the following statements are true and which are false,…
On a streaming platform, series are grouped into seasons. If a series has a total of $42$ episodes, state which of the following statements are true and which are false, briefly reasoning your answer:
- a) The number $6$ is a divisor of $42$.
- b) $42$ is a multiple of $5$.
- c) $42$ is divisible by $14$.
Work out mentally and write in your notebook: a) The first five multiples of $12$. b) All the divisors of the number $24$. c) The multiples of $7$ between $30$ and $60$.
Work out mentally and write in your notebook:
- a) The first five multiples of $12$.
- b) All the divisors of the number $24$.
- c) The multiples of $7$ between $30$ and $60$.
Divisibility rules
Dividing every time is slow. Divisibility rules let you decide just by looking at the digits.
| Divisible by | Rule |
|---|---|
| $2$ | The last digit is $0, 2, 4, 6$, or $8$. |
| $3$ | The sum of the digits is divisible by $3$. |
| $4$ | The number formed by the last two digits is divisible by $4$. |
| $5$ | The last digit is $0$ or $5$. |
| $6$ | The number is divisible by $2$ and by $3$. |
| $8$ | The number formed by the last three digits is divisible by $8$. |
| $9$ | The sum of the digits is divisible by $9$. |
| $10$ | The last digit is $0$. |
| $11$ | (sum of digits in odd positions) $-$ (sum of digits in even positions) is $0$ or a multiple of $11$. |
Why do these work? Since $100 = 4 \times 25$, every hundred is divisible by $4$, so only the last two digits matter. In the same way $1{,}000 = 8 \times 125$, so only the last three digits matter for $8$. For $3$ and $9$, the numbers $10$, $100$, $1{,}000$ are each one more than a multiple of $9$. So a number leaves the same remainder as its digit sum does.
For the rule of $11$, number the positions from the right: the units digit is 1st, the tens digit is 2nd, and so on.
Number patterns made of dots are called polygonal numbers. Triangular numbers use triangles. Pentagonal numbers use pentagons: the 1st is a single dot, the 2nd is a pentagon with $5$ dots, and each next one is a bigger pentagon that shares a corner and two sides with the previous one. To draw the next arrangement, add a new outer layer of dots along the two new sides.
| Term $n$ | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Pentagonal number | $1$ | $5$ | $12$ | $22$ | ? | ? |
| Dots added | $+4$ | $+7$ | $+10$ | ? | ? |
The number of dots added at each step goes up by $3$ each time: $4, 7, 10, 13, 16, \ldots$ (the $n$th layer adds $3n - 2$ dots).
Look at the following polygonal numbers that represent the pentagonal numbers. The first terms are $1, 5, 12, 22...$ a) Draw in your notebook the arrangement of dots for…
Look at the following polygonal numbers that represent the pentagonal numbers. The first terms are $1, 5, 12, 22...$
- a) Draw in your notebook the arrangement of dots for the fifth pentagonal number.
- b) Following the sequence, what is the numerical value of the fifth and sixth pentagonal numbers?
- c) Check if the tenth pentagonal number ($145$) is divisible by $3$, by $5$ and by $11$.
Prime and composite numbers
A prime number has exactly two factors: $1$ and itself. A composite number has more than two factors. The number $1$ is neither prime nor composite, because it has only one factor.
How do you test a bigger number $n$? Try dividing by the primes $2, 3, 5, 7, \ldots$ in order, and stop once you pass $\sqrt{n}$. Why can you stop? If $n = a \times b$ with $a \le b$, then $a$ cannot be bigger than $\sqrt{n}$. So if no small prime divides $n$, no larger one will either.
Look at the numbers that appear on the following panel and classify them into prime numbers or composite numbers.
Look at the numbers that appear on the following panel and classify them into prime numbers or composite numbers.
Prime factorization
Every composite number can be written as a product of primes, and in only one way (apart from the order). This is called its prime factorization. A factor tree helps you find it: split the number into any two factors, then keep splitting until every branch ends in a prime.
Group equal primes and write them as powers: $90 = 2 \times 3^2 \times 5$.
Find the prime factorization of the following natural numbers. Remember to write the final result as a product of powers: a) $36$ b) $60$ c) $126$
Find the prime factorization of the following natural numbers. Remember to write the final result as a product of powers:
- a) $36$
- b) $60$
- c) $126$
GCF and LCM
The greatest common factor (GCF) of two numbers is the largest number that divides both. The least common multiple (LCM) is the smallest positive number that is a multiple of both.
Prime factorizations make both easy:
-
GCF: take only the primes that appear in both numbers, each with its smallest exponent.
-
LCM: take every prime that appears in either number, each with its largest exponent.
There is a handy relationship for two numbers $a$ and $b$:
$$\text{GCF}(a, b) \times \text{LCM}(a, b) = a \times b$$It lets you find a missing LCM, GCF, or number. Check with $12$ and $18$: $6 \times 36 = 216 = 12 \times 18$.
Calculate the greatest common factor (GCF) and the least common multiple (LCM) of the following pairs of numbers: a) $10$ and $15$ b) $20$ and $30$ c) $8$ and $12$
Calculate the greatest common factor (GCF) and the least common multiple (LCM) of the following pairs of numbers:
- a) $10$ and $15$
- b) $20$ and $30$
- c) $8$ and $12$
Knowing that the product of two numbers is $2160$ and that their greatest common factor (GCF) is $12$: a) Calculate the least common multiple (LCM) of these numbers…
Knowing that the product of two numbers is $2160$ and that their greatest common factor (GCF) is $12$:
- a) Calculate the least common multiple (LCM) of these numbers using the relationship between GCF and LCM.
- b) If one of the numbers is $60$, what is the other number?
- c) Find the prime factorization of both numbers to check that the results of the previous sections are correct.
Problems that use the GCF
Word problems hide a GCF or an LCM. The wording tells you which one.
For splitting problems, the numbers may be three quantities. The method is the same: use only primes that appear in all of them, with the smallest exponent.
Emma has $24$ star stickers and $16$ planet stickers. She wants to make identical gift envelopes (with the same number of stars and the same number of planets in each…
Emma has $24$ star stickers and $16$ planet stickers. She wants to make identical gift envelopes (with the same number of stars and the same number of planets in each one) with no stickers left over.
What is the maximum number of envelopes she can prepare? How many stickers of each type will there be in each envelope?
An interior design company has two rolls of colored LED strips: a blue light one measuring $120$ feet and a warm light one measuring $156$ feet. They want to cut both…
An interior design company has two rolls of colored LED strips: a blue light one measuring $120$ feet and a warm light one measuring $156$ feet. They want to cut both rolls into pieces of the same length, as long as possible, with no material left over.
- a) How long must each piece be?
- b) How many pieces of each color will they get in total?
A logistics company must organize three types of aid packages into shipping containers. They have $144$ boxes of blankets, $120$ boxes of non-perishable food and $84$…
A logistics company must organize three types of aid packages into shipping containers. They have $144$ boxes of blankets, $120$ boxes of non-perishable food and $84$ boxes of hygiene kits.
They want to load the maximum number of identical containers, so that each container has the same amount of boxes of each type and no boxes are left over in the warehouse.
-
How many containers can be sent?
-
How many boxes of each type will there be in each container?
Problems that use the LCM
When two or more things repeat on different schedules, they line up again at a common multiple of their cycle lengths. The first time is the least common multiple.
Two lights on a gaming keyboard flash differently. The blue light turns on every $6$ seconds and the orange light every $9$ seconds. If both have turned on at the same…
Two lights on a gaming keyboard flash differently. The blue light turns on every $6$ seconds and the orange light every $9$ seconds. If both have turned on at the same time right now, how many seconds will pass until they coincide turned on again for the first time?
Three streaming channels start broadcasting special content today at 10:00 in the morning. Channel A broadcasts a giveaway every $18$ hours. Channel B broadcasts an…
Three streaming channels start broadcasting special content today at 10:00 in the morning.
-
Channel A broadcasts a giveaway every $18$ hours.
-
Channel B broadcasts an interview every $24$ hours.
-
Channel C broadcasts a tournament every $30$ hours.
How many days must pass as a minimum for the three events to coincide again at the same time? At what time and on what day of the week will it happen if today is Monday?
On the main stage of a music festival, there are three robotic lighting systems. The first system emits a white flash every $18$ seconds, the second a blue flash every…
On the main stage of a music festival, there are three robotic lighting systems. The first system emits a white flash every $18$ seconds, the second a blue flash every $24$ seconds and the third an orange flash every $30$ seconds.
At $21:00$ hours the three systems coincide for the first time. How many times will the three flashes coincide exactly again before the concert finishes at $22:25$ hours?
Tiles, gears, and clocks
Some problems need one more step after the GCF or LCM.
Tiles. Covering a rectangle with the largest square tiles that need no cutting means the side is the GCF of the length and width. To count tiles, find how many fit along each side and multiply.
Gears. Two meshing gears with $a$ and $b$ teeth line up again after $\text{LCM}(a, b)$ teeth have passed. Then each gear has turned (teeth passed) $\div$ (its number of teeth) times.
Clocks. Convert everything to one unit (usually minutes), find the LCM, then convert back to hours and add to the start time.
A town council wants to pave a rectangular plaza $45$ feet long by $24$ feet wide using square stone tiles. The architect wants the tiles to be as large as possible and…
A town council wants to pave a rectangular plaza $45$ feet long by $24$ feet wide using square stone tiles. The architect wants the tiles to be as large as possible and that none have to be cut.
-
What must the side length of each tile be?
-
If for budget reasons they decide to use tiles half that size, how many tiles will they need now to cover the whole plaza?
The mechanism of an old clock uses two cogwheels that mesh together. Wheel $A$ has $54$ teeth and wheel $B$ has $36$ teeth. If we put a red mark on the point where the…
The mechanism of an old clock uses two cogwheels that mesh together. Wheel $A$ has $54$ teeth and wheel $B$ has $36$ teeth. If we put a red mark on the point where the teeth touch right now:
-
How many teeth of wheel $A$ must pass for the marks to coincide again for the first time?
-
How many turns will each wheel have made at that moment?
Three artificial satellites orbit the Earth. The first completes an orbit every $90$ minutes, the second every $2$ hours and the third every $105$ minutes. If at $12:00$…
Three artificial satellites orbit the Earth. The first completes an orbit every $90$ minutes, the second every $2$ hours and the third every $105$ minutes. If at $12:00$ noon they are aligned over the Greenwich meridian:
-
At what exact time will they be aligned again for the first time?
-
How many orbits will the slowest satellite have completed in that time?
Finding a missing digit
In a code like $6A4$, the letter stands for an unknown digit from $0$ to $9$. If a code is written with a blank, like $345\_$, the blank is the missing last digit of the four-digit number.
The strategy: write what the rule says in terms of the unknown digit, then list the digits $0$ to $9$ that work.
-
For $2$, $5$, $10$ only the last digit matters. For $4$ and $8$ only the last two or three digits matter.
-
For $3$ and $9$, add the digits, treating the unknown digit as a variable.
A video game requires you to enter a four-digit code to unlock a level: $3.45\$. Help the player find the last digit so that the number meets the following conditions:…
A video game requires you to enter a four-digit code to unlock a level: $3.45\_$. Help the player find the last digit so that the number meets the following conditions:
- a) The number is divisible by $2$ and by $5$ at the same time.
- b) The number is divisible by $3$, but not by $2$.
- c) It is a multiple of $9$.
A programmer is designing a four-digit access code. The code follows the format $35A2$, where $A$ is an unknown digit. For the code to be valid, the number must be…
A programmer is designing a four-digit access code. The code follows the format $35A2$, where $A$ is an unknown digit. For the code to be valid, the number must be divisible by $3$ and by $4$ simultaneously.
Determine all the possible values that the digit $A$ can take and write down the resulting complete numbers.
Several conditions at once
When a number must satisfy two or more rules, solve each rule separately and write down all values that work. Then keep only the values on both lists.
Back to the beginning. For $7X2Y$ to be divisible by $4$, the last two digits $2Y$ must be a multiple of $4$: $20, 24, 28$, so $Y \in \{0, 4, 8\}$. For divisibility by $9$, the digit sum $7 + X + 2 + Y = 9 + X + Y$ must be a multiple of $9$. If $Y = 0$, then $X = 0$ or $9$. If $Y = 4$, then $X = 5$. If $Y = 8$, then $X = 1$. So Sofia's PIN is one of $7020$, $7920$, $7524$, $7128$.
At a video game convention, they want to organize the participants into teams. We have a security code for access which is a four-digit number of the form $4A2B$. For…
At a video game convention, they want to organize the participants into teams. We have a security code for access which is a four-digit number of the form $4A2B$.
For the code to be valid, it must meet two conditions:
- a) It must be divisible by $3$.
- b) It must be divisible by $11$.
Find all the possible values for the digits $A$ and $B$.
A famous influencer* wants to protect access to his video editing account with a four-digit PIN code of the form $5X4Y$. So as not to forget it, he has memorized the…
A famous influencer wants to protect access to his video editing account with a four-digit PIN code of the form $5X4Y$. So as not to forget it, he has memorized the following conditions based on divisibility:
-
The number is divisible by $4$.
-
The number is also divisible by $9$.
-
The units digit ($Y$) is greater than the thousands digit.
Find all the possible PIN codes that meet these conditions.
Find a natural number that simultaneously meets the following conditions: 1. It is between $200$ and $250$. 2. It is a multiple of $13$. 3. When divided by $2$ and by…
Find a natural number that simultaneously meets the following conditions:
-
It is between $200$ and $250$.
-
It is a multiple of $13$.
-
When divided by $2$ and by $3$ it gives an exact division, but it is not divisible by $9$.
Counting factors
You can find how many factors a number has without listing them. Write its prime factorization $N = p^a \times q^b \times \cdots$. Each factor chooses an exponent for $p$ from $0$ to $a$ ($a + 1$ choices), an exponent for $q$ from $0$ to $b$ ($b + 1$ choices), and so on.
Check with $12 = 2^2 \times 3$: $(2 + 1)(1 + 1) = 6$, and the factors are $1, 2, 3, 4, 6, 12$. The perfect-square rule works because squaring a number doubles every exponent, and doubled exponents are always even.
Calculate the total number of divisors that the number $360$ has without needing to write them all down. To do this: a) Find its prime factorization using powers. b)…
Calculate the total number of divisors that the number $360$ has without needing to write them all down. To do this:
- a) Find its prime factorization using powers.
- b) Apply the property of the product of the exponents increased by one.
- c) State whether the number $360$ is a perfect square, reasoning your answer based on the exponents of its factorization.
A natural number $N$ has the following prime factorization: $N = 2^{a} \cdot 3^{2} \cdot 5^{1}$. We know that the total number of divisors of $N$ is exactly $24$. 1.…
A natural number $N$ has the following prime factorization: $N = 2^{a} \cdot 3^{2} \cdot 5^{1}$.
We know that the total number of divisors of $N$ is exactly $24$.
-
Calculate the value of the exponent $a$.
-
Determine the numerical value of $N$.
-
Write down all the divisors of $N$ that are multiples of $15$ but not of $2$.
It is known that a number $X$ is a multiple of $12$ and $15$ simultaneously. Furthermore, $X$ has exactly $10$ natural divisors. 1. Using prime factorization, deduce the…
It is known that a number $X$ is a multiple of $12$ and $15$ simultaneously. Furthermore, $X$ has exactly $10$ natural divisors.
-
Using prime factorization, deduce the value of $X$. (Hint: reason about the exponents of the factorization).
-
Justify whether the number $X+1$ is a prime or composite number.