From the earliest clay tablets in Mesopotamia to the silicon microchips powering modern cryptography, explore the complete four-thousand-year evolution of the Least Common Multiple. Click any section below to jump directly:
The Least Common Multiple isn't a modern invention — it's a concept that humans have been discovering, refining, and using for over four thousand years. From the mud-brick cities of Mesopotamia to the silicon chips inside your phone, the LCM has quietly shaped how we count, build, and compute.
In this article, we'll trace that history — the mistakes, the breakthroughs, and the brilliant minds who turned a practical tool for farmers and astronomers into a cornerstone of modern cryptography and computer science.
From the earliest clay tablets to modern microchips, here are the pivotal moments that shaped our understanding of the LCM.
Babylonian scribes used a base-60 (sexagesimal) number system to solve practical problems in astronomy, trade, and calendar work. To combine fractions or align lunar cycles, they needed common multiples — the earliest known use of the LCM concept.
Why base 60? It has many divisors (2, 3, 4, 5, 6, 10, 12, 15, 20, 30), making LCM calculations easier. That's why we still use 60 minutes in an hour and 360 degrees in a circle.
Egyptian scribes wrote fractions as sums of unit fractions (1/2, 1/3, 1/4, …). To add them, they had to find common denominators — which is exactly the LCM. The Rhind Mathematical Papyrus contains several such problems.
Euclid described the famous Euclidean algorithm for finding the Greatest Common Divisor. Because LCM(a, b) = a × b ÷ GCD(a, b), this gave mathematicians a fast and elegant way to compute LCMs — over two thousand years before computers existed.
Euclid also proved that every integer has a unique prime factorization, which is the foundation of the modern LCM formula.
Chinese mathematicians compiled a comprehensive work describing methods for reducing fractions using common denominators — essentially LCM by another name. This text would inspire centuries of Chinese mathematical innovation.
Chinese mathematician Sun Zi posed a puzzle: "Find a number that leaves remainder 2 when divided by 3, remainder 3 when divided by 5, and remainder 2 when divided by 7." The solution used LCM concepts — and would eventually become the basis for modern cryptography.
Indian mathematician Aryabhata developed systematic methods for working with fractions and divisibility. His work on the kuttaka method for solving Diophantine equations relied on reasoning closely tied to the LCM.
Brahmagupta advanced Indian arithmetic significantly, giving rules for zero, negative numbers, and — critically — systematic methods for finding common multiples. His work influenced mathematics across the Islamic world and Europe.
Persian mathematician Al-Khwarizmi (whose name gives us the word "algorithm") systematized arithmetic and algebra. His books introduced Indian numerals and methods to Europe, including techniques for LCM and GCD computations.
Leonardo of Pisa (Fibonacci) introduced the Hindu-Arabic numeral system to Europe in his book Liber Abaci. He included practical LCM problems for merchants — calculating when different trading cycles would coincide.
Euler formalized much of modern number theory, including deeper results about divisibility and prime factorization. His work laid the foundation for using LCM in rigorous mathematical proofs.
Carl Friedrich Gauss wrote the foundational text of modern number theory. His systematic treatment of congruences and the Chinese Remainder Theorem formalized LCM's role in modular arithmetic — critical for today's cryptography.
Rivest, Shamir, and Adleman developed the RSA encryption algorithm, which uses LCM (indirectly, via the totient function) to generate public and private keys. Every secure website visit today relies on this mathematics.
LCM appears throughout computer science: distributed systems use it for clock synchronization, hash tables use it for sizing, task schedulers use it to align periodic events, and rate limiters use it for traffic shaping.
Over four thousand years ago, in the fertile crescent between the Tigris and Euphrates rivers, Babylonian mathematicians were already solving problems that required common multiples.
The Babylonians used a sexagesimal (base-60) number system. This wasn't arbitrary — 60 has many divisors (1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60), making it easy to work with fractions and to find common multiples.
A stylized illustration of how Babylonian scribes would record common multiple calculations using cuneiform script on a clay tablet.
Around 300 BCE, the Greek mathematician Euclid wrote his masterwork, Elements — arguably the most influential mathematics textbook ever written. Hidden within it was the algorithm that would become the backbone of modern LCM calculation.
Euclid wanted to find the Greatest Common Divisor (GCD) of two numbers. His method — repeatedly dividing and taking remainders — is still one of the fastest algorithms known today.
Now, here's the crucial insight: since LCM(a, b) × GCD(a, b) = a × b, we can find the LCM quickly once we know the GCD.
Euclid's algorithm is so efficient that it's still used in modern computers today. It's a perfect example of how a 2,300-year-old idea remains at the cutting edge of technology.
While Greek mathematicians were formalizing the theory of divisibility, scholars in China and India were developing sophisticated techniques for solving real-world problems using common multiples.
Sun Zi, a Chinese mathematician, posed a famous puzzle:
The solution is 23 — and the method used to find it is now called the Chinese Remainder Theorem. It generalizes to any system of congruences where the moduli are pairwise coprime.
Why is this important? Because 1,600 years later, the Chinese Remainder Theorem would become a foundational tool in RSA cryptography, secure multi-party computation, and error-correcting codes.
Around the same era, Indian mathematicians were developing their own sophisticated methods. Aryabhata (c. 500 CE) and Brahmagupta (c. 628 CE) worked on fraction arithmetic, divisibility, and the kuttaka method for solving linear Diophantine equations — all of which relied on the concept of common multiples.
| Civilization | Key Contribution | Approximate Date |
|---|---|---|
| Babylonian | Base-60 arithmetic with common multiples for astronomy | c. 2000 BCE |
| Egyptian | LCM reasoning in fraction tables (Rhind Papyrus) | c. 1650 BCE |
| Greek (Euclid) | Euclidean algorithm for GCD → LCM | c. 300 BCE |
| Chinese | Chinese Remainder Theorem and Nine Chapters | c. 200–400 CE |
| Indian | Kuttaka method, systematic fraction arithmetic | c. 500–628 CE |
| Islamic | Algebra, decimal system transmission | c. 820 CE |
| European | Liber Abaci, modern number theory | 1202 CE → 1801 CE |
By the 20th century, LCM had moved from clay tablets and parchment to paper and, finally, silicon. Today, LCM runs silently inside nearly every computing device you own.
A visual map of where the LCM algorithm is used today — from the browser on your phone to global internet infrastructure.
Every time you visit an https:// website, your browser performs LCM-based calculations. RSA key generation uses the totient function, which relies on LCM properties of prime numbers.
In a distributed system, different nodes might run tasks on different schedules (say, every 6 and every 8 milliseconds). The system uses LCM(6, 8) = 24 to know when both tasks will fire simultaneously — critical for maintaining consistency.
When you set up a cron job to run "every 15 minutes" and another to run "every 20 minutes," the system uses LCM(15, 20) = 60 to know how often they overlap.
Audio and video streams often have different frame rates. Synchronization algorithms use LCM to find the smallest time window where both streams align perfectly.
Choosing the right size for a hash table involves LCM reasoning — sizes that are powers of two or prime avoid predictable patterns that would cause clustering.
The four-thousand-year journey of the LCM reveals something profound about how mathematics develops.
The story of the LCM is far from over. As computing moves into quantum territory and cryptography evolves to defend against quantum attacks, new applications for LCM will emerge.
Post-quantum cryptography already uses lattice-based algorithms that rely on LCM-like reasoning. Quantum computing research involves modular arithmetic, which builds on the same foundations laid by Euclid, Sun Zi, and Gauss.
The next time you compute LCM(12, 18) = 36 in a math problem, remember: you're participating in a tradition that stretches back to Babylonian astronomers watching the stars, Greek philosophers writing on papyrus, and Chinese scholars solving puzzles by candlelight. The math hasn't changed — but the world it powers has.
No single person invented the LCM — it emerged independently across several ancient civilizations. Babylonian mathematicians were using common multiples over 4,000 years ago. Egyptian scribes needed common denominators for fractions around 1650 BCE. Euclid formalized algorithms for GCD (and therefore LCM) around 300 BCE.
Babylonian scribes used their base-60 sexagesimal system to solve problems in astronomy, calendar work, and trade. To predict when celestial cycles would align or when shipments would arrive together, they needed common multiples — the earliest known LCM calculations.
Euclid's Elements (c. 300 BCE) described the Euclidean algorithm for finding the GCD. Because LCM(a, b) = a × b ÷ GCD(a, b), this gave mathematicians a fast and elegant way to compute LCMs — an approach still used in modern computers.
Posed by Chinese mathematician Sun Zi around 400 CE, the Chinese Remainder Theorem describes how to reconstruct a number from its remainders modulo several pairwise coprime numbers. It's now used in RSA cryptography, error-correcting codes, and secure multi-party computation.
LCM appears throughout modern computer science: in cryptography (via RSA and the Chinese Remainder Theorem), distributed systems (clock synchronization), hash table sizing, task scheduling (aligning periodic events), and audio/video synchronization.
Euclid's algorithm is extremely efficient — it runs in O(log min(a, b)) time, meaning it can handle numbers with thousands of digits in milliseconds. It's also simple to implement, which makes it ideal for cryptographic systems that need to run quickly and securely.