

# Background and motivation for unique factorization

Unique factorization is a fundamental concept in number theory, which deals with the factorization of integers into prime factors. The concept of unique factorization is essential in number theory and has numerous applications in other fields of mathematics, such as algebra, combinatorics, and cryptography. Understanding unique factorization helps us to solve various problems and provides a solid foundation for further studies in these areas.

Consider the integer 12. It can be factored into its prime factors as follows:

$$12 = 2 \times 2 \times 3$$

This factorization is unique because the prime factors 2, 2, and 3 cannot be rearranged to obtain another factorization.

## Exercise
Find the prime factorization of the integer 30.

Instructions:

- Factor the integer 30 into its prime factors.
- Write down the prime factorization.

### Solution
The prime factorization of 30 is:

$$30 = 2 \times 3 \times 5$$

# Prime numbers and prime factorization

A prime number is a natural number greater than 1 that has no divisors other than 1 and itself. In other words, if a number is prime, it cannot be factored into smaller natural numbers. The prime factorization of an integer is the process of expressing that integer as a product of prime numbers.

Consider the integer 15. It can be factored into its prime factors as follows:

$$15 = 3 \times 5$$

In this factorization, the prime numbers are 3 and 5.

## Exercise
Find the prime factorization of the integer 18.

Instructions:

- Factor the integer 18 into its prime factors.
- Write down the prime factorization.

### Solution
The prime factorization of 18 is:

$$18 = 2 \times 3^2$$

# The fundamental theorem of arithmetic

The fundamental theorem of arithmetic states that every integer greater than 1 has a unique prime factorization. This means that every integer can be expressed as a product of prime numbers in exactly one way. The theorem is fundamental because it provides a basis for understanding the structure of integers and their factorization.

Consider the integer 72. It can be factored into its prime factors as follows:

$$72 = 2^3 \times 3$$

This factorization is unique because the prime factors 2, 2, 2, and 3 cannot be rearranged to obtain another factorization.

## Exercise
Find the prime factorization of the integer 84.

Instructions:

- Factor the integer 84 into its prime factors.
- Write down the prime factorization.

### Solution
The prime factorization of 84 is:

$$84 = 2^2 \times 3^2$$

# Greatest common divisor and least common multiple

The greatest common divisor (GCD) and the least common multiple (LCM) are two fundamental concepts in number theory. The GCD of two integers is the largest number that divides both of them, while the LCM is the smallest number that is divisible by both of them.

Consider the integers 12 and 15. Their GCD is 3, and their LCM is 60.

## Exercise
Find the GCD and LCM of the integers 36 and 48.

Instructions:

- Calculate the GCD of 36 and 48.
- Calculate the LCM of 36 and 48.

### Solution
The GCD of 36 and 48 is 12.
The LCM of 36 and 48 is 144.

# Algorithms for finding prime factorization and unique factorization

There are several algorithms for finding the prime factorization of an integer. One of the most common algorithms is the trial division method, which involves dividing the integer by all prime numbers less than or equal to its square root. Another algorithm is the Sieve of Eratosthenes, which is used to generate all prime numbers up to a given limit.

Consider the integer 100. Using the trial division method, we can find its prime factorization as follows:

$$100 = 2 \times 2 \times 5 \times 5$$

## Exercise
Find the prime factorization of the integer 98.

Instructions:

- Use the trial division method to factor the integer 98.
- Write down the prime factorization.

### Solution
The prime factorization of 98 is:

$$98 = 2 \times 7 \times 11$$

# Applications of unique factorization

Unique factorization has numerous applications in various fields of mathematics and beyond. Some of these applications include:

- Solving linear Diophantine equations
- Proving the existence and uniqueness of solutions to linear systems of equations
- Proving the existence and uniqueness of solutions to quadratic equations
- Factoring polynomials
- Solving problems in number theory, such as the Fermat's Last Theorem

Consider the linear Diophantine equation 12x + 15y = 30. Using unique factorization, we can find the solution to this equation.

## Exercise
Solve the linear Diophantine equation 12x + 15y = 30.

Instructions:

- Use unique factorization to find the solution to the equation.
- Write down the solution.

### Solution
The solution to the linear Diophantine equation 12x + 15y = 30 is x = 2 and y = 1.

# The Chinese Remainder Theorem

The Chinese Remainder Theorem (CRT) is a fundamental theorem in number theory. It states that if we have a system of congruences with pairwise coprime moduli, then there exists a unique solution modulo the product of the moduli.

- The Chinese Remainder Theorem is a generalization of the Fermat's Little Theorem.
- The theorem is named after the Chinese mathematician who first proved it.

Consider the system of congruences:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)

Using the Chinese Remainder Theorem, we can find the unique solution modulo the product of the moduli (3 and 5).

## Exercise
Instructions:

Find the unique solution modulo 15 for the system of congruences:

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)

Instructions:

- Use the Chinese Remainder Theorem to find the solution.
- Write down the solution.

### Solution
The unique solution modulo 15 for the system of congruences is x = 11.

# Euclidean algorithm for finding greatest common divisor

The Euclidean algorithm is a method for finding the greatest common divisor (GCD) of two integers. It is named after the Greek mathematician Euclid. The algorithm is based on the principle that the GCD of two numbers is the same as the GCD of the two numbers when the larger number is replaced by its difference with the smaller number.

The Euclidean algorithm can be implemented through a series of steps:

1. Divide the larger number by the smaller number and obtain the quotient and the remainder.
2. Replace the larger number with the smaller number and the smaller number with the obtained remainder.
3. Repeat steps 1 and 2 until the remainder is 0.

The GCD is the last non-zero remainder.

Find the GCD of 84 and 120 using the Euclidean algorithm.

## Exercise
Instructions:

Find the GCD of 84 and 120 using the Euclidean algorithm.

Instructions:

- Use the Euclidean algorithm to find the GCD.
- Write down the GCD.

### Solution
The GCD of 84 and 120 is 12.