# Number Theory: Prime numbers

## Understanding Prime Numbers

• A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself.
• A prime number has two factors, 1 and the number itself, and it cannot be written as a product of two smaller natural numbers.
• The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

## Properties of Prime Numbers

• 2 is the only even prime number; all other even numbers can be divided by 2 so they are not prime.
• The fundamental theorem of arithmetic states that any natural number larger than 1 can be represented uniquely (up to the order of the factors) as a product of prime numbers. This underscores the importance of prime numbers in number theory.
• There is an infinite number of prime numbers. This is proven through a proof by contradiction: if there were a largest prime number, multiply all known primes together, add 1, and the resulting number cannot be divisible by any known prime, contradicting the assumption that we know all primes.

## Identifying Prime Numbers

• Prime factorisation is a common method to identify whether a number is prime. If the number can only be factored to 1 and itself, then it’s a prime number.
• Primality tests are used for large numbers. The Sieve of Eratosthenes and the AKS primality test are two popular tests.

## Primes in Cryptography

• In modern cryptography, prime numbers play a pivotal role, particularly in RSA encryption. Large primes are used to generate encryption keys.
• The security of RSA encryption comes from the fact that, while it is easy (with a know-how) to multiply large prime numbers together to form a composite number, it is extremely difficult to factorize a large composite number back into primes.