Basic Number Theory

Not sure you’re ready?

Take the ~3-minute readiness diagnostic and see where you stand.

Mathematics begins with the observation that numbers are not merely isolated, arbitrary quantities, but precise structures built from elemental building blocks. Just as a physicist looks at a complex molecule and asks what atoms comprise it, a mathematician looks at a number and asks what elemental numbers multiply together to form it. Basic number theory is the study of this underlying architecture. By understanding how numbers break down into fundamental units and how they scale infinitely upward, we reveal the hidden patterns governing everything from elementary arithmetic to modern cryptographic security.

To understand the nature of numbers, we must first categorize them by their structural integrity. We divide whole numbers into two primary categories based on how they can be divided.

A prime number is a whole number greater than 1 that has exactly two distinct positive divisors.

Those two distinct positive divisors of a prime number are the number 1 and the prime number itself. Because they cannot be broken down any further through division, primes are the "atoms" of mathematics.

Unlike composite numbers, which can be geometrically arranged into uniform rectangles based on their multiple factors, prime numbers have exactly two factors and can only be arranged in a single linear row.

Conversely, a composite number is a whole number greater than 1 that has more than two positive divisors.

A composite number is like a molecule; it is formed by binding together smaller, elemental prime numbers through multiplication.

When observing the landscape of numbers, two particular numbers require special classification: 0 and 1.

The number 0 is neither a prime number nor a composite number. It cannot be divided in a meaningful way that yields a finite set of divisors, nor does it build other numbers through multiplication (as multiplying by zero always yields zero).
The number 1 is neither a prime number nor a composite number. For a number to be prime, it must have exactly two distinct positive divisors. The number 1 only has a single divisor (itself). If we allowed 1 to be prime, the entire foundation of unique factorization would collapse.

The Landscape of Primes

If we begin counting upward, the first true building block we encounter is the number 2. The number 2 is the smallest prime number. It is profoundly unique in the mathematical universe because the number 2 is the only even prime number.

By definition, an even number is divisible by 2. Therefore, every even whole number greater than 2 is a composite number, because it will inherently possess at least three divisors: 1, itself, and 2.

Because primes are the building blocks of all other numbers, familiarizing yourself with the earliest primes is essential for fluent arithmetic. The prime numbers less than 20 are 2, 3, 5, 7, 11, 13, 17, and 19.

The Sieve of Eratosthenes is an ancient visual algorithm used to identify prime numbers. It works by systematically finding the first unmarked number and eliminating all of its subsequent multiples, leaving only the primes.

Furthermore, if you take any two of these elemental building blocks and multiply them, the result fundamentally changes state. The mathematical product of any two prime numbers is always a composite number. For instance, multiplying the prime 3 by the prime 5 yields 15, which is composite because it is divisible by 1, 3, 5, and 15.

When we analyze how numbers interact, we look in two directions: inward (division) and outward (multiplication). This brings us to factors and multiples.

Looking Inward: Factors

A factor is a whole number that divides exactly into another whole number without leaving a remainder.

When you are finding factors, you are digging into the earth beneath the number to find its foundation. Because every number divides evenly by 1, the number 1 is a factor of every whole number. Similarly, because any number divides evenly into itself (yielding 1), every whole number greater than zero is a factor of itself.

Because you cannot divide a number by an integer larger than itself and still yield a whole number, you are constrained. Therefore, any specific whole number has a finite quantity of factors. The factors of 12, for example, are strictly limited to the finite set {1, 2, 3, 4, 6, 12}.

A visual representation of the finite factors of the composite number 10. The quantities of 1, 2, 5, and 10 are the only whole numbers that can divide perfectly into the total without leaving a remainder.

Looking Outward: Multiples

A multiple is the product of a given whole number and any other whole number.

If factors are the bricks that build a wall, multiples are the infinite shadows that wall casts as it scales upward. To find the multiples of 5, you multiply 5 by 1, by 2, by 3, and so on (yielding 5, 10, 15...).

Because multiplying any number by 1 yields the original number, every whole number is a multiple of itself. And because the sequence of whole numbers we can multiply by stretches on forever, every whole number greater than zero has an infinite quantity of multiples.

The most beautiful and powerful realization in basic number theory is that every composite number is merely a unique combination of prime numbers in disguise.

The Fundamental Theorem of Arithmetic states that every composite number can be uniquely expressed as a product of prime numbers.

This theorem guarantees that every composite number has an absolute, immutable "DNA sequence" of primes. No two distinct composite numbers share the same prime factorization, and a composite number can only be broken down into primes in exactly one way (ignoring the order of the primes).

To uncover this sequence, we use a specific analytical method:

Prime factorization is the mathematical process of expressing a composite number as the product of prime numbers.

To perform this process systematically, mathematicians often rely on a visual heuristic. A factor tree is a visual diagram used to break down a composite number into the composite number's prime factors.

Imagine breaking down the number 60:

We might split 60 into branches of 6 and 10 (since $6 \times 10 = 60$ ). Neither is prime.
We break the 6 into branches of 2 and 3. Both 2 and 3 are prime. The branches stop.
We break the 10 into branches of 2 and 5. Both 2 and 5 are prime. The branches stop.
Gathering our prime "leaves" at the ends of the branches, the unique prime factorization of 60 is $2 \times 2 \times 3 \times 5$ (or $2^2 \times 3 \times 5$ ).

A divisibility lattice for the number 60, mapping all of its interconnected factors. The foundational prime factors (2, 3, and 5) sit at the base, multiplying in different combinations to uniquely create all the composite factors above.

Finding factors and primes requires us to test numbers for divisibility. Rather than performing long division for every candidate, mathematicians rely on algebraic properties of our base-10 number system to create elegant shortcuts. Memorizing these divisibility rules allows you to instantly recognize the structural components of large numbers.

Divisor	Divisibility Rule	Example
2	A whole number is divisible by 2 if the number's final digit is 0, 2, 4, 6, or 8.	4,138 ends in 8. It is divisible by 2.
3	A whole number is divisible by 3 if the sum of the number's digits is a multiple of 3.	For 411: $4+1+1 = 6$ . Since 6 is a multiple of 3, 411 is divisible by 3.
4	A whole number is divisible by 4 if the two-digit number formed by the final two digits is a multiple of 4.	5,124: The final digits form 24. Since 24 is a multiple of 4, 5,124 is divisible by 4.
5	A whole number is divisible by 5 if the number's final digit is exactly 0 or 5.	8,905 ends in 5. It is divisible by 5.
6	A whole number is divisible by 6 if the number is simultaneously divisible by the number 2 and the number 3.	114: Ends in 4 (divisible by 2). Digits sum to 6 (divisible by 3). Therefore, divisible by 6.
9	A whole number is divisible by 9 if the sum of the number's digits is a multiple of 9.	For 8,154: $8+1+5+4 = 18$ . Since 18 is a multiple of 9, 8,154 is divisible by 9.
10	A whole number is divisible by 10 if the number's final digit is exactly 0.	9,430 ends in exactly 0. It is divisible by 10.

These rules are not arbitrary magic tricks; they are direct consequences of place value arithmetic. For example, because 100 is perfectly divisible by 4, any hundreds, thousands, or millions place will also be divisible by 4. Thus, you only ever need to check the last two digits (the tens and units) to see if the entire massive number is divisible by 4.

Number theory extends beyond isolated numbers; it explores the relationships between different numbers. By comparing the factors and multiples of multiple quantities, we can synchronize systems or simplify complex ratios.

The Greatest Common Factor (GCF)

The Greatest Common Factor is the largest whole number that divides evenly into two or more specified whole numbers.

Think of the GCF as the ultimate standardizing tool. If a carpenter has a plank of wood 24 inches long and another plank 36 inches long, and wants to cut both into the largest possible identical segments without wasting any wood, she must find the GCF.

Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24.
Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36. The greatest factor they share is 12.

The Greatest Common Factor has physical applications, such as finding the largest possible uniform square tile (12x12) that can perfectly cover a rectangular space measuring 24 by 60 without any gaps or overlapping.

The Least Common Multiple (LCM)

The Least Common Multiple is the smallest positive whole number that is a multiple of two or more specified whole numbers.

While the GCF is about cutting things down into shared elements, the LCM is about projecting sequences forward until they perfectly align. Think of two gears, or two planets orbiting a star. If Planet A orbits every 4 years, and Planet B orbits every 6 years, when will they next align? We look for the LCM.

Multiples of 4: 4, 8, 12, 16, 20...
Multiples of 6: 6, 12, 18, 24... The smallest positive multiple they share is 12. They will align in 12 years.

Relatively Prime Numbers

Occasionally, two composite numbers will share no common internal structure. Consider the numbers 8 and 15.

The prime factorization of 8 is $2 \times 2 \times 2$ .
The prime factorization of 15 is $3 \times 5$ .

They share absolutely no prime factors. When we list their standard divisors, the only factor they share is the universal factor, 1.

Two numbers are defined as relatively prime if the Greatest Common Factor of the two numbers is exactly 1.

In mechanical engineering, adjoining gears are often designed with relatively prime numbers of teeth (such as 13 and 21) so their Least Common Multiple is exceptionally high. This maximizes the time before the exact same teeth align again, evenly distributing physical wear.

Notice that neither 8 nor 15 are prime numbers themselves—they are both highly composite! Yet, relative to each other, they are mathematically isolated. This specific relationship is a foundational pillar of modern computer cryptography, where selecting massively large relatively prime numbers ensures that encrypted data remains secure against unauthorized division and decoding.

Modern public-key cryptography relies on the mathematical properties of massive relatively prime numbers to generate the complex locks and keys that secure digital communication worldwide.