The Fundamental Theorem of Arithmetic

We have seen that any natural number can be written as a product of its prime factors. For instance,

2 = 2,

4 = 2 × 2,

253 = × .(Fill the answers in ascending order only).

Now, let’s flip the question: Can every natural number be created by multiplying prime numbers?.

Pick any natural number, let us say 44, if we factorize it with just primes we get

44= x x .(Fill the answers in ascending order only).

What about 1771 ?

1771 = x x . (Fill the answers in ascending order only).

Building Numbers Using Prime Factors

Take any collection of prime numbers, say 2, 3, 7, 11 and 23. If we multiply some or all of these numbers, allowing them to repeat as many times as we wish, we can produce a large collection of positive integers (In fact, infinitely many). Let us list a few :

7 × 11 × 23 =

3 × 7 × 11 × 23 =

2 × 3 × 7 × 11 × 23 =

23 × 3 × 73 =

22 × 3 × 7 × 11 × 23 =

As you can see, combining primes in different ways creates new numbers. But here’s the big question: If we include all possible prime numbers, can we generate every natural number?

The Infinitude of Primes

There are infinitely many prime numbers, which means if we take all primes and combine them in every possible way, we can generate an infinite collection of numbers. This includes all primes and all possible products of primes.

But what about composite numbers? Can every composite number be expressed as a product of primes? Or could there exist a composite number that cannot be written this way? Let’s explore further.

We are going to use the factor tree with which we are all familiar. Let's take some large number, say, 32760 and factorise it as shown.

Note: You can enter any number of your choice in the input field below.If you are unable to see all the numbers then select the entire factorization tree and move.Do not move the individual element.

Please enter a number to find it's prime factors.

Upon factorised 32760 we get:

32760 = 2 × 2 × 2 × 3 × 3 × 5 × 7 × as a product of primes

i.e., 32760 = 23 × 32 × 5 × 7 × 13 as a product of powers of primes.

Once we have decided that the order will be ascending, then the way the number is factorised, is unique.

Let us try another number, say, 123456789.

This can be written as

32 × × .

We will also have to check if last two factors are primes or not! (Try it out for several other natural numbers using the above factorisation panel).

Upon trying out a variety of large numbers, we can see that every number can be written as the product of powers of . This statement is called the Fundamental Theorem of Arithmetic.

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.

This theorem is fundamental because it forms the backbone of understanding integers and their properties.

Why is This Important?

Prime factorization helps us:

1.Simplify fractions and find common factors.

2.Understand the nature of numbers in different fields of math.

3.Solve real-world problems like cryptography and computer algorithms.

An equivalent version of the above theorem was (probably) first recorded as "Proposition 14" of Book IX in Euclid’s Elements, before it came to be known as the Fundamental Theorem of Arithmetic.

However, the first correct proof was given by Carl Friedrich Gauss in his Disquisitiones Arithmeticae. Carl Friedrich Gauss is often referred to as the ‘Prince of Mathematicians’ and is considered one of the three greatest mathematicians of all time, along with Archimedes and Newton. He has made fundamental contributions to both mathematics and science.

Note: A composite number can be factorised as a of prime numbers in a ‘unique’way, except for the order in which the primes occur.

So, for example: we regard factorisation of 210 = 2 × 3 × 5 × 7 is same as writing 210 = 3 × 5 × 7 × 2 (or) any other possible order in which these primes are written.

This fact is also stated in the following form:

The prime factorisation of a natural number is , except for the order of its factors.

So now that you’ve seen the power of prime numbers, let’s use this theorem to uncover more mysteries hidden in the world of numbers!

In general, given a composite number x, we factorise it as x = p1 p2 ... pn , where p1, p2, ... pn are primes and written in ascending order, i.e., p1 ≤ p2 ≤. . . ≤ pn . If we combine the same primes, we will get powers of primes.The fundamental theorem also has a solved proof. Interested students can check it out at Proof of Fundamental Theorem of Arithmetic.

For example, 32760 = 2 × 2 × 2 × 3 × 3 × 5 × 7 × 13

= 23× 32× 5 × 7 × 13

Once we have decided that the order will be ascending, then the way the number is factorised, is unique.

Since the theorem is proved, it means that it will always hold in the world of mathematics. That means we can take this as fact and then build on top of it for more interesting conclusions.

For example, consider the numbers 4n, where n is a natural number. Is there is any value of n for which 4n ends with the digit zero? How do we begin to answer this question?

If the number 4n, for any n, were to end with the digit zero, then it would be divisible by the prime number .

That is, the prime factorisation of 4n would have to contain the prime 5. This is not possible because 4n=22n; so the only prime in the factorisation of 4n is .

So, the uniqueness of the Fundamental Theorem of Arithmetic guarantees that there are no other primes in the factorisation of 4n. So, there is natural number n for which 4n ends with the digit zero.

So, we took the uniqueness part of the theorem and applied it to quickly deduct the point that 4n will never end with zero for all n belongs to natural numbers.

Before moving forward, let's revise HCF and LCM.

S.No	Feature	LCM (Least Common Multiple)	HCF (Highest Common Factor)
1	Definition	The smallest number that is a multiple of two or more numbers	The largest number that divides two or more numbers without a remainder
2	Keywords	Common multiples; Least common; When will they meet again?	Common factors; Greatest common; Dividing evenly
3	Context	Synchronizing events (timing/schedules); Finding shared cycles or intervals; Combining sets of numbers	Dividing something into equal parts; Sharing items equally; Simplifying fractions or ratios
4	Usage	Scheduling tasks; Finding the least common time or number; Problem: "When will two bells ring together next?"	Dividing items or objects equally; Simplifying mathematical expressions; Problem: "What is the largest piece that can divide two ropes evenly?"
5	Example 1	Find LCM of 4 and 6: Multiples of 4: 4, 8, 12, 16... Multiples of 6: 6, 12, 18... LCM = 12	Find HCF of 12 and 15: Factors of 12: 1, 2, 3, 4, 6, 12 Factors of 15: 1, 3, 5, 15 HCF = 3
6	Example 2	Two traffic lights blink every 4 minutes and 6 minutes. When will they blink together? Answer: 12 minutes	What is the largest piece of wood that can evenly cut planks of 12 m and 15 m? Answer: 3 m
7	Formula	Prime factorization: Take the highest powers of all primes	Prime factorization: Take the lowest powers of all common primes
8	Key Concept	Multiples (focuses on numbers getting bigger)	Factors (focuses on dividing numbers into smaller parts)

HCF and LCM

We can now see that the prime factorization method actually uses the Fundamental Theorem of Arithmetic to gets its result.

Finding the HCF and LCM of 6 and 20

fill the answers in ascending order only

Prime factors of 6 = x

Prime factors of 20 = x x

i.e. 20 = 22 x 5

So HCF(6,20) = while LCM(6,20) =

HCF(6, 20) = 21 = Product of the smallest power of each common prime factor in the numbers.

LCM (6, 20) = 22×31×51 = Product of the greatest power of each prime factor involved in the numbers.

In the example above, we can see that HCF(6, 20) × LCM(6, 20) = x =

But 6 x 20 is also equal to 120.

It can be proven that for any two positive integers a,b:

HCF(a,b) x LCM(a,b) = a x b

This will easily enable us to find the HCF or the LCM if the other is given.

Find the HCF of 96 and 404 by the prime factorisation method. Hence, find their LCM.

The prime factorisation of 96 and 404 gives:

96 = × and 404 = ×

Therefore, the HCF of these two integers is 22= .

Now, if you need to find the LCM of 96 and 404 then we use the relationship:

HCF × LCM = Product of the numbers

So, LCM (96, 404) = 96x404HCF96,404 = 96x4044 =

Find the HCF and LCM of 6, 72 and 120, using the prime factorisation method.

We have : 6 = 2 × 3, 72 = × , 120 = × ×

Here, 21 and 31 are the smallest powers of the common factors 2 and 3, respectively.

So, HCF (6, 72, 120) = 21 × 31 = × =

23, 32 and 51 are the greatest powers of the prime factors 2, 3 and 5 respectively involved in the three numbers.

So, LCM (6, 72, 120) = 23 × 32 × 51 =

Remark: Notice, 6 × 72 × 120 HCF (6, 72, 120) × LCM (6, 72, 120). So, the product of three numbers is not equal to the product of their HCF and LCM.

Rational Numbers and Their Decimal Expansions

We have studied earlier that rational numbers have either a terminating decimal expansion or a non-terminating repeating decimal expansion. In this section, we are going to consider a rational number, say pq, q ≠ 0, and explore exactly when the decimal expansion of pq is terminating and when it is non-terminating repeating(or recurring).

To come up with some hypothesis we first start with some concrete examples. Let us take some decimals and convert them into pq form and see if we can identify some patterns.

0.375=3751000=375103

0.0875=87510000=875104

23.3456=23345610000=233456104

We can see a clear pattern. All the denominators are powers of .

If we want to rewrite 10 as a product of prime factors we can use the primes and .

Even though, we have worked only with a few examples, you can see that any real number which has a decimal expansion that terminates can be expressed as a rational number whose denominator is a power of 10. Also the only prime factors of 10 are 2 and 5. So, cancelling out the common factors between the numerator and the denominator, we find that this real number is a rational number of the form ,pq where the prime factorisation of q is of the form 2n5m, and n, m are some non-negative integers.

Formally we can define the theorem as:

Let x = pq be a rational number, such that the prime factorisation of q is of the form 2n·5m , where n, m are non-negative integers. Then x has a decimal expansion which terminates.

Now, if we consider any non terminating and recurring rational nu,bers like 1/7, 2/3, 7/11 etc we see that the denominators are not of the form 2n·5m.

Let x = p/q , where p and q are coprimes, be a rational number, such that the prime factorisation of q is not of the form 2n·5m , where n, m are non-negative integers. Then, x has a decimal expansion which is non-terminating repeating (recurring).

With the help of these theorems we can quickly find out if a rational number of the form p/q is terminating or non terminating. You can do so using the following steps.

1. Find out if q can be represented as a power of the prime factors 2 or 5.

2. If yes, its terminating. If not, it's non terminating.

For example, consider 3/8. Here 8 can be represented as 23. So it is terminating. We can chek it easily as below

38 =323=3·5323·53=375103= .

Some rational numbers have decimal expansions that do not terminate but instead repeat in a specific pattern. These are called non-terminating, recurring decimals.

Example: Decimal Expansion of 17
Let’s consider the fraction:

17 = 0.142857142857142857...

Here, the decimal expansion does not end but follows a repeating pattern of digits "142857". This repeating sequence continues indefinitely, making it a non-terminating, recurring decimal.

Why is 17 a Recurring Decimal?

The denominator 7 cannot be expressed as a power of 2 or 5 (i.e., in the form 2m x 5n).
Only fractions with denominators that are purely in the form of 2 and/or 5 produce terminating decimals.
Since 7 does not fit this rule, its decimal expansion must be and repeating**.

Chapter 1: Real Numbers

Glossary

The Fundamental Theorem of Arithmetic

HCF and LCM

Rational Numbers and Their Decimal Expansions

Sign in to Innings2

Chapter 1: Real Numbers

Reset Progress

Glossary

The Fundamental Theorem of Arithmetic

HCF and LCM

Rational Numbers and Their Decimal Expansions