Hill Climbing and Prime Factorization
When I first started cooking, I had an untrained palate. I would cook a dish, taste it, and think: “That’s not right.” But, since I wasn’t sure what was wrong with it, I didn’t know how to fix it. After making a random change, I would taste it again. Most of the time, the dish still tasted wrong — but was it better or worse than before? I had no idea. Over time, I learned to taste a dish and recognize: “Oh, that’s too sweet.” And if I keep training my palate, eventually I’ll just know: “Needs more acid.”
Playing around with recipes is safer and a lot more fun when your palate gives you the feedback you need to correct mistakes and refine flavors. Without that feedback, you are wandering blindly through the wilderness; with that feedback, you are in control and free to explore. Adjusting a dish by taste is a form of problem-solving known as hill climbing. We make a small change and taste the dish. If the dish tastes better, we keep heading in that direction; if not, we choose a new direction.
The goal is to keep improving the flavor of the dish — climbing uphill — until we reach the optimal solution.
As I was describing my interactive math app, Drawing Area, in Information-Processing, Microworlds, and Drawing Area, I was struck by how often my goal is to arm students with the feedback they need to solve problems by hill climbing. There is something powerful and confidence-building about using one’s own senses and judgment to work out a solution — instead of relying on someone else or arcane algorithms for answers. I want students to know that, if they get lost, they can always re-orient themselves and still find the top of the hill.
We can’t play if we don’t feel secure.
Confusing algorithms
When I was teaching middle school, seventh-graders were expected to learn two algorithms: one for finding the greatest common factor (GCF) and one for finding the least common multiple (LCM) of two numbers using prime factorization. Although the two algorithms are similar, you would never mix them up if you understood what you were doing.
Of course, students mixed them up all the time. The confusion was so bad, more than one school system elected to ignore the state standards and only teach one of the algorithms.
72 = 2³ × 3²96 = 2⁵ × 3¹Compare the exponents on the 2 and the exponents on the 3.To find the GCF of 72 and 96, choose the smaller exponents:
2³ × 3¹ = 24.To find the LCM of 72 and 96, choose the greater exponents:
2⁵ × 3² = 288.
Debating which algorithm to teach was depressing. We should have been investigating why students didn’t understand what they were doing, and then experimenting with new teaching strategies. But we are so used to students not understanding, we just take it for granted that there’s nothing we can do.
Identifying factors and multiples
Every whole number greater than 1 can be written as a product of one or more prime numbers. For example, 24 = 2 × 2 × 2 × 3. This product is known as the number’s prime factorization. We can use exponents to make our prime factorizations more compact: 24 = 2³ × 3¹.
We can tell if 6 is a factor of 24 by comparing their prime factorizations.
6 = 2 × 324 = 2 × 2 × 2 × 3
Because the prime factorization of 24 contains the prime factorization of 6, we can write 24 as the product of 6 and another whole number.
24 = 2 × 2 × 2 × 3 = (2 × 2) × (2 × 3) = 4 × 6This proves that 6 is a factor of 24 and 24 is a multiple of 6.
Hill climbing and GCF
To find the greatest common factor of 1620 and 2160, start by finding any common factor, no matter how small.
1620 = 2 × 2 × 3 × 3 × 3 × 3 × 52160 = 2 × 2 × 2 × 2 × 3 × 3 × 3 × 5
Since the prime factorizations of 1620 and 2160 both contain a 2, we know that 2 is a common factor—it’s a factor of both numbers.
Is there another prime factor we can add to the 2 that 1620 and 2160 both contain? We can add a second 2. The prime factorizations of 1620 and 2160 both contain 2 × 2, so 2 × 2 = 4 is another common factor, and it’s greater than 2.
Now we are hill climbing. We keep adding prime factors—finding greater and greater common factors—until it’s impossible to add any more. At that point, we have found the greatest common factor.
The GCF of 1620 and 2160 is 540. 540 = 2 × 2 × 3 × 3 × 3 × 51620 = (2 × 2 × 3 × 3 × 3 × 5) × (3) = 540 × 32160 = (2 × 2 × 3 × 3 × 3 × 5) × (2 × 2) = 540 × 4We know it is the greatest common factor because it is impossible to add another prime factor that 1620 and 2160 have in common.
Hill climbing and LCM
Finding the least common multiple of 1620 and 2160 works the same way.
Start by finding any common multiple, no matter how great. We know that 1620 × 2160 is a multiple of both 1620 and 2160, so let’s start there.
2 × 2 × 2 × 2 × 2 × 2 × 3 × 3 × 3 × 3 × 3 × 3 × 3 × 5 × 5 is a common multiple of 1620 and 2160—it contains the prime factorizations of both 1620 and 2160.
Is there a prime factor we can remove and still contain both prime factorizations? If we remove a 2, that leaves us with five 2's—and we only need two 2’s for 1620 and four 2’s for 2160.
By removing prime factors one at a time, we find smaller and smaller common multiples, until it is impossible to remove any more. At that point, we have found the least common multiple.
The LCM of 1620 and 2160 is 6480.6480 = 2 × 2 × 2 × 2 × 3 × 3 × 3 × 3 × 56480 = (2 × 2 × 3 × 3 × 3 × 3 × 5) × (2 × 2) = 1620 × 46480 = (2 × 2 × 2 × 2 × 3 × 3 × 3 × 5) × (3) = 2160 × 3We know it is the least common multiple because it is impossible to remove another prime factor and still contain 1620 and 2160.
From hill climbing to abstraction
Most students use hill climbing once or twice before figuring out more efficient strategies for finding the GCF or LCM by counting prime factors or comparing exponents. They end up deriving the same two algorithms, which so many students confuse, entirely on their own. When we’re secure and relaxed, our brains naturally look for patterns and shortcuts to make our lives easier.
But I don’t focus on hill climbing as an instructional designer because I want students to derive rules for themselves or to use alternative strategies. I focus on hill climbing because I want them to have the sense of security that comes from knowing they have the capability to figure stuff out on their own. When students derive a rule or an algorithm, it shouldn’t be a one-off; they should be able to reconstruct that rule or algorithm from their core understandings any time they need it—even years later.
Ground, scale, leverage
Vertical learners ground, scale, and leverage their understanding. The first step in that process—grounding—means drilling down until we make sense of something on a concrete and intuitive level, and it is fully integrated into our mental models.
Once we understand how to identify factors and multiples using prime factorization, hill climbing to find a GCF or LCM is incredibly concrete and intuitive. It just makes sense on a gut level. And once our understanding is securely grounded, scaling and leveraging that understanding in increasingly powerful and sophisticated ways is easy and natural. In fact, I would describe the process as playful.
Playing with factors and prime factorization
Here is a problem that most teachers would never assign, but my students handle easily. They actually think the problem is fun because they have the tools to reason it out on their own—applying core understandings that are concrete and intuitive for them.
211,680 = 2⁵ × 3³ × 5¹ × 7²987,840 = 2⁶ × 3² × 5¹ × 7³What is the greatest common factor of 211,680 and 987,840 that is also a square number?
To solve the problem, we need to know the definition of a square number.
A square number is a whole number that is a square of another whole number. If I can re-arrange the prime factorization of 15,876 into a product of two identical whole numbers, that proves 15,876 is a square number.
15,876 = 2 × 2 × 3 × 3 × 3 × 3 × 7 × 715,876 = (2 × 3 × 3 × 7) × (2 × 3 × 3 × 7) = 126 × 126 = 126²Can you tell that 15,876 is a square number before re-arranging its prime factors into two identical whole numbers?
Therefore, the greatest common factor of 211,680 and 987,840 that’s also a square number has a prime factorization that just fits inside of both 211,680 and 987,840, and can be re-arranged into a product of two identical whole numbers. We can solve this problem by hill climbing.
The understanding gap
I’m sure some people are wondering why we teach students to find greatest common factors and least common multiples in the first place. That’s an important question; but in my opinion, a much more important question is almost never asked.
We can’t make sense of the algorithms for finding a GCF and LCM unless we understand how to find factors and multiples using prime factorization first. So, why are we trying to teach students these two algorithms without ever showing them how to find factors and multiples? We are putting them in a position where their only option is to memorize the algorithms. That’s plain wrong. I’d even describe it as abusive.
And motivating students to memorize an algorithm by making it relevant to them—something they learn in the pursuit of a passion—is no less abusive.
Testing a prototype
To test some of my theories, I created an interactive online curriculum on using prime factorizations to find GCFs and LCMs. This is just a prototype, so the design is very unpolished. But I’d love any feedback and I hope you enjoy it. I’m working on an app based on the same concepts, but I’ve put it on the back burner for now.
