GCF And LCM — Determine GCF and LCM using factor structure.

Historical Context & Motivation

The concepts of greatest common factor (GCF) and least common multiple (LCM) trace their origins to the earliest systematic treatments of number theory. Ancient mathematicians recognized that understanding the internal structure of integers — specifically their divisors and multiples — was essential for solving problems in measurement, commerce, and astronomy. The factor structure approach, rooted in the Fundamental Theorem of Arithmetic, provides a deterministic and elegant method for computing both the GCF and LCM of any set of positive integers. On the GMAT, this framework is not merely academic — it is the backbone of a significant class of quantitative reasoning questions that test your ability to manipulate divisibility relationships under time pressure.

The central question this lesson addresses is deceptively simple: given two or more positive integers, how do we systematically determine their largest shared factor and their smallest shared multiple? While listing factors and multiples can work for small numbers, the prime factorization method provides a universal, efficient framework that scales to any pair of integers and — critically for the GMAT — reveals structural relationships that enable you to solve problems without brute-force computation.

Core Principles & Definitions

The factor structure approach to GCF and LCM rests on a small set of powerful ideas. Once internalized, these principles allow you to decompose any GCF/LCM problem into a mechanical procedure — one that is both fast and error-resistant. The conceptual core is the unique prime factorization of every positive integer greater than 1, which serves as a kind of "DNA" for that number, encoding all information about its divisors and multiples.

Visual Explanation — Venn Diagram of Prime Factors

The most intuitive way to visualize GCF and LCM is through a Venn diagram of prime factors. Consider two numbers — 360 and 756. Their prime factorizations are 2³ × 3² × 5 and 2² × 3³ × 7, respectively. The Venn diagram places shared prime bases (with their minimum exponents) in the intersection, and each number's "excess" primes in the outer regions. The GCF is the product of what lies in the intersection; the LCM is the product of everything in the entire diagram.

This diagram makes the min/max logic concrete. For each prime, the intersection captures the minimum exponent (what both numbers guarantee they share), while each outer region adds the "excess" exponent unique to that number. The LCM, by taking the maximum exponent, absorbs both the shared and excess factors. This visual framework is especially powerful on GMAT data sufficiency questions, where you must determine whether a given piece of information is sufficient to pin down the GCF or LCM without needing to compute the actual values.

Mathematical Framework

Let us formalize the procedure. Suppose two positive integers a and b have prime factorizations involving the primes p₁, p₂, …, pₖ (the union of all primes appearing in either factorization). We can write each number using every prime in this union, allowing zero exponents where a prime does not divide a given number.

Detailed Breakdown — Exponent Comparison Table

A systematic way to organize the computation is to build an exponent comparison table. This technique is especially useful when dealing with three or more numbers, or when a problem gives you partial prime factorization information and asks what you can deduce. The table lists every distinct prime along the rows and the exponent each number contributes along the columns. An additional column records the min (for GCF) and max (for LCM). Let us illustrate with a three-number example: find GCF(180, 252, 300) and LCM(180, 252, 300).

The exponent comparison table and flowchart together provide a complete, systematic procedure. The table is the workspace; the flowchart is the algorithm. For GMAT purposes, you will rarely encounter numbers requiring more than three or four distinct primes, so the table typically has just a few rows — making this approach extremely efficient on timed questions.

Worked Example — GMAT-Style Problem

Let us work through a representative GMAT-style problem from start to finish. Problem: Two gears rotate at constant speeds. Gear A completes a full revolution every 168 seconds, and Gear B completes a full revolution every 180 seconds. If both gears start at the same position simultaneously, after how many seconds will they first return to that position at the same time?

Method Comparison — Strengths & Limitations

The factor structure method is not the only approach to GCF and LCM. On the GMAT, recognizing which method to deploy — and when — is itself a strategic skill. The table below compares three common methods across key dimensions.

Connection to Advanced Number Theory & GMAT Patterns

The factor structure framework extends naturally into several advanced GMAT topics. Understanding these connections transforms isolated formulas into a coherent web of number-theoretic reasoning. The table below maps core GCF/LCM concepts to their advanced applications.

Looking beyond the GMAT, the lattice of divisors — where GCF and LCM serve as the meet and join operations — connects to abstract algebra and cryptography. RSA encryption, for instance, relies on the difficulty of prime factorization for large numbers, and the extended Euclidean algorithm (a generalization of the GCF algorithm) computes modular inverses central to public-key cryptography. While these topics are well beyond the GMAT's scope, understanding that GCF and LCM are gateway concepts to a rich mathematical landscape provides motivational context for mastery.

Practice Problems

Lesson Summary