How to Understand Number Theory

The direct answer: number theory is the branch of mathematics that studies the integers, especially properties of primes, divisibility, and remainders. It asks questions like which numbers divide which, how to find common factors, and what happens when you wrap counting around a fixed modulus. This guide covers the core ideas and the algorithms that make them useful.

Number Theory at a Glance

Divisibility and Primes

We say a divides b, written a | b, when b is a multiple of a with no remainder. For example, 3 divides 12 because 12 = 3 times 4.

A prime number is an integer greater than 1 whose only positive divisors are 1 and itself. The first few primes are 2, 3, 5, 7, 11, 13. The number 1 is not prime by definition, which keeps the unique factorization theorem clean. A composite number has divisors other than 1 and itself.

The Fundamental Theorem of Arithmetic

The Fundamental Theorem of Arithmetic states that every integer greater than 1 can be written as a product of primes in exactly one way, apart from the order of the factors. For example, 60 = 2 squared times 3 times 5, and no other prime factorization exists. This uniqueness is why prime factorization works as a kind of fingerprint for integers, a theme the Khan Academy number theory lessons return to Khan Academy.

Greatest Common Divisor

The greatest common divisor, gcd(a, b), is the largest integer that divides both a and b. For 12 and 18, the common divisors are 1, 2, 3, 6, so gcd(12, 18) = 6.

The gcd and lcm link

The least common multiple, lcm(a, b), is the smallest positive integer that both divide. For 4 and 6, the lcm is 12. These two are linked by:

gcd(a, b) times lcm(a, b) = a times b

So for 12 and 18, gcd is 6, lcm is (12 times 18) divided by 6 = 36, and 6 times 36 = 216 = 12 times 18. The formula is handy because once you have one, you have the other.

The Euclidean Algorithm

Finding the gcd by listing divisors works for small numbers but is slow for large ones. The Euclidean algorithm uses repeated division:

gcd(a, b) = gcd(b, a mod b)

Repeat until the remainder is 0; the last nonzero remainder is the gcd.

Worked example

gcd(48, 18): 48 = 18 times 2 + 12, so gcd(48, 18) = gcd(18, 12). 18 = 12 times 1 + 6, so gcd(18, 12) = gcd(12, 6). 12 = 6 times 2 + 0, so gcd(12, 6) = 6.

Thus gcd(48, 18) = 6.

This method is fast even for very large integers, which is why it underpins modern cryptography. Each step replaces a pair with a smaller pair, so the numbers shrink quickly instead of growing.

Modular Arithmetic

Modular arithmetic is counting with wrap around. We write a is congruent to b modulo n, written a is congruent to b (mod n), when a and b leave the same remainder after division by n. On a 12 hour clock, 14 is congruent to 2 (mod 12) because both point to 2.

Clocks and calendars

Modular arithmetic is not abstract. A 12 hour clock is arithmetic modulo 12: 9 plus 5 = 14 is congruent to 2, which is why the hand lands on 2. Days of the week are modulo 7, so if today is Wednesday (day 3 if Sunday is 0) and an event is 10 days away, 3 + 10 = 13 is congruent to 6, or Saturday. The same wrap around governs computer hash functions and checksums, where a number is reduced modulo a fixed size to fit inside a table. Knowing the remainder rule lets you predict the result without counting all the way around.

Useful facts

• If a is congruent to b (mod n) and c is congruent to d (mod n), then a + c is congruent to b + d (mod n).
• Likewise a times c is congruent to b times d (mod n).
• You can reduce intermediate numbers modulo n to keep calculations small.

A small example: what is 17 times 23 modulo 5? Reduce first: 17 is congruent to 2 (mod 5) and 23 is congruent to 3 (mod 5). Then 2 times 3 = 6 is congruent to 1 (mod 5). So the answer is 1.

Why It Matters

Number theory once seemed like pure curiosity. Today it is the backbone of public key cryptography, the system that secures online communication. The difficulty of factoring large numbers into primes is what makes certain encryption hard to break. The Euclidean algorithm and modular arithmetic are the exact tools behind how keys are generated and how messages are scrambled and unscrambled.

Quick Divisibility Checks

A handful of tests let you spot factors without dividing, which speeds up factorization and gcd work.

The standard tricks

• A number is divisible by 2 if its last digit is even.
• It is divisible by 3 if the sum of its digits is divisible by 3.
• It is divisible by 5 if it ends in 0 or 5.
• It is divisible by 9 if the sum of its digits is divisible by 9.
• It is divisible by 10 if it ends in 0.

These come from how our base 10 system interacts with modular arithmetic. For example, 10 is congruent to 1 (mod 3), so every power of 10 is also congruent to 1 (mod 3), which is why digit sums decide divisibility by 3. The same reasoning gives checks for 11 using alternating digit sums.

Why factorization matters in practice

Factoring 60 into 2 squared times 3 times 5 tells you at a glance its divisors, its gcd with any other number, and whether it is a perfect square (it is not, because the prime exponents are not all even). This is the daily payoff of the Fundamental Theorem of Arithmetic, and it is the step that makes matrices determinants and polynomial factoring easier later, since all three rest on pulling numbers or expressions into irreducible pieces.

Fermat's Little Theorem

A result that connects the ideas above to cryptography is Fermat's little theorem. If p is prime and a is any integer not divisible by p, then a to the (p minus 1) is congruent to 1 (mod p).

Why it matters

Try a = 2, p = 7: 2 to the 6 = 64, and 64 mod 7 = 1, because 63 is divisible by 7. The theorem gives a quick necessary condition for primality and underpins the math behind public key systems. A number that fails the congruence cannot be prime, which is one way computers weed out composite candidates before the expensive step of factoring. It is a neat payoff for the modular arithmetic section: the same wrap around counting that feels like clock arithmetic is what locks your messages.

Common Misconceptions

• Calling 1 a prime number; it is excluded by definition.
• Thinking a larger number always has more prime factors; not necessarily.
• Mixing up gcd and lcm. The gcd is the largest shared divisor, the lcm the smallest shared multiple.
• Forgetting that congruence respects addition and multiplication but not division in general.
• Trying to factor huge numbers by hand instead of using the Euclidean algorithm for the gcd.
• Believing number theory is only for contests. It runs the security behind everyday logins and payments.

Frequently Asked Questions

Is 0 a prime or composite number?

Neither. Primes and composites are defined for integers greater than 1, so 0 is outside both categories.

What does "mod" mean in plain terms?

It is the remainder after division. "a mod n" is what is left when you divide a by n.

Why is unique factorization important?

It guarantees that prime factorization is a reliable fingerprint for an integer, which many proofs and algorithms depend on.

How do I find the gcd of big numbers?

Use the Euclidean algorithm with repeated remainders rather than listing divisors.

Does number theory show up on standardized tests?

Some algebra and contest problems use divisibility and modular reasoning. The basics also support matrices and computer science courses.

What is a good first proof to learn?

That there are infinitely many primes, shown by assuming a finite list and constructing one more. It is short and uses only the tools above.

Sources

• Khan Academy, cryptography and ciphers
• Wolfram MathWorld, number theory