Number Theory

In this session, we hope to instill a fascination for prime numbers and their properties. Primes are central to number theory and can be considered as the basic building blocks of natural numbers. The reason for this will be evident at the end of this session.

The Hero’s Entry

  1. Can all natural numbers be generated from 2 and 3 using addition only?
    • All natural numbers at least 2.
    • What if we allow subtraction? Can all integers be generated?
    • What if we have 4 and 6 instead of 2 and 3?
    • What property is needed for a and b if they have to generate all natural numbers using addition and subtraction?
  2. A teaser for Bezout’s identity.
    • The integers that can be generated using two natural numbers $a$ and $b$ using addition and subtraction only are precisely the multiples of gcd$(a,b)$.
      • Prove that only multiples of the gcd$(a,b)$ can be generated.
      • What about the other direction?

  3. If we are only allowed to use a single number (instead of two) and addition and subtraction only, which number would you pick?

  4. If we were allowed two seeds but allowed only multiplication and division (no addition or subraction), which two numbers will you choose?
    • Any two are insufficient!
    • What if you are allowed three numbers?
    • How many numbers do you need?
      • You need all prime numbers!
  5. A natural number is prime if it has exactly two distinct divisors.
    • Is 1 prime?

Practice with Primes

  1. Sieve of Eratosthenes (200 CE)

  2. How many primes are there?

  3. Theorem: Every integer greater than 1 can be represented uniquely as a product of prime numbers, up to the order of the factors.

  4. Can we find $k$ consecutive composite numbers? Here $k = 3, 5, 10, 100, \ldots$.

  5. Twin prime conjecture (Polignac, 1849). There are infinitely many primes $p$ such that $p + 2$ is also prime.
    • Examples of twin primes: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109), (137, 139),
    • Can you find a prime number $p$ such that $p + 2$ and $p + 4$ are also prime?
  6. Goldbach’s Conjecture (Goldbach, 1742). Every even natural number greater than 2 is the sum of two prime numbers.