Fundamental theorem of arithmetic proof, applications, exercises

The 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 It is one that only admits itself and 1 as positive divisors. The following numbers are prime: 2, 3, 5, 7, 11, 13 and so on, since there are infinities. The number 1 is not considered a prime, because it has a single divisor.

For their part, the numbers that do not comply with the above are called composed numbers, 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₁, p_two, p₃... p_r are prime numbers and k₁, k_two, k₃,... k_r they are natural numbers. So the prime numbers act like the bricks from which, through multiplication, the natural numbers are built.

Article index

• 1 Proof of the Fundamental Theorem of Arithmetic
  • 1.1 Uniqueness of prime factorization
• 2 Applications
  • 2.1 Prime numbers in nature
  • 2.2 Prime numbers and online shopping
• 3 Solved exercises
  • 3.1 - Exercise 1
  • 3.2 - Exercise 2
• 4 References

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₁, with P₁ a prime number, then n is written as:

n = p₁.d

If d is prime there is nothing more to do, but if it is not, there is a number n_two which is a divisor of d and less than this: n_two < d, por lo que d podrá escribirse como el producto de n_two by another prime number p_two:

d = p_two n_two

That when substituting in the original number n would give:

n = p₁ .p_two .n_two

Now suppose that n_two either is a prime number and we write it as the product of a prime number p₃, by a divisor of yours n₃, such that n₃ < n_two < n₁ < n:

n_two = p₃.n₃ → n = p₁ p_two p₃.n₃

 We repeat this procedure a finite number of times until we obtain:

n = p₁.p_two.p₃ ... p_r

This means that it is possible to decompose everyone whole numbers from 2 to 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₁.p_two.p₃ ... p_r = q_1.what_two.what₃... what_s  (with r ≤ s)

Of course that₁, what_two, what₃... are prime numbers too. As p₁ divide a (q_1.what_two.what₃... what_s) Then p₁ is equal to any of the "q", it does not matter to which, so we can say that p₁ = q₁. We divide n by p₁ and we get:

p_two.p₃ ... p_r =_.what_two.what₃... what_s

We repeat the procedure until we divide everything by p_r, then we get:

1 = q_{r + 1}... what_s

But it is not possible to get to what_{r + 1}... what_s = 1 when r < s, solo si r = s. Aunque al admitir que r = s, también se admite que los “p” y los “q” son los mismos. Por lo tanto la descomposición es única.

Applications

As we have said before, the prime numbers represent, if you will, the atoms of the numbers, their basic components. So the fundamental theorem of arithmetic has numerous applications, the most obvious one: we can work more easily with large numbers 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 sums 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 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 that 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.

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 arrives precisely at the store 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 a key, which when multiplying them give much larger numbers, whose detailed decomposition involves a huge task.

Solved exercises

- Exercise 1

Decompose 1029 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³, then:

1029 = 3 × 7³ = 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^two + 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; a.b = 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⁴ × 3³ = 2 × 3³× 2³ = 2⁴× 3^two × 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 between the prime factors, but to solve the proposed exercise, the only suitable combination is: 432 = 24 × 18 since 24 + 18 = 42, then:

x^two + 42x + 432 = (x + 24). (x +18)

References

1. Baldor, A. 1986. Theoretical practical arithmetic. Compañía Cultural Editora de Textos Americanos S.A.
2. BBC World. The Hidden Code of Nature. Recovered from: bbc.com.
3. De Leon, Manuel Prime numbers: the guardians of the internet. Recovered from: blogs.20minutos.es.
4. UNAM. Number Theory I: Fundamental theorem of Arithmetic. Recovered from: teoriadenumeros.wikidot.com.
5. Wikipedia. The fundamental theorem of arithmetic. Recovered from: es.wikipedia.org.