- Proof of the fundamental theorem of arithmetic
- Uniqueness of prime factorization
- Applications
- Prime numbers in nature
- Prime numbers and online shopping
- Solved exercises
- - Exercise 1
- Solution
- - Exercise 2
- Solution
- References
The fundamental theorem of arithmetic states that any natural number greater than 1 can be decomposed as a product of prime numbers - some can be repeated - and this form is unique for that number, although the order of the factors may be different.
Recall that a prime number p is one that only admits itself and 1 as positive divisors. The following numbers are primes: 2, 3, 5, 7, 11, 13 and so on, since there are infinities. The number 1 is not considered a prime, as it has only one divisor.
Figure 1. Euclid (left) proved the fundamental theorem of arithmetic in his book Elements (350 BC), and the first complete proof is due to Carl F. Gauss (1777-1855) (right). Source: Wikimedia Commons.
For its part, the numbers that do not comply with the above are called composite numbers, such as 4, 6, 8, 9, 10, 12, 14… Let's take the number 10 for example and immediately we see that it can be decomposed as a product of 2 and 5:
10 = 2 × 5
Both 2 and 5 are, effectively, prime numbers. The theorem states that this is possible for any number n:
Where p 1, p 2, p 3 … p r are prime numbers and k 1, k 2, k 3,… k r are natural numbers. So the prime numbers act as the building blocks from which, through multiplication, the natural numbers are built.
Proof of the fundamental theorem of arithmetic
We begin by showing that every number can be decomposed into prime factors. Let be a natural number n> 1, prime or composite.
For example if n = 2, it can be expressed as: 2 = 1 × 2, which is prime. In the same way, proceed with the following numbers:
3 = 1 × 3
4 = 2 × 2
5 = 1 × 5
6 = 2 × 3
7 = 1 × 7
8 = 2 × 2 × 2
We continue like this, decomposing all the natural numbers until we reach the number n -1. Let's see if we can do it with the following number: n.
If n is prime, we can decompose it as n = 1 × n, but suppose that n is composite and has a divisor d, logically less than n:
1 <d <n.
If n / d = p 1, with p 1 a prime number, then n is written as:
n = p 1.d
If d is prime there is nothing more to do, but if it is not, there is a number n 2 that is a divisor of d and less than this: n 2 <d, so d can be written as the product of n 2 by another prime number p 2:
d = p 2 n 2
That when substituting in the original number n would give:
n = p 1.p 2.n 2
Now suppose that n 2 is not a prime number either and we write it as the product of a prime number p 3, by its divisor n 3, such that n 3 <n 2 <n 1 <n:
n 2 = p 3.n 3 → n = p 1 p 2 p 3.n 3
We repeat this procedure a finite number of times until we obtain:
n = p 1.p 2.p 3 … p r
This means that it is possible to decompose all whole numbers from 2 to the number n, as a product of prime numbers.
Uniqueness of prime factorization
Now let us verify that except for the order of the factors, this decomposition is unique. Suppose that n can be written in two ways:
n = p 1.p 2.p 3 … p r = q 1. q 2.q 3 …..q s (with r ≤ s)
Of course q 1, q 2, q 3… are prime numbers too. Since p 1 divides (q 1. q 2.q 3 …..q s) then p 1 is equal to any of the “q”, it doesn't matter which one, so we can say that p 1 = q 1. We divide n by p 1 and obtain:
p 2.p 3 … p r = . q 2.q 3 …..q s
We repeat the procedure until we divide everything by p r, then we obtain:
1 = q r + 1 … q s
But it is not possible to arrive at q r + 1 … q s = 1 when r <s, only if r = s. Although by admitting that r = s, it is also admitted that the "p" and the "q" are the same. Therefore the decomposition is unique.
Applications
As we have said before, the prime numbers represent, if you like, the atoms of the numbers, their basic components. So the fundamental theorem of arithmetic has numerous applications, the most obvious: we can work with large numbers more easily if we express them as the product of smaller numbers.
In the same way, we can find the greatest common multiple (LCM) and the greatest common divisor (GCF), a procedure that helps us to make additions of fractions more easily, find roots of large numbers, or operate with radicals, rationalize and solve application problems of a very diverse nature.
Furthermore, prime numbers are extremely enigmatic. A pattern is not yet recognized in them and it is not possible to know which one will be the next. The largest so far was found by computers and has 24,862,048 digits, although the new prime numbers appear less frequently each time.
Prime numbers in nature
The cicadas, cicádidos or cicadas that live in the northeast of the United States emerge in cycles of 13 or 17 years. They are both prime numbers.
In this way, the cicadas avoid coinciding with predators or competitors who have other periods of birth, nor do the different varieties of cicadas compete with each other, since they do not coincide during the same year.
Figure 2. The Magicicada cicada of the eastern United States emerges every 13 to 17 years. Source: Pxfuel.
Prime numbers and online shopping
Prime numbers are used in cryptography to keep credit card details secret when making purchases over the Internet. In this way, the data that the buyer reaches the store precisely without being lost or falling into the hands of unscrupulous people.
How? The data on the cards is encoded in a number N that can be expressed as the product of prime numbers. These prime numbers are the key that the data reveals, but they are unknown to the public, they can only be decoded on the web to which they are directed.
Decomposing a number into factors is an easy task if the numbers are small (see the solved exercises), but in this case prime numbers of 100 digits are used as the key, which when multiplying them give much larger numbers, whose detailed decomposition involves a huge task.
Solved exercises
- Exercise 1
Break 1029 down into prime factors.
Solution
1029 is divisible by 3. It is known because when adding its digits the sum is a multiple of 3: 1 + 0 + 2 + 9 = 12. As the order of the factors does not alter the product, we can start there:
1029 3
343
1029 = 3 × 343
On the other hand 343 = 7 3, then:
1029 = 3 × 7 3 = 3 × 7 × 7 × 7
And since both 3 and 7 are prime numbers, this is the decomposition of 1029.
- Exercise 2
Factor the trinomial x 2 + 42x + 432.
Solution
The trinomial is rewritten in the form (x + a). (x + b) and we need to find the values of a and b, such that:
a + b = 42; ab = 432
The number 432 is decomposed into prime factors and from there the appropriate combination is chosen by trial and error so that the added factors give 42.
432 = 2 4 × 3 3 = 2 × 3 3 × 2 3 = 2 4 × 3 2 × 3 =…
From here there are several possibilities to write 432:
432 = 16 × 27 = 24 × 18 = 54 × 8 = 6 × 72….
And all of them can be found by combining products among the prime factors, but to solve the proposed exercise, the only suitable combination is: 432 = 24 × 18 since 24 + 18 = 42, then:
x 2 + 42x + 432 = (x + 24). (x +18)
References
- Baldor, A. 1986. Theoretical practical arithmetic. Compañía Cultural Editora de Textos Americanos SA
- BBC World. The Hidden Code of Nature. Recovered from: bbc.com.
- De Leon, Manuel. Prime numbers: the guardians of the internet. Recovered from: blogs.20minutos.es.
- UNAM. Number Theory I: Fundamental Theorem of Arithmetic. Recovered from: teoriadenumeros.wikidot.com.
- Wikipedia. The fundamental theorem of arithmetic. Recovered from: es.wikipedia.org.