1. Introduction to Number Theory

Number theory is one of the oldest branches of mathematics, focusing on the properties and relationships of integers. Often called the "Queen of Mathematics," it has fascinated mathematicians for centuries due to its elegant theorems and challenging problems.

While many number theory problems are simple to state, they can be extraordinarily difficult to solve. From ancient civilizations to modern cryptography, number theory has played a crucial role in mathematics and its applications.

2. Divisibility and Division Algorithm

Divisibility is a fundamental concept in number theory that establishes the relationship between integers.

Division Algorithm

The division algorithm states that for any integers a and b where b > 0, there exist unique integers q (quotient) and r (remainder) such that:

a = bq + r, where 0 ≤ r < b

Divisibility Tests

Divisibility tests are shortcuts to determine if a number is divisible by another without performing the actual division.

3. Prime Numbers and Factorization

The first few prime numbers are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...

Fundamental Theorem of Arithmetic

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

Sieve of Eratosthenes

An ancient algorithm for finding all prime numbers up to any given limit:

1. Create a list of consecutive integers from 2 through n: (2, 3, 4, ..., n).
2. Start with the first prime number, p = 2.
3. Mark all multiples of p as composite (not prime).
4. Find the first unmarked number greater than p. This is the next prime.
5. Repeat steps 3 and 4 until p² exceeds n.

Properties of Prime Numbers

• There are infinitely many prime numbers.
• Every even integer greater than 2 can be expressed as the sum of two primes (Goldbach's Conjecture, still unproven for all numbers).
• The distribution of primes becomes less dense as numbers get larger.

4. Greatest Common Divisor (GCD) and Least Common Multiple (LCM)

Euclidean Algorithm

The Euclidean algorithm is an efficient method to find the GCD of two integers.

function gcd(a, b) {
    while (b !== 0) {
        let t = b;
        b = a % b;
        a = t;
    }
    return a;
}
            

Relationship Between GCD and LCM

For two positive integers a and b:

LCM(a, b) × GCD(a, b) = a × b

Extended Euclidean Algorithm

The Extended Euclidean Algorithm not only finds the GCD of integers a and b but also finds integers x and y such that:

ax + by = GCD(a, b)

This is particularly useful in solving linear Diophantine equations and in modular arithmetic.

5. Modular Arithmetic

Modular arithmetic is like "clock arithmetic" where numbers "wrap around" after reaching a certain value.

Properties of Modular Arithmetic

For integers a, b, c, and n > 0:

• If a ≡ b (mod n) and c ≡ d (mod n), then a + c ≡ b + d (mod n).
• If a ≡ b (mod n) and c ≡ d (mod n), then a × c ≡ b × d (mod n).
• If a ≡ b (mod n), then a^k ≡ b^k (mod n) for any positive integer k.

Modular Exponentiation

Computing large powers in modular arithmetic efficiently using the square-and-multiply algorithm:

function modPow(base, exponent, modulus) {
    if (modulus === 1) return 0;
    let result = 1;
    base = base % modulus;
    
    while (exponent > 0) {
        // If exponent is odd, multiply result with base
        if (exponent % 2 === 1) {
            result = (result * base) % modulus;
        }
        
        // Square the base
        base = (base * base) % modulus;
        
        // Divide exponent by 2
        exponent = Math.floor(exponent / 2);
    }
    
    return result;
}
            

Fermat's Little Theorem

If p is a prime number and a is an integer not divisible by p, then:

a^p-1 ≡ 1 (mod p)

This theorem is used in primality testing and public-key cryptography.

6. Diophantine Equations

Linear Diophantine Equations

The simplest form is ax + by = c, where we seek integer solutions for x and y.

Pythagorean Triples

These are integer solutions to the equation a² + b² = c², which is a non-linear Diophantine equation.

All primitive Pythagorean triples (where gcd(a, b, c) = 1) can be generated using:

• a = m² - n²
• b = 2mn
• c = m² + n²

Where m > n > 0 are coprime integers and not both odd.

7. Number Theoretic Functions

Euler's Totient Function φ(n)

Möbius Function μ(n)

Sum and Product Functions

Other important number theoretic functions include:

• σ₀(n): the number of divisors of n
• σ₁(n): the sum of divisors of n
• σₖ(n): the sum of the k-th powers of the divisors of n

8. Continued Fractions

Types of Continued Fractions

• Finite continued fraction: Represents a rational number.
• Infinite continued fraction: Represents an irrational number.
• Periodic continued fraction: An infinite continued fraction where the sequence of integers eventually repeats. These represent quadratic irrationals.

Converting Numbers to Continued Fractions

1. For rational numbers: Use the Euclidean algorithm.
2. For irrational numbers: Use the floor function iteratively.

function toContinuedFraction(numerator, denominator) {
    let a = numerator;
    let b = denominator;
    let quotients = [];
    
    while (b !== 0) {
        quotients.push(Math.floor(a / b));
        let temp = a;
        a = b;
        b = temp % b;
    }
    
    return quotients;
}
            

Best Approximations Property

Convergents of continued fractions provide the best rational approximations to real numbers. This property makes them useful in various applications, including designing gear ratios and calculating lunar and planetary motion.

9. Quadratic Residues

Legendre Symbol

For an odd prime p and an integer a not divisible by p, the Legendre symbol (a/p) is defined as:

• (a/p) = 1 if a is a quadratic residue modulo p
• (a/p) = -1 if a is a quadratic non-residue modulo p

Law of Quadratic Reciprocity

For distinct odd primes p and q:

(p/q)(q/p) = (-1)^{((p-1)/2)((q-1)/2)}

This remarkable result connects quadratic residues of different moduli and is fundamental in number theory.

10. Number Theory Quiz

Test your understanding of number theory with this interactive quiz!