Lesson Library> Prime Factorizations
Prime Factorizations
The sum of three positive integers is $\textit{61}$ and their product is $\textit{636}$. What are the three numbers?
We could try to solve this problem by choosing three numbers whose sum equals $61$ and then tweaking these numbers to get the product right. Let’s say we guess at $1$, $3$ and $58$, but this gives us the product $174$. If we instead try $2 \cdot 2 \cdot 57=228$ we improve the product somewhat, but we are still not there.
In this lesson, we will cover a method called prime factorization for solving such problems in less than $30$ seconds. If you want to learn what this method is, then read on!
Introduction to Prime Numbers
All integers have so-called divisors, which are the numbers with which the integer can be evenly divided with no remainder left at the end. The divisors to the number $6$, for example, are $1$, $2$, $3$ and $6$.
Some other examples of numbers and their divisors are:
$1$: $1$
$8$: $1$, $2$, $4$, $8$
$24$: $1$, $2$, $3$, $4$, $6$, $8$, $12$, $ 24$
$53$: $1$, $53$
$105$: $1$, $3$, $5$, $7$, $15$, $21$, $35$, $105$
Numbers with several divisors can often be broken up into products of smaller integers. For example, $24 \ =$$ \ 2 \cdot2 \cdot2 \cdot3$ or $2^3 \cdot3$. Similarly, $105 = $$ \ 3 \cdot 5 \cdot 7$.
We keep dividing the numbers into smaller factors until we can't get any further. The numbers we are left with at the end, such as $2$, $3$, $5$, $7$ and $11$ are called prime numbers. Prime numbers are special because they only have two divisors, $1$ and themselves, so they can’t be divided further into smaller factors. We can therefore think of prime numbers as the smallest building blocks of a number.
Rewriting an integer or an expression as a product of smaller factors is called factoring. And when we divide an integer into a product of prime numbers we call it prime factorization.
Exercise 1
Find all prime numbers smaller than $100$. There are $25$ of them in total.
Hint! Start by crossing out all numbers divisible by the first prime number, $2$, so $4$, $6$, $8 \dots$ $100$ are eliminated. Then cross out all numbers that were divisible by the second prime number, $3$, etc.
All prime numbers smaller than $100$ are:
$\mathbf{2}$, $\mathbf{3}$, $\mathbf{5}$, $\mathbf{7}$, $\mathbf{11}$, $\mathbf{13}$, $\mathbf{17}$, $\mathbf{19}$, $\mathbf{23}$, $\mathbf{29}$, $\mathbf{31}$, $\mathbf{37}$, $\mathbf{41}$, $\mathbf{43}$, $\mathbf{47}$, $\mathbf{53}$, $\mathbf{59}$, $\mathbf{61}$, $\mathbf{67}$, $\mathbf{71}$, $\mathbf{73}$, $\mathbf{79}$, $\mathbf{83}$, $\mathbf{89}$, $\mathbf{97}$
The number $1$ does not actually count as a prime number. We will discuss why this is so later in this lesson.
Prime Factorization in Practice
Let's try to prime factorize the number $126$. The easiest way to factorize prime numbers is to start with the smallest possible prime number, which in this case is $2$. This gives us $\dfrac{63}{3}=63$.
Prime factors: $2$
Remaining number: $63$
$63$ is divisible by $3$. We now have $\dfrac{63}{3}=21$.
Prime factors: $2 \cdot3$
Remaining number: $21$
$21$ can be divided by $3$, which gives us $\dfrac{21}{3}=7$.
Prime factors: $2 \cdot 3 \cdot 3$
Remaining number: $7$
The number $7$ is a prime number and can't be factorized further.
Prime factors: $2 \cdot3 \cdot3 \cdot7$
Remaining number: -
$126$ can thus be prime factorized to $2 \cdot3 \cdot3 \cdot7 = 2 \cdot3^2 \cdot7$. It is always a good idea to write down all prime factors as you determine them to keep your calculations organized.
Exercise 2
Prime factorize the following numbers.
a) $27$
b) $31$
c) $114$
d) $288$
e) $726$
f) $1380$
g) $9240$
a) $\mathbf{3^3}$
b) $\mathbf{31}$
c) $\mathbf{2 \cdot3 \cdot19}$
d) $\mathbf{2^5 \cdot3^2}$
e) $\mathbf{2 \cdot3 \cdot11^2}$
f) $\mathbf{2^2 \cdot3 \cdot5 \cdot23}$
g) $\mathbf{2^3 \cdot3 \cdot5 \cdot7 \cdot11}$
Why 1 Is Not a Prime Number
The number $1$ is actually not a prime number. This may sound strange, since $1$ is divisible by $1$ and it is also divisible by itself (which also happens to be $1$). Why then does it not count as a prime number?
The reason is that $1$ does not contribute anything to the prime factorization. Let’s say we prime factorize $15 = $$ \ 3 \cdot5$. If we count $1$ as a prime number, we could also write this as $15 = $$ \ 3 \cdot5 $$ \ \cdot1$, as $3 \cdot5 $$ \ \cdot1 $$ \ \cdot1$, or as $3 \cdot 5 \cdot1 $$ \ \cdot1$$ \ \cdot1$. We can add any number of $1$s and still have the same product.
Prime numbers have two important properties. Firstly, they have no other divisors other than $1$ and themselves. This means that they be divided into a product of two smaller whole numbers. Secondly, they must have a meaningful value. Although the number $1$ cannot be divided into a product of two smaller numbers, its value is irrelevant when we work with multiplication.
Another difference between the number $1$ and the real prime numbers is that $1$ has only one divisor: $1$. To be counted as a prime number, a number must have exactly two divisors: $1$ and itself. No more. No less.
$1$ can therefore be said to be the number that completely lacks prime factors. Just as we can add any number of zeros to a sum without changing the sum’s value, we can also multiply a product by any number of $1$s without changing the product’s value.
Using Prime Factorization to Find Divisors
Exercise 1
Find all the divisors for the following numbers:
a) $25$
b) $68$
c) $71$
d) $99$
e) $120$
f) $208$
g) $594$
h) $1000$
a) $1, 5, 25$
b) $1, 2, 4$$, 17, 34, 68$
c) $1, 71$
d) $1, 3, 9, 11, 33, 99$
e) $1, 2, 3, 4, 5, 6, 8, 10$$, 12, 15, 20, 24, 30,$$40, 60, 120$
f) $1, 2, 4, 8, 13, 16, 26, 52,$$104, 208$
g) $1, 2, 3, 6, 9, 11, 18, 22, 27, 33, 54, 66,$$99, 198, 297, 594$
h) $1, 2, 4, 5, 8, 10, 20, 25, 40, 50, 100,$$ 125, 200, 250,$$ 500, 1000$
Using Prime Factorization in Problem Solving
Let us now return to the question we posed at the beginning of the lesson:
The sum of three positive integers is $\textit{61}$ and their product is $\textit{636}$. What are the three numbers?
Prime factoring gives us $636 = 2^2 \cdot 3 \cdot 53$. Whichever three numbers we choose, they must consist of exactly these factors for their product to equal $636$. By combining these prime factors in different ways, we can create different sets of three numbers with different sums. One such combination is $(3, 2^2, 53) \ =$$ \ (3, 4, 53)$ with the sum $3+4+53=$$60$. Another is $(\ \_ \ , \ 2 \cdot 3, \ 2 \cdot 53) \ = $$ \ (1, 6, 106)$ with the sum $1+6+106=$$113$.
Obviously, we can't combine $53$ with any other prime factor since that number would be at least $2 \cdot 53=106$. This would make it impossible for the three numbers to equal $61$. One of our three numbers must therefore be $53$. We now have the prime factors $2^2 \cdot 3$ left to create two numbers whose sum should equal $61-53$$=8$. By trial and error shows we find that the numbers $2$ and $6$ are only solution.
The three numbers we are looking for are thus $\mathbf{2}$, $\mathbf{6}$ and $\mathbf{53}$. The table below shows all possible ways to divide the prime factors $2^2 \cdot 3 \cdot 53$ to form three numbers, only one of which gives the sum $61$.
Notice how simple this problem became when we started with getting the product right instead of getting the sum right. This is because there are countless sets of three numbers whose sum equals $61$. But there are very few sets of three numbers whose product equals $636$. By starting at the narrow end, we significantly reduce the number of possible cases we need to check.
This is why prime factorization is such a powerful tool. It lets us know which factors we must include in our calculations. It also tells us which factors we can’t use.
Imagine that your friend would attempt to solve this problem by trying to find three numbers whose sum equals $61$. Your friend guesses at $1$, $5$ and $55$, but this combination contains a $5$. To get to $636$ we must have exactly two $2$s, one $3$ and one $53$. If the product of our three numbers includes a $5$, it can’t possibly equal $636$. You already know that the guess won’t work without even having to determine the product!
Now imagine that your friend makes a new guess: $2, 3, 56$. Just by looking at the number $56=7 \cdot 8$ and realizing that it contains a $7$, you know that this guess won’t work either.
Note! Prime factorization can only be used for problems with products of integers. If we are not $100$% sure that it is an integer, we can not use the method. Prime factorization will also not help us if the task is only about sums or differences of integers. But if we have a product of integers, prime factorization will almost always be the way to go.
Greatest Common Factor (GCF)
We have seen how prime factorization can be used to determine the divisors of a number. When we have two or more numbers, these will sometimes share common divisors. For example, if we list the divisors of the numbers $36$, $42$ and $90$, we can see that $1$, $2$, $3$ and $6$ are divisors for all three numbers. The largest of these divisors, $6$, is called the greatest common factor (GCF). This is written as $GCF(36, 42, 90)$$ = 6$.
Exercise 1
How can we use prime factorization to determine the greatest common factor?
We can determine the greatest common factor by examining which prime factors the numbers have in common:
$36 = 2 \cdot 2 \cdot3 \cdot \ 3$
$42 = 2 \cdot3 \cdot \ 7$
$90 = 2 \cdot3 \cdot \ 3 \cdot5$
All three numbers contain one $2$ and one $3$. Their GCF must therefore be $2\cdot3 = 6$. If the numbers have no common factors, then $GCF = 1$. Numbers that don’t have any prime factors in common are called mutually prime. One example of numbers that are mutually prime are $15=3\cdot5$ and $28=2^2\cdot7$.
Exercise 2
Find the greatest common factor of the following groups of numbers.
a) $2, 4, 8, 16, 32$
b) $252, 306$
c) $126, 42, 154$
d) $308, 420, 672$
e) $147, 256$
f) $98, 180, 188, 330$
a) $2 \ = \ 2$
$4 \ = \ 2^2$
$8 \ = \ 2^3$
$16 \ = \ 2^4$
$GCF=\pmb{2}$
b) $252 \ = \ 2^2 \cdot 3^2 \cdot 7$
$306 \ = \ 2 \cdot 3^2 \cdot 17$
$GCF=2\cdot3^2=\pmb{18}$
c) $126 \ = \ 2 \cdot 3^2 \cdot 7$
$42 \ = \ 2 \cdot 3 \cdot 7$
$154 \ = \ 2 \cdot 7 \cdot 11$
$GCF = 2 \cdot 7 = \pmb{14}$
d) $308 \ = \ 2^2 \cdot 7 \cdot 11$
$420 \ = \ 2^2 \cdot 3 \cdot 5 \cdot 7$
$420 \ = \ 2^5 \cdot 3 \cdot 7$
$GCF = 2^2 \cdot 7 = \pmb{28}$
e) $147 \ = \ 3 \cdot 7^2$
$256 \ = \ 2^8$
$GCF = \pmb{1}$
f) $98 \ = \ 2 \cdot 7^2$
$180 \ = \ 2^2 \cdot 3^2 \cdot 5$
$188 \ = \ 2^2 \cdot 47$
$330 \ = \ 2 \cdot 3 \cdot 5 \cdot 11$
$GCF = \pmb{2}$
Simplifying Fractions
Being able to find common prime factors is very useful for simplifying fractions. If both the numerator and the denominator are large, the easiest way to simplify the fraction is to prime factorize both numbers and eliminate all common factors. Take the fraction $\dfrac{39 \ 984}{42 \ 840}$ as an example. If we factorize the numerator and the denominator, we get:
$ \dfrac{39 \ 984}{42 \ 840} \ = $$ \ \dfrac{2^4 \cdot3 \cdot7^2 \cdot17}{2^3 \cdot3^2 \cdot5 \cdot7 \cdot17} \ =$$ \ \dfrac{(2 \cdot7) (2^3 \cdot3 \cdot7 \cdot17)}{(3 \cdot5) (2^3 \cdot3 \cdot7 \cdot17)} \ \ =$$ \ \dfrac{2 \cdot7}{3 \cdot5} \ =$$ \ \dfrac{14}{15} $
The fraction can thus be simplified to $\dfrac{14}{15}$. Note that the factors we eliminated was the GCF of the numerator and the denominator.
$\text{GCF}(39 \ 984, \ 42 \ 840) \ = $$ \ (2^3 \cdot3 \cdot7 \cdot 17) \ = $$ \ 2856$
It is thus the greatest common factor of the numerator and the denominator that we simplify a fraction with.
Exercise 3
Simplify the following fractions as far as possible.
a) $\dfrac{105}{60}$
b) $\dfrac{693}{528}$
c) $\dfrac{212}{63}$
d) $\dfrac{15 \ 912}{7488}$
e) $\dfrac{275 \ 184}{458 \ 640}$
a) $\dfrac{105}{60} \ = $$ \ \dfrac{3 \cdot 5 \cdot 7}{2^2 \cdot 3 \cdot 5} \ = $$ \ \dfrac{(7)(3 \cdot 5}{(2^2)(3 \cdot 5)} \ = $$ \ \mathbf{\dfrac{7}{4}}$
b) $\dfrac{693}{528} \ = $$ \ \dfrac{3^2 \cdot 7 \cdot 11}{2^4 \cdot 3 \cdot 11} \ = $$ \ \dfrac{(3 \cdot 7)(3 \cdot 11}{(2^4)(3 \cdot 11)} \ = $$ \ \mathbf{\dfrac{21}{16}}$
c) $\dfrac{212}{63} \ = $$ \ \dfrac{2^2 \cdot 53}{3^2 \cdot 7} \ = $$ \ \mathbf{\dfrac{212}{63}}$
The numerator and the denominator have no common factors. The fraction can’t be simplified any further.
d) $\dfrac{15 \ 912}{7488} \ =$$ \ \dfrac{2^3 \cdot 3^2 \cdot 13 \cdot 17}{2^6 \cdot 3^2 \cdot 13} \ = $$ \ \dfrac{(17)(2^3 \cdot 3^2 \cdot 13)}{(2^3)(2^3 \cdot 3^2 \cdot 13)} \ = $$ \ \mathbf{\dfrac{17}{8}}$
e) $\dfrac{275 \ 184}{458 \ 640} \ =$$ \ \dfrac{2^4 \cdot 3^3 \cdot 7^2 \cdot 13}{2^4 \cdot 3^2 \cdot 5 \cdot 7^2 \cdot 13} \ = $$ \ \dfrac{(3)(2^4 \cdot 3^2 \cdot 7^2 \cdot 13)}{(5)(2^4 \cdot 3^2 \cdot 7^2 \cdot 13)} \ = $$ \ \mathbf{\dfrac{3}{5}}$
Least Common Multiple (LCM)
Closely tied to the greatest common factor is the least common multiple (LCM).
A multiple of an integer $x$ is a number that can be evenly divided by $x$. For example, $14$, $21$ and $77$ are multiples of the number $7$ because they are all divisible by $7$. Similarly, $4$, $12$, $20$ and $100$ are multiples of the number $4$. A multiple to $x$ is simply $x$ multiplied by another integer.
The least common multiple of a group of integers is the smallest number that all integers divide evenly. Note! Sometimes the least common multiple is also the least common divisor (LCD).
Take the numbers $84 = 2^2 \cdot3 \cdot7$ and $112 = 2^4 \cdot7$ as examples. For a number to be a multiple of $84$, it must contain at least two $2$s, one $3$ and one $7$. To be a multiple of $112$ it must contain at least four $2$ s and one $7$. Since we want a multiple to both $84$ and $112$, that number must therefore contain at least four $2$s, one $3$ and one $7$. The least common multiple is thus $2^4 \cdot3 \cdot7 =$$ 336$. This can be written as $\text{LCM}(84, 112$) $$= $336$.
$84 = 2^2 \cdot \mathbf{3} \cdot \mathbf{7}$
$112 = \mathbf{2^4} \cdot7$
$\text{LCM}=2^4 \cdot 3 \cdot 7=$$336$
To find the least common multiple, we only need to factorize the numbers and then pick the factor with the highest exponent for each prime factor. If we multiply these prime factors, we get the numbers’ LCM.
Exercise 1
Find the least common multiple for the following.
a) $48, 108$
b) $33, 84, 135$
c) $2, 4, 8, 16, 32$
d) $11, 13, 19$
e) $18, 21, 45$
a) $48 = 2^4 \cdot 3$
$108= 2^2 \cdot 3^3$
$LCM=(2^4 \cdot 3^3)=\mathbf{432}$
b) $33 = 3 \cdot 11$
$84= 2^2 \cdot 3 \cdot 7$
$132= 2^2 \cdot 11$
$LCM=(2^2 \cdot 3 \cdot 7 \cdot 11)=\mathbf{924}$
c) $2=2$
$4=2^2$
$8=2^3$
$16=2^4$
$32=2^5$
$LCM=(2^5)=\mathbf{32}$
d) $11=11$
$13=13$
$19=19$
$LCM=(11 \cdot 13 \cdot 19) =\mathbf{2717}$
e) $18 = 2 \cdot 3^2$
$21= 3 \cdot 7$
$45= 3^2 \cdot 5$
$LCM=(2 \cdot 3^2 \cdot 5 \cdot 7)=\mathbf{630}$
Exercise 2
How many multiples of $13$ are there between $100$ and $300$?
The smallest number divisible by $13$ in this range is $104$ and the greatest is $299$. There are a total of $\frac{299 - 104}{13} = 15$ multiples of $13$ that are greater than $104$. Including $104$ in our counting, we find that there are $15 + 1 = \mathbf{16}$ multiples number $13$ between $100$ and $300$.
Exercise 3
Three runners are jogging around a circular track. The first runner completes a lap every $24$ seconds, the second runner completes a lap every $35$ seconds and the third runner completes a lap every $56$ seconds. All runners start jogging at the same time from the same starting line, and they keep jogging clockwise around the track at a constant speed.
a) When will all three runners be back at the starting line for the first time?
b) When will two runners be back at the starting line for the first time?
a) The time it takes for all three runners to be back at the starting line is the LCM of their lap times.
$24 = 2^3 \cdot 3$
$35= 5 \cdot 7$
$56= 2^3 \cdot 7$
$LCM=(2^3 \cdot 3 \cdot 5 \cdot 7)=840$
So all three runners will be back at the starting line for the first time after $\mathbf{840}$ seconds.
b) The time it takes for two runners to be back at the starting line is the smallest of the three LCMs we get when we pair the runners’ lap times.
$LCM(24,35) = 840$
$LCM(24,56) = 168$
$LCM(35,56) = 840$
So two runners (runner #1 and runner #3) will be back at the starting line for the first time after $\mathbf{168}$ seconds.
Problems to Solve
Exercise 1
What is the difference between:
a) When it comes to integers, factors and divisors are exactly the same. They are the numbers that a certain integer is evenly divisible by.
When we work with algebraic expressions, however, we usually only use the word “factor” to describe a number or an expression with which our original expression is evenly divisible by. For example, $3$, $5$ and $(x + 2)$ are factors to the expression $15x + 30=$$15(x+2)$.
b) If a number is a multiple of $x$, it’s by definition also divisible by $x$. For example, $60$ is a multiple of $12$, and thus $60$ is also divisible by $12$. There is no difference between these formulations.
c) Divisors are the numbers by which a number is evenly divisible. The multiples of the number, on the other hand, are the numbers to which the number itself is a divisor. For example, the number $18$ has the parts $1, 2, 3, 6, 9$ and $18$, and its multiples are $18, 36, 54,$$ 72, 90 \dots$ etc. A number always has a limited number of divisors but infinitely many multiples.
Exercise 2
How many prime numbers have $5$ as their last digit?
If a number ends with $5$, it must also be divisible by $5$. However, prime numbers must not have any divisor other than $1$ and itself. Thus, $\pmb{5}$ is the only prime number that has $5$ as its last digit.
Exercise 3
Three integers $a$, $b$ and $c$ are multiples of $9$. Can we be sure that $\text{GCF}(a, b, c) = 9$?
If all three numbers are multiples of $9$, their GCF must contain the factor $3^2$. However, it is possible that the numbers have more common factors than that. The numbers $36$, $54$ and $72$, for example, all contain two $3$s but also one $2$. They are all multiples of $9$ but their GCF is $2 \cdot3^2 = 18$.
That all numbers are multiples of $9$ only means that their GCF must be divisible by $9$. The number GCF must therefore be one of the numbers $9, 18, 27, 36, 45 ...$ etc, but without further information we can not be sure that $\text{GCF}(a, b, c) = 9$.
Exercise 4
Carina has two fabrics that are $72$ inches and $90$ inches long. She wants to cut both fabrics into strips so that all strips are of the same width. What is the widest measure she could cut the strips into?
Since all strips have the same width, the width of a strip (in inches) must be a number that evenly divides both $72 = 2^3 \cdot3^2$ and $90 = 2 \cdot3^2 \cdot5$ . We could think of think as $72=wa$ and $90=wb$, where $w$ is the width of each strip and $a$ and $b$ are the number of strips we get from each fabric when they are cut into strips of $w$ inches.
We want the width to be as large as possible, so what we are searching for the is greatest common factor of $72$ and $90$. By comparing the numbers’ prime factors, we see that the greatest possible width the strips could have is $2 \cdot3^2 = \mathbf{18}$ inches.
Exercise 5
The product of two consecutive positive odd numbers is $675$. What are the two numbers?
(Two consecutive odd numbers are, for example, $5$ and $7$ or $21$ and $23$).
We start by prime factoring $675=3^3 \cdot5^2$. Since the product of integers is $675$, both numbers must be divisors of $675$. If we list all the divisors of $675$, we get the following:
$1$
$3$
$5$
$9$
$15$
$25$
$27$
$45$
$75$
$135$
$225$
$675$
The only two pairs of consecutive odd numbers are $(1,3)$ and $(25,27)$. The pair $(1,3)$ are obviously not the right answer, but the product of $\mathbf{25}$ and $\mathbf{27}$ becomes exactly $675$.
Exercise 6
Alex makes two types of cakes: chocolate and vanilla. He cuts all chocolate cakes into slices of $6$ and all the vanilla cakes into slices of $8$. If the same number of slices of both cakes are the same, what is the least number of cakes Alex could have baked?
The number of chocolate cake slices must be a multiple of $6$ and the number of vanilla cake slices must be a multiple of $8$. The least common multiple of $(6,8)$ is $24$, which would give Alex $24$ slices of each cake. The least number of cakes he could have baked is thus $\frac{24}{6} = 4$ chocolate cakes and $\frac{24}{8} = 3$ vanilla cakes, which is $4 + 3 = \mathbf{7}$ cakes in total.
Exercise 7
Determine $\dfrac{666666 \cdot 666666}{1 + 2 + 3 + 4 + 5 + 6 + 5 + 4 + 3 + 2 + 1}$.
Adding all the numbers in the denominator gives us $36$, which can be factorized to $6 \cdot 6$. Both $666666$s in the denominator each contain one $6$, so we can cancel out these factors in the denominator and the numerator against each other so that we only have the product $111111 \cdot111111$ left.
$ \dfrac{666666 \cdot 666666}{6 \cdot 6} \ \ =$$ \ \dfrac{(6 \cdot 6)(111111 \cdot 111111)}{6 \cdot 6} \ \ =$$ \ 111111 \cdot 111111 $
So the answer is $111111^2=\mathbf{12345654321}$.
Exercise 8
If $p$ is a prime number, how many divisors does $p^3$ have?
Since $p$ is a prime number, we can’t factorize $p^3$ any further. All possible divisors to $p3$ are therefore $1, p, p^2$ and $ p^3$ so the number has $\mathbf{4}$ divisors.
Exercise 9
The sum of three numbers is $83$ and their product is $1480$. What are the three numbers?
We start by prime factoring $1480=2^3 \cdot5 \cdot 37$. One of the three numbers must therefore be a multiple of $37$. We see that $3 \cdot37 = 111$ which is greater than $83$, so one of the numbers must be either $1 \cdot37 = 37$ or $2 \cdot 37 = 74$.
Let’s assume that one of the numbers is $37$. The other two numbers must then contain three $2$s and one $5$. By dividing the prime factors between these two numbers we can the following sums:
The greatest possible sum we can get is $41$, but even this is not enough to get to $83$ $(41 + 37 = 78)$. This means that our assumption was wrong, so one of the numbers must therefore be $74$. The other two numbers must then contain two $2$s and one $5$. Dividing these prime factors between the two numbers in all possible ways gives us the following sums:
The only division that gives the sum $83$ is to let one number be $4$ and the other $5$ $(4 + 5 + 74 =$$ 83)$. The three numbers are thus $\mathbf{4, 5}$ and $\mathbf{74}$.
Exercise 10
What is the smallest number, apart from $1$, found in all three series of numbers below?
$1, 9, 17, 25, 33, 41…$
$1, 14, 27, 40, 53, 66…$
$1, 19, 37, 55, 73, 81…$
The first series increases by +8 each time.
The second series increases by +13 each time.
The third series increases by +18 each time.
The next time the same number appears in all three series is the least common multiple of 8, 13, and 18. To find the least common multiple, we first prime factorize the numbers and then look at their common primes.
$8 = 2^3$
$13 = 13$
$18 = 2 \cdot 3^2$
The least common multiple is therefore $2^3 \cdot 13 \cdot 3^2 = 936$. But since all series start from $1$ instead of $0$, we must therefore add a $1$ to this number.
The smallest number, apart from $1$, that can be found in all three series is $936 + 1 = \mathbf{937}$.
Exercise 11
Marcus is making desserts for himself and his five friends. Each of the six desserts consists of chocolates, kiwis and strawberries. The ice cream is only sold in packages of $12$ pieces, the kiwis only in boxes of $10$ kiwis and the strawberries can only be bought in packages of $20$ strawberries. Marucs wants there to be as many chocolates, kiwis and strawberries in each dish. What is the least number of strawberries he needs to buy?
Since Marcus is making six desserts, the number of strawberries must be a multiple of $6$ for everyone to have the same number of strawberries. The number of strawberries must also be a multiple of $20$, as this is the only number that can be bought at a time. The least number of strawberries he would need to buy is thus $\text{LCM}(6,20)=\mathbf{30}$. The information about the chocolates and the bananas is not needed to solve the problem.
Exercise 12
There are $8$ horses: horse $1$, horse $2$, … horse $8$. The number in the name corresponds to the number of minutes it takes for the horse to run around the same circular path. All horses begin running at the same time on the starting line and they continue to run around the track at the same speed.
What is the shortest time (in minutes) after the start when at least six horses are back on the starting line again?
The shortest time it will take for all eight horses to get back to the starting line is the least common multiple of $1, 2, 3 \dots 8$, which is $2^3 \cdot 3 $$\cdot 5 \cdot 7$. We now want to remove two horses from the starting line to make the LCM for the six remaining horses as small as possible. The best choice we can make is to remove horses $5$ and $7$, which will reduce the least common multiple to $2^3 \cdot3=24$. (The multiple will not decrease at all if we remove one of the horses $1, 2, 3, 4$ or $6$, and if we remove horse $8$ it will only decrease the LCM by a factor of $2$). The shortest time after the start when at least six horses are back on the starting line is thus $\mathbf{24}$ minutes
Exercise 13
Simon is blowing balloons for a birthday party. The balloons have one of the colors blue, yellow or pink. He plans to create six clusters of balloons so that each color is evenly spread out over all six clusters. If Simon has five times as many yellow balloons as blue, and half as many pink balloons as yellow, what is the least number of balloons he can have?
Since Simon has five times as many yellow balloons as blue, the number of yellow balloons must be a multiple of $5$. There should also be half as many pink balloons as there are yellow, which is only possible if the number of yellow balloons is also a multiple of $2$. The number of yellow balloons must therefore be divisible by both $5$ and $2$, which is the same as being a multiple of $10$. If there are $10x$ yellow balloons, then there are $2x$ blue and $5x$ pink balloons.
Simon wants to divide the balloons into six clusters. This is only possible if the number of balloons of each color is a multiple of $6$. The number of pink balloons will only be a multiple of $6$ if $x$ is a multiple of $6$.
The smallest number that $x$ can be is thus $6$, so the least number of balloons that Simon can have is $2 \cdot6 + 10 \cdot 6$$ + 5 \cdot6 =$$ 12 + 60 + 30 =$$ \mathbf{102}$. Each of the six clusters then has $2$ blue, $10$ yellow and $5$ pink balloons.
Exercise 14
Show that
$$ \text{GCF}(a, b) \ \cdot \ \text{LCM}(a, b) = ab$$
for all integers $a$ and $b$.
To determine the GCF of two numbers, we first prime factorise them, compare the exponents for each prime factor, and then pick the smaller of the two exponents for each prime.
To determine the LCM of two numbers, we again prime factorise them, compare the exponents for each prime factor, and then pick the larger of the two exponents for each prime.
For example, let’s say that one of the numbers contained the factor $2^3$ and the other contained the factor $2^5$. Then we would pick $2^3$ for the GCF and $2^5$ for the LCM. If both numbers had the same exponent, say $2^4$, we will still pick one for the GCF and one for the LCM.
This means every factor in the numbers will be either in the GCF or the LCM, so the product of the GCF and the LCM must therefore equal the product of both numbers.
This question can also be proven with the same reasoning using algebra. Let $p$ be a prime number that exists $m$ times in the number $a$ and $n$ times in the number $b$. (It is possible that $m$ or $n$ is $0$, so that $p$ does not exist at all in $a$ or $b $). This means that $a$ is divisible by $p^m$, $b$ is divisible by $p^n$ and their product $ab$ is divisible by $p^m \cdot p^n =$$ p^{m + n}$.
Let $n$ be greater than or equal to $m$. Since $n$ is the greatest exponent, $p^n$ will always be found in $\text{LCM}(a, b)$, and $p^m$ will always be found in $\text{GCF}(a, b)$.
$ \text{GCF}(a, b) \cdot \text{LCM}(a, b) = ab $
$ \ \ \ \ \ \ p^m$ $ \cdot$ $p^n$ $=$ $p^{m + n}$
This reasoning applies to all prime numbers $p$. All prime factors in $ab$ are thus found in either the GCF or the LCM, so the sides of the equation must therefore be equal.
Exercise 15
The difference between two integers is $31$ and their product is $2112$. What are the two numbers?
We begin as usual with the prime factoring $2112=2^6 \cdot3 \cdot11$. Note that the difference between our numbers is odd. This means that one number must be even and the other must be odd. An odd number can’t contain any $2$s, so all six $2$s must be in the even number. If we let the even number be $2^6 = 64$ the odd number becomes $33$ and we reach the desired difference $64 - 33 = 31$.
However, we need to prove that there are no other combinations of positive integers whose difference is also $31$. This can be done that fairly easily. If we transfer a prime factor from the odd to the even number, the even number will be larger at the same time as the odd number will be smaller. The difference then becomes larger than $31$, and thus there are no other positive integers whose difference is $31$ and product is $2112$.
In this reasoning, we have assumed that both numbers are positive. But there was never anything in the question that they must be positive. The only restriction we had was that the numbers should be integers, so we need to investigate negative numbers as well. For the product to be positive, both numbers must be negative. We can use the same reasoning as in the above paragraph to show that one number must be a multiple of $2^6 = 64$ and that the only solution is if the numbers are $-33$ and $-64$, as all other combinations will create a difference that is either greater or less than $31$.
The two solutions to the problem are thus $\mathbf{(33,64)}$ and $\mathbf{(-33,-64)}$.