Number Theory: Prime numbers

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.