Arithmetic

Prime Numbers

Prime Number Hunters

In 1588 Italian mathematician **Pietro Cataldi** found the prime 524287 = 2¹⁹ − 1. He spent years on the calculations by hand. Today, volunteers in the **GIMPS** (Great Internet Mersenne Prime Search) project use thousands of computers to hunt for enormous primes.

Primes are not just a mathematical curiosity. RSA encryption, which protects bank transactions and private communications, is based on the difficulty of factoring large numbers into primes.

Bank passwords are protected by prime numbers. RSA encryption works because multiplying two enormous primes together is easy, but factoring the result back apart is practically impossible. Prime numbers are the foundation of modern cryptography.

**Cryptography:** RSA, protecting bank transactions
**Hashing:** verifying data integrity
**Music:** intervals and harmonies are related to prime numbers

Definition of a Prime Number

The number 12 can be broken up: 12 = 3 × 4 = 2 × 6 = 2 × 2 × 3. But the number 7? Only 7 = 1 × 7. These 'unbreakable' numbers are called **primes**.

A **prime number** is a natural number greater than 1 that is divisible only by 1 and itself. Primes: 2, 3, 5, 7, 11, 13, 17, 19, 23... Composites: 4, 6, 8, 9, 10, 12, 14, 15...

Prime numbers are the 'atoms' of arithmetic. Every integer can be broken down into prime factors, just as a molecule can be broken into atoms. And this factorization is unique!

Which of the following is a prime number?

Primality Testing

How to check whether 97 is prime? Divide by every number from 2 to 96? There's a better way!

**Why √n is sufficient:** If n = a × b, one of the factors does not exceed √n. For 100: √100 = 10. If 100 is composite, one divisor is ≤ 10. 100 = 10 × 10 = 4 × 25 = 2 × 50 In every pair there is a divisor ≤ 10.

For very large numbers (hundreds of digits), probabilistic tests are used. They don't give a 100% guarantee but run in seconds.

Up to what number is it sufficient to check divisors when testing whether 143 is prime?

The Sieve of Eratosthenes

How to find ALL prime numbers up to 100? The ancient Greek mathematician Eratosthenes invented an elegant method - a 'sieve' that filters out composite numbers.

**Efficiency of the sieve:** To find all primes up to n: • Naive method: ~n² operations • Sieve of Eratosthenes: ~n log log n operations For n = 1,000,000 - a difference of thousands of times!

The sieve is an example of an algorithm that is easiest to understand visually. Composite numbers 'fall through' the sieve; primes remain.

In the Sieve of Eratosthenes for numbers up to 50, after crossing out multiples of 7, what is the next number to process?

There Are Infinitely Many Primes

There are infinitely many prime numbers. This was proved by Euclid over 2,300 years ago in one of the most beautiful proofs in mathematics.

**Open questions about primes:** • Goldbach's Conjecture: is every even number > 2 the sum of two primes? • Twin Prime Conjecture: are there infinitely many pairs (p, p+2)? • Riemann Hypothesis: on the distribution of primes (a million-dollar prize!)

Prime numbers are one of the deepest topics in mathematics. They appear random, but obey subtle patterns that we still do not fully understand.

The formula p₁×p₂×...×pₙ + 1 always gives a prime number

This formula gives a number not divisible by the known primes, but it may be composite

2×3×5×7×11×13 + 1 = 30031 = 59 × 509. The number is not prime, but its factors (59 and 509) are new primes not in the list. Euclid's proof still works!

If the only primes are 2, 3, 5, then the number 2×3×5 + 1 = 31...

Key Ideas

A prime is divisible only by 1 and itself (1 is NOT prime!)
To test primality, check divisors only up to √n
The Sieve of Eratosthenes finds all primes up to n
There are infinitely many primes (Euclid's theorem)

Вопросы для размышления

Why is 2 the only even prime number?
How do computers find prime numbers with hundreds of digits?
Why do prime numbers seem 'random' in their distribution?