Popular Courses
Beginner – Linear Regression
Introduction
Beginner – Decision Trees
Introduction
Beginner – Neural Networks
Introduction

Sign in to Curvingo

or

New Account     Reset Password     

Plans

Details
Real Numbers
Introduction
The Fundamental Theorem of Arithmetic
HCF and LCM, the Prime Way
Practice: Factors, HCF and LCM
Revisiting Irrational Numbers
Practice: Proving Irrationality
Summary
Curvingo · Made in India

Share

Send us Feedback

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

This will delete your progress and chat data for all chapters in this course, and cannot be undone!

Glossary

Select one of the keywords on the left…

Real NumbersThe Fundamental Theorem of Arithmetic

Reading time: ~20 min

If primes are atoms, we should be able to build other numbers from them just by multiplying. Pick any primes you like — repeats allowed — and multiply:

7 \times 11 \times 23 = 1771

2^3 \times 3 \times 7^3 = 8232

2 \times 3 \times 7 \times 11 \times 23 = 10626

There are primes, so this factory can turn out an endless supply of numbers. But here is the real question: can it build every composite number? Let's find out by running the factory towards a target.

Tap primes to multiply them together until you hit each target exactly.

One Number, Many Trees

Going the other way — from a number back to its primes — is called factorising. A factor tree does it one split at a time: break the number into any two factors, then keep breaking every branch until only primes are left. The primes are the leaves of the tree.

Below is the tree for 32760 that peels off the smallest prime at each step. But you are free to split in any order you like!

Grow at least three different trees — for 32760 or the other numbers — and compare the leaves.

The branches changed every time, but the leaves . For 32760 we always end up with 2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 \times 13, which we write more compactly as 32760 = 2^3 \times 3^2 \times 5 \times 7 \times 13. Even a giant like 123456789 behaves the same way: it is 3^2 \times 3607 \times 3803 (and yes, 3607 and 3803 are both primes).

What you have just seen is a conjecture — a pattern we believe is always true: every composite number can be broken into primes, and always into the same primes. Mathematicians have proved it, and it is so important that it has a grand name.

Theorem 1.1 (Fundamental Theorem of Arithmetic): Every composite number can be expressed (factorised) as a product of primes, and this factorisation is unique, apart from the order in which the prime factors occur.

The theorem makes two promises:

  1. Existence — every composite number can be written as a product of primes. The prime factory can build anything.
  2. Uniqueness — there is only way to do it. We don't count a change of order: 2 \times 3 \times 5 \times 7 and 7 \times 5 \times 3 \times 2 are the same factorisation.

A 2,000-year-old idea

A version of this theorem appears in Euclid's Elements (Book IX, Proposition 14), written around 300 BCE. But the first complete proof came only in 1801, from the German mathematician Carl Friedrich Gauss, in his book Disquisitiones Arithmeticae.

A Number's Prime Fingerprint

Uniqueness means that a prime factorisation works like a fingerprint: every number has exactly one, and no two numbers share the same one. So that fingerprints are easy to compare, we always write the primes in order and group repeated primes into powers — for example 360 = 2^3 \times 3^2 \times 5.

Drag the number ${n} to see its fingerprint.

Challenge: find the smallest number whose fingerprint uses three different primes.

Can a Power of 4 End in Zero?

A fingerprint does more than identify a number — it can also tell you about the number's digits. Take some numbers that end in the digit 0 and look at their fingerprints:

Every one of them contains . That is no accident: a number ends in 0 exactly when it is a multiple of 10, and 10 = 2 × 5 — so the pair 2 × 5 must be in its fingerprint.

Now turn the idea around. The powers of 4 — 4, 16, 64, 256, … — grow very fast. Will one of them ever end in 0? Let's experiment. Drag n = ${n}.

However far you go, the last digit is only ever 4 or 6. But an experiment is not a proof — maybe a zero appears at n = 1000? The Fundamental Theorem settles the question for every n at once.

Example 1: Consider the numbers 4^n, where n is a natural number. Check whether there is any value of n for which 4^n ends with the digit zero.

Solution: A number that ends in 0 is a multiple of 10 = 2 \times 5, so its prime factorisation would have to contain the prime . But 4^n = (2^2)^n = 2^{2n}, so the only prime in its factorisation is . By the uniqueness part of the Fundamental Theorem, no other prime can sneak in. So there is natural number n for which 4^n ends with the digit zero.

Now use the same idea yourself. To end in 0, a number's fingerprint needs both a 2 and a 5.

Drag each power into the right bucket.

20n
6n
10n
25n
15n
30n
12n
Always ends in 0
Never ends in 0

Counting zeros

Every zero at the end of a number comes from one 2 × 5 pair in its fingerprint. For example, 2^3 \times 5^2 = 200 has only two such pairs (there are three 2s but only two 5s), so it ends in exactly zeros.

Sina