Prime Numbers

โฑ 8 minโœ๏ธ Quiz at the end

What is a Prime Number?

A prime number is a whole number greater than 1 that has exactly two factors: 1 and itself.

It can only be divided exactly by 1 and the number itself โ€” no other whole number divides it evenly.

Examples: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47...

Primes are the building blocks of all numbers โ€” every whole number greater than 1 is either prime or can be broken down into prime factors.

Key Terms

  • Prime number: a whole number > 1 with exactly two factors (1 and itself)
  • Composite number: a whole number with more than two factors
  • Factor: a whole number that divides into another with no remainder
  • Prime factorisation: expressing a number as a product of prime factors
  • Fundamental Theorem of Arithmetic: every integer > 1 has a unique prime factorisation

Composite Numbers

A composite number has more than two factors โ€” it can be divided by numbers other than 1 and itself.

Examples and their factors:

  • 4: factors are 1, 2, 4
  • 9: factors are 1, 3, 9
  • 15: factors are 1, 3, 5, 15
  • 36: factors are 1, 2, 3, 4, 6, 9, 12, 18, 36

Special Cases

  • 1 is neither prime nor composite. It has only one factor (itself), so it does not meet the definition of prime (two factors) or composite (more than two).
  • 2 is the only even prime number. Every other even number is divisible by 2, giving it at least three factors (1, 2, and itself), making it composite.

The Sieve of Eratosthenes

This ancient method finds all primes up to any number efficiently:

  1. Write all whole numbers from 2 to your target (e.g. 50)
  2. Circle 2 (it is prime), then cross out every multiple of 2: 4, 6, 8, 10...
  3. Move to 3 (not crossed out โ€” it is prime), cross out multiples of 3: 6, 9, 12...
  4. Move to 5, cross out multiples: 10, 15, 20...
  5. Move to 7, cross out multiples: 14, 21, 28...
  6. Stop when the next uncrossed number is greater than โˆš50 โ‰ˆ 7.07
  7. All remaining uncrossed numbers are prime

Primes up to 50: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

You only need to check factors up to the square root of a number โ€” a useful shortcut when testing if a number is prime.

Testing Whether a Number is Prime

To test if 97 is prime:

  • โˆš97 โ‰ˆ 9.8, so only check divisors up to 9: 2, 3, 5, 7
  • 97 รท 2: remainder (odd number)
  • 97 รท 3: 9+7=16, not divisible by 3
  • 97 รท 5: does not end in 0 or 5
  • 97 รท 7: 7 ร— 13 = 91, 7 ร— 14 = 98 โ†’ not divisible
  • None divide evenly, so 97 is prime

Prime Factorisation

Every composite number is a unique product of prime factors. There are two methods:

Method 1 โ€” Factor tree: Factorise 60:

  • 60 = 2 ร— 30
  • 30 = 2 ร— 15
  • 15 = 3 ร— 5
  • 60 = 2 ร— 2 ร— 3 ร— 5 = 2ยฒ ร— 3 ร— 5

Method 2 โ€” Repeated division: Divide by the smallest prime repeatedly:

  • 60 รท 2 = 30
  • 30 รท 2 = 15
  • 15 รท 3 = 5
  • 5 รท 5 = 1
  • 60 = 2ยฒ ร— 3 ร— 5

This is the Fundamental Theorem of Arithmetic โ€” every integer greater than 1 has exactly one prime factorisation (ignoring the order of factors).

Uses of Prime Factorisation

Prime factorisation is used to:

  • Find the Highest Common Factor (HCF) of two numbers
  • Find the Lowest Common Multiple (LCM) of two numbers
  • Simplify fractions to their lowest terms
  • Solve problems in cryptography (internet security relies on the difficulty of factorising large numbers)

Common Mistakes to Avoid

  • Calling 1 a prime number โ€” it is not; it has only one factor
  • Stopping the sieve too early โ€” you must cross out all multiples, not just the first few
  • Incomplete factor trees โ€” all branches must end in prime numbers, not composite numbers
  • Forgetting powers in prime factorisation โ€” write 60 = 2ยฒ ร— 3 ร— 5, not 2 ร— 2 ร— 3 ร— 5

Tips and Tricks

  • Divisibility rules speed up prime testing: divisible by 2 if even; by 3 if digit sum is divisible by 3; by 5 if ends in 0 or 5
  • The primes below 20 are worth memorising: 2, 3, 5, 7, 11, 13, 17, 19
  • There are infinitely many prime numbers โ€” mathematicians have proved there is no largest prime
  • The largest known prime (as of 2024) has over 41 million digits
Related Topics