Fundamental Theorem of Arithmetic with Examples, Class 10

Mul­ti­ply­ing primes together#

Pick a few primes, say 2, 3, 7, 11 and 23, and mul­ti­ply them in dif­fer­ent com­bi­na­tions, let­ting a prime repeat as often as you like:

$$\begin{aligned} 7 \times 11 \times 23 &= 1771 \\ 3 \times 7 \times 11 \times 23 &= 5313 \\ 2 \times 3 \times 7 \times 11 \times 23 &= 10626 \\ 2^3 \times 3 \times 7^3 &= 8232 \\ 2^2 \times 3 \times 7 \times 11 \times 23 &= 21252 \end{aligned}$$

Each result is a new com­pos­ite num­ber built entirely from primes. Since there are infi­nitely many primes, you could build infi­nitely many com­pos­ite num­bers this way.

Now turn the ques­tion round. Given any com­pos­ite num­ber, can we always break it back down into primes? And could two dif­fer­ent sets of primes ever give the same num­ber?

Break­ing num­bers back down: the fac­tor tree#

Why the break­ing down always stops#

Take any com­pos­ite num­ber and split it into two smaller fac­tors, each greater than 1. If either fac­tor is com­pos­ite, split it again. Every split pro­duces strictly smaller num­bers, and whole num­bers greater than 1 can­not keep get­ting smaller for ever, so the process must stop. It can only stop when every piece is prime. So every com­pos­ite num­ber is a prod­uct of primes.

Method: prime fac­tori­sa­tion by repeated divi­sion#

1. Divide the num­ber by the small­est prime that divides it exactly (try 2, then 3, then 5, and so on).
2. Repeat with the quo­tient, using the same prime as long as it still divides.
3. Stop when the quo­tient is itself a prime.
4. Write the num­ber as the prod­uct of all the primes used, group­ing repeats as pow­ers.

Exam­ple 1: fac­toris­ing 32760#

Pull out a 2 to leave 16380, another 2 to leave 8190, and a third 2 to leave 4095, which is odd, so the 2s are fin­ished. Pull out a 3 to leave 1365, another 3 to leave 455, then a 5 to leave 91. Finally $91 = 7 \times 13$, and both are prime.

$$32760 = 2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 \times 13 = 2^3 \times 3^2 \times 5 \times 7 \times 13$$

Even a large num­ber such as 123456789 gives way: $123456789 = 3^2 \times 3607 \times 3803$, and 3607 and 3803 are both prime. How­ever big the num­ber, it comes apart into primes.

A bit of his­tory. An equiv­a­lent form of this fact was prob­a­bly first recorded more than two thou­sand years ago, as Propo­si­tion 14 of Book IX of Euclid's Ele­ments. The first cor­rect proof is cred­ited to Carl Friedrich Gauss (1777–1855), in his Dis­qui­si­tiones Arith­meti­cae.

The Fun­da­men­tal The­o­rem of Arith­metic#

State­ment#

The­o­rem (Fun­da­men­tal The­o­rem of Arith­metic). Every com­pos­ite num­ber can be expressed (fac­torised) as a prod­uct of primes, and this fac­tori­sa­tion is unique, apart from the order in which the prime fac­tors occur.

The sur­pris­ing part is the word unique. The the­o­rem does not only say that a com­pos­ite num­ber can be bro­ken into primes; it says there is exactly one such break­down. Writ­ing the fac­tors of 32760 as $2 \times 2 \times 2 \times 3 \times 3 \times 5 \times 7 \times 13$ or as $13 \times 7 \times 5 \times 3 \times 3 \times 2 \times 2 \times 2$ counts as the same fac­tori­sa­tion, just shuf­fled. No other col­lec­tion of primes mul­ti­plies to 32760.

In gen­eral, a com­pos­ite num­ber $x$ can be writ­ten as

$$x = p_1 p_2 \cdots p_n,$$

where $p_1, p_2, \ldots, p_n$ are primes writ­ten in ascend­ing order, $p_1 \le p_2 \le \cdots \le p_n$. Once we agree always to write the primes small­est first, there is exactly one cor­rect answer. In Class 10 the unique­ness part is accepted with­out proof; the exis­tence part is the split­ting argu­ment above.

Exam­ple 2: can $4^n$ end in the digit 0?#

A num­ber end­ing in 0 is divis­i­ble by 10, so it is divis­i­ble by 5, and its prime fac­tori­sa­tion must con­tain the prime 5. But

$$4^n = (2^2)^n = 2^{2n},$$

so the only prime in the fac­tori­sa­tion of $4^n$ is 2. By unique­ness, no other prime, 5 included, can appear. There­fore $4^n$ can never end in the digit 0 for any nat­ural num­ber $n$. (Check: $4, 16, 64, 256, \ldots$ end in 4 or 6.)

Exam­ple 3: show­ing num­bers are com­pos­ite#

Explain why $7 \times 11 \times 13 + 13$ and $7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 + 5$ are com­pos­ite.

Take out the com­mon fac­tor in each.

$$\begin{aligned} 7 \times 11 \times 13 + 13 &= 13(7 \times 11 + 1) = 13 \times 78 = 1014 \\ 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 + 5 &= 5(7 \times 6 \times 4 \times 3 \times 2 \times 1 + 1) = 5 \times 1009 = 5045 \end{aligned}$$

Each num­ber has a fac­tor other than 1 and itself (13 and 5 respec­tively), so both are com­pos­ite.

Using the the­o­rem to find HCF and LCM#

Def­i­n­i­tions and the rule#

The HCF (high­est com­mon fac­tor) of two num­bers is the largest num­ber that divides both exactly. The LCM (low­est com­mon mul­ti­ple) is the small­est num­ber that both divide exactly. The Fun­da­men­tal The­o­rem of Arith­metic gives the prime fac­tori­sa­tion method:

• HCF = prod­uct of the small­est power of each prime com­mon to the num­bers.
• LCM = prod­uct of the great­est power of each prime that appears in any of the num­bers.

Method#

1. Write each num­ber as a prod­uct of prime pow­ers.
2. For the HCF, list the primes found in every num­ber and take the low­est power of each.
3. For the LCM, list every prime found in any num­ber and take the high­est power of each.
4. Mul­ti­ply out, and check that the HCF divides the LCM.

Exam­ple 4: HCF and LCM of 6 and 20#

$$6 = 2^1 \times 3^1, \qquad 20 = 2^2 \times 5^1$$

Only 2 is com­mon, with small­est power $2^1$, so $\text{HCF}(6, 20) = 2$. The great­est pow­ers of 2, 3 and 5 give $\text{LCM}(6, 20) = 2^2 \times 3 \times 5 = 60$.

Notice that $\text{HCF}(6, 20) \times \text{LCM}(6, 20) = 2 \times 60 = 120 = 6 \times 20$. This is always true for two pos­i­tive inte­gers:

$$\text{HCF}(a, b) \times \text{LCM}(a, b) = a \times b$$

Why this works: for each prime, the HCF takes the smaller of the two expo­nents and the LCM takes the larger. The smaller plus the larger equals the sum of the two expo­nents, which is exactly the expo­nent of that prime in $a \times b$.

Exam­ple 5: HCF of 96 and 404, then the LCM#

$$96 = 2^5 \times 3, \qquad 404 = 2^2 \times 101$$

The only com­mon prime is 2, with small­est power $2^2$, so $\text{HCF}(96, 404) = 4$. Using the prod­uct rela­tion­ship:

$$\displaystyle \text{LCM}(96, 404) = \frac{96 \times 404}{\text{HCF}(96, 404)} = \frac{96 \times 404}{4} = \frac{38784}{4} = 9696$$

As a check, the great­est pow­ers give $2^5 \times 3 \times 101 = 9696$.

Exam­ple 6: three num­bers, and a cau­tion#

Find the HCF and LCM of 6, 72 and 120.

$$6 = 2 \times 3, \qquad 72 = 2^3 \times 3^2, \qquad 120 = 2^3 \times 3 \times 5$$

The small­est com­mon pow­ers are $2^1$ and $3^1$, so $\text{HCF}(6, 72, 120) = 2 \times 3 = 6$. The great­est pow­ers are $2^3$, $3^2$ and $5^1$, so $\text{LCM}(6, 72, 120) = 2^3 \times 3^2 \times 5 = 360$.

The prod­uct rela­tion­ship does not carry over to three num­bers. Here

$$6 \times 72 \times 120 = 51840, \quad \text{but} \quad \text{HCF} \times \text{LCM} = 6 \times 360 = 2160.$$

These are not equal. The rule $\text{HCF} \times \text{LCM} =$ prod­uct works only for two num­bers.

Com­mon mis­takes#

• Leav­ing a com­pos­ite num­ber in the "prime" fac­tori­sa­tion, for exam­ple writ­ing $32760 = 2^3 \times 9 \times 5 \times 91$. Keep split­ting until every fac­tor is prime.
• Tak­ing the great­est power for the HCF or the small­est for the LCM. HCF uses the small­est pow­ers of com­mon primes; LCM uses the great­est pow­ers of all primes.
• Includ­ing in the HCF a prime that appears in only one of the num­bers.
• Using $\text{HCF} \times \text{LCM} =$ prod­uct for three or more num­bers.
• Treat­ing 1 as a prime. It is nei­ther prime nor com­pos­ite, and it never appears in a prime fac­tori­sa­tion.
• Say­ing $4^n$ can­not end in 0 "because 4 is even". The real rea­son is that its only prime fac­tor is 2, so it has no fac­tor 5.

Try these#

1. Express as a prod­uct of prime fac­tors: (i) 140 (ii) 156 (iii) 3825 (iv) 5005 (v) 7429. Answer: (i) $2^2 \times 5 \times 7$ (ii) $2^2 \times 3 \times 13$ (iii) $3^2 \times 5^2 \times 17$ (iv) $5 \times 7 \times 11 \times 13$ (v) $17 \times 19 \times 23$
2. Find the HCF and LCM of each pair, and check that HCF $\times$ LCM equals the prod­uct of the two num­bers: (i) 26 and 91 (ii) 510 and 92 (iii) 336 and 54. Answer: (i) HCF 13, LCM 182 (ii) HCF 2, LCM 23460 (iii) HCF 6, LCM 3024
3. Find the HCF and LCM using prime fac­tori­sa­tion: (i) 12, 15 and 21 (ii) 17, 23 and 29 (iii) 8, 9 and 25. Answer: (i) HCF 3, LCM 420 (ii) HCF 1, LCM 11339 (iii) HCF 1, LCM 1800
4. Given that $\text{HCF}(306, 657) = 9$, find $\text{LCM}(306, 657)$. Answer: 22338
5. Check whether $6^n$ can end with the digit 0 for any nat­ural num­ber $n$. Answer: No; $6^n = 2^n \times 3^n$ has no prime fac­tor 5.
6. Sonia takes 18 min­utes to drive one round of a cir­cu­lar path around a sports field, while Ravi takes 12 min­utes. If they start together from the same point and go in the same direc­tion, after how many min­utes will they meet again at the start­ing point? Answer: 36 min­utes (the LCM of 18 and 12)

Key terms#

Prime num­ber

A nat­ural num­ber greater than 1 whose only fac­tors are 1 and itself.

Com­pos­ite num­ber

A nat­ural num­ber greater than 1 that has at least one fac­tor other than 1 and itself.

Prime fac­tori­sa­tion

Writ­ing a num­ber as a prod­uct of primes, such as $32760 = 2^3 \times 3^2 \times 5 \times 7 \times 13$.

Fac­tor tree

A dia­gram that splits a num­ber into fac­tors step by step until every branch ends in a prime.

Fun­da­men­tal The­o­rem of Arith­metic

Every com­pos­ite num­ber is a prod­uct of primes in exactly one way, apart from the order of the fac­tors.

HCF

The high­est com­mon fac­tor: the largest num­ber that divides each of the given num­bers exactly.

LCM

The low­est com­mon mul­ti­ple: the small­est num­ber that each of the given num­bers divides exactly.

Coprime num­bers

Two num­bers whose HCF is 1, such as 8 and 9.

Com­mon ques­tions#

Why is the the­o­rem called "fun­da­men­tal"?#

Because primes are the build­ing blocks of all whole num­bers greater than 1, and unique­ness means each num­ber has one fixed "recipe". Many later results, includ­ing the irra­tional­ity of $\sqrt{2}$, depend on it.

Why is 1 not counted as a prime?#

If 1 were prime, fac­tori­sa­tions would stop being unique, since $6 = 2 \times 3 = 1 \times 2 \times 3 = 1 \times 1 \times 2 \times 3$. Exclud­ing 1 keeps the the­o­rem true as stated.

Does HCF $\times$ LCM $=$ prod­uct work for three num­bers?#

No. For 6, 72 and 120 the prod­uct is 51840, while HCF $\times$ LCM is only 2160. The rela­tion­ship is for two num­bers only.

Is the prime fac­tori­sa­tion method bet­ter than list­ing fac­tors?#

For large num­bers, yes. List­ing all fac­tors of 32760 would be slow and error-prone, while repeated divi­sion by primes takes a few lines and gives both the HCF and the LCM.

How do I know when a num­ber such as 101 is prime?#

Test divi­sion by the primes up to its square root. Since $10^2 = 100 \lt 101 \lt 121 = 11^2$, it is enough to try 2, 3, 5 and 7; none divides 101, so 101 is prime.

Ref­er­ences#

1. National Coun­cil of Edu­ca­tional Research and Train­ing. Math­e­mat­ics: Text­book for Class X. NCERT, New Delhi.
2. Hardy, G. H. and Wright, E. M. An Intro­duc­tion to the The­ory of Num­bers. Oxford Uni­ver­sity Press.
3. Bur­ton, D. M. Ele­men­tary Num­ber The­ory. McGraw-Hill Edu­ca­tion.
4. Heath, T. L. (trans.) The Thir­teen Books of Euclid's Ele­ments. Dover Pub­li­ca­tions.