Introduction to Prime Factorization and the Least Common Multiple
What you'll learn to do: Use prime factorization to find the least common multiple of a number
Peter is exploring a new city, and he's getting around by train. There are three train lines that leave from the station closest to his hostel. One arrives every [latex]15[/latex] minutes, one arrives every [latex]12[/latex] minutes, and one arrives every [latex]9[/latex] minutes. If all the trains depart the station at the same time every morning, how long will it be before they're all at the station at the same time again? To find this out, you'll use prime factorization and find the least common multiple--we'll explore both of those concepts in this section. Before you get started in this module, try a few practice problems and review prior concepts.readiness quiz
1. If you missed this problem, review the following example.
Identify each number as prime or composite:
We can stop when we get to [latex]11[/latex] because the quotient [latex]\text{(7.545}\ldots\text{)}[/latex] is less than the divisor.
We did not find any prime numbers that are factors of [latex]83[/latex], so we know [latex]83[/latex] is prime.
2. Test each prime, in order, to see if it is a factor of [latex]77[/latex].
Since [latex]77[/latex] is divisible by [latex]7[/latex], we know it is not a prime number. It is composite.
- [latex]83[/latex]
- [latex]77[/latex]
Answer: Solution: 1. Test each prime, in order, to see if it is a factor of [latex]83[/latex] , starting with [latex]2[/latex], as shown. We will stop when the quotient is smaller than the divisor.
Prime | Test | Factor of [latex]83?[/latex] |
---|---|---|
[latex]2[/latex] | Last digit of [latex]83[/latex] is not [latex]0,2,4,6,\text{or}8[/latex]. | No. |
[latex]3[/latex] | [latex]8+3=11[/latex], and [latex]11[/latex] is not divisible by [latex]3[/latex]. | No. |
[latex]5[/latex] | The last digit of [latex]83[/latex] is not [latex]5[/latex] or [latex]0[/latex]. | No. |
[latex]7[/latex] | [latex]83\div 7=11.857\ldots[/latex] | No. |
[latex]11[/latex] | [latex]83\div 11=7.545\ldots[/latex] | No. |
Prime | Test | Factor of [latex]77?[/latex] |
---|---|---|
[latex]2[/latex] | Last digit is not [latex]0,2,4,6,\text{or }8[/latex]. | No. |
[latex]3[/latex] | [latex]7+7=14[/latex], and [latex]14[/latex] is not divisible by [latex]3[/latex]. | No. |
[latex]5[/latex] | the last digit is not [latex]5[/latex] or [latex]0[/latex]. | No. |
[latex]7[/latex] | [latex]77\div 11=7[/latex] | Yes. |
Contribute!
Did you have an idea for improving this content? We’d love your input.
Licenses & Attributions
CC licensed content, Shared previously
- Ex 1: Apply Divisibility Rules to a 4 Digit Number. Authored by: James Sousa (Mathispower4u.com). License: CC BY: Attribution.
- Train at a station. Authored by: harlock81. Located at: https://www.flickr.com/photos/harlock81/2470743749/. License: CC BY-SA: Attribution-ShareAlike.
- Question ID: 145433, 145411. Authored by: Alyson Day. License: CC BY: Attribution. License terms: IMathAS Community License CC-BY + GPL.
CC licensed content, Specific attribution
- Prealgebra. Provided by: OpenStax License: CC BY: Attribution. License terms: Download for free at http://cnx.org/contents/[email protected].