Prímfaktorálás

Prímfaktorálás, also known as prime factorization, is the process of expressing a composite number as a product of its prime factors. A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, 2, 3, 5, 7, and 11 are prime numbers. A composite number is a natural number that can be formed by multiplying two smaller natural numbers. For instance, 4, 6, 8, 9, and 10 are composite numbers.

The fundamental theorem of arithmetic states that every integer greater than 1 is either a prime number itself or can be represented as a product of prime numbers, and this representation is unique, up to the order of the factors. This uniqueness is crucial to the concept of prime factorization.

To perform prime factorization, one can use various methods. A common approach is to repeatedly divide the number by the smallest prime number that divides it evenly. For example, to factorize 12, we start with the smallest prime, 2. 12 divided by 2 is 6. Then, we factorize 6. 6 divided by 2 is 3. 3 is a prime number, so we stop. Thus, the prime factorization of 12 is 2 × 2 × 3, or 2² × 3.

Prime factorization has numerous applications in number theory and other areas of mathematics. It is used in finding the greatest common divisor (GCD) and least common multiple (LCM) of two or more numbers. It also plays a role in cryptography, particularly in algorithms that rely on the difficulty of factoring large composite numbers into their prime components.