Number Theory 101: Exploring Integers and Primes

Number theory, the study of integers and their properties, uncovers the hidden structure of numbers like -5, 0, and 42. Focusing on concepts such as prime numbers, divisibility, greatest common divisors (GCD), least common multiples (LCM), modular arithmetic, and Euler’s totient function, it forms the foundation for advanced mathematics and practical applications like cryptography. This MathMultiverse guide offers a clear exploration with detailed examples, visualizations, and real-world applications, making number theory accessible and engaging.

Understanding Prime Numbers

A prime number is a positive integer greater than 1 with exactly two distinct positive divisors: 1 and itself (e.g., 2, 3, 5, 7, 11). Composite numbers have additional divisors (e.g., 4: 1, 2, 4), while 1 is neither prime nor composite, and 0 and negative numbers are excluded.

Fundamental Theorem of Arithmetic

Every integer greater than 1 has a unique prime factorization (up to order):

\[ 12 = 2^2 \times 3 \]

This uniqueness is critical for applications like simplifying fractions and cryptography.

Properties

Euclid proved there are infinitely many primes. The Prime Number Theorem describes their distribution, showing primes become less frequent as numbers grow.

Examples

Let’s explore number theory concepts with detailed calculations.

GCD via Euclidean Algorithm

The GCD is the largest positive integer dividing two numbers without remainder.

GCD(48, 18):

\[ 48 = 2 \times 18 + 12 \] \[ 18 = 1 \times 12 + 6 \] \[ 12 = 2 \times 6 + 0 \] \[ \text{GCD}(48, 18) = 6 \]

Verify: \( 48 \div 6 = 8 \), \( 18 \div 6 = 3 \).

GCD(56, 98):

\[ 98 = 1 \times 56 + 42 \] \[ 56 = 1 \times 42 + 14 \] \[ 42 = 3 \times 14 + 0 \] \[ \text{GCD}(56, 98) = 14 \]

Verify: \( 56 \div 14 = 4 \), \( 98 \div 14 = 7 \).

LCM Calculation

LCM is the smallest number divisible by both inputs:

\[ \text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)} \]

LCM(48, 18):

\[ \text{GCD}(48, 18) = 6 \] \[ \text{LCM} = \frac{48 \times 18}{6} = \frac{864}{6} = 144 \]

Verify: \( 144 \div 48 = 3 \), \( 144 \div 18 = 8 \).

LCM(15, 25):

\[ 25 = 1 \times 15 + 10 \] \[ 15 = 1 \times 10 + 5 \] \[ 10 = 2 \times 5 + 0 \] \[ \text{GCD}(15, 25) = 5 \] \[ \text{LCM} = \frac{15 \times 25}{5} = \frac{375}{5} = 75 \]

Prime Factorization

Factorize 60:

\[ 60 = 2^2 \times 3 \times 5 \]

Factorize 100:

\[ 100 = 2^2 \times 5^2 \]

Prime Factor Counts

Number of prime factors for numbers up to 100.

Coprimality

Two numbers are coprime if GCD = 1.

15 and 28:

\[ 28 = 1 \times 15 + 13 \] \[ 15 = 1 \times 13 + 2 \] \[ 13 = 6 \times 2 + 1 \] \[ 2 = 2 \times 1 + 0 \] \[ \text{GCD}(15, 28) = 1 \]

15 and 28 are coprime.

24 and 36:

\[ 36 = 1 \times 24 + 12 \] \[ 24 = 2 \times 12 + 0 \] \[ \text{GCD}(24, 36) = 12 \]

Not coprime.

Modular Arithmetic

Solve \( 17 \pmod{5} \):

\[ 17 = 3 \times 5 + 2 \] \[ 17 \equiv 2 \pmod{5} \]

Solve \( 25 \times 13 \pmod{7} \):

\[ 25 \equiv 4 \pmod{7}, \quad 13 \equiv 6 \pmod{7} \] \[ 4 \times 6 = 24 \equiv 3 \pmod{7} \]

Euler’s Totient Function

Counts numbers coprime to \( n \):

\[ \phi(n) = n \prod_{p|n} \left(1 - \frac{1}{p}\right) \]

\( \phi(12) \):

\[ 12 = 2^2 \times 3 \] \[ \phi(12) = 12 \left(1 - \frac{1}{2}\right) \left(1 - \frac{1}{3}\right) = 12 \times \frac{1}{2} \times \frac{2}{3} = 4 \]

\( \phi(15) \):

\[ 15 = 3 \times 5 \] \[ \phi(15) = 15 \left(1 - \frac{1}{3}\right) \left(1 - \frac{1}{5}\right) = 15 \times \frac{2}{3} \times \frac{4}{5} = 8 \]

Euler’s Totient Values

Totient function values for selected numbers.

Applications

Number theory powers diverse fields with practical applications.

RSA Cryptography

Using primes \( p = 11 \), \( q = 13 \):

\[ n = 11 \times 13 = 143 \] \[ \phi(143) = (11-1) \times (13-1) = 10 \times 12 = 120 \] \[ e = 7, \quad 7d \equiv 1 \pmod{120}, \quad d = 103 \]

Public key: \( (7, 143) \), private key: \( (103, 143) \).

Fibonacci in Nature

Fibonacci ratios approach the golden ratio:

\[ \frac{8}{5} = 1.6, \quad \frac{13}{8} = 1.625 \approx \phi \approx 1.618 \]

Hash Functions

For \( k = 123 \), \( m = 17 \):

\[ h(123) = 123 \pmod{17} = 4 \]

Error-Correcting Codes

Hamming codes use modular arithmetic for parity checks:

\[ \text{Position 1 checks bits 1, 3, 5, …} \]

Music Theory

Cycles of 12 and 15 beats sync at:

\[ \text{LCM}(12, 15) = \frac{12 \times 15}{\text{GCD}(12, 15)} = \frac{180}{3} = 60 \]

Zeller’s Congruence

Day of week for March 14, 2025:

\[ h = \left( 14 + \left\lfloor \frac{13 \times 4}{5} \right\rfloor + 25 + \left\lfloor \frac{25}{4} \right\rfloor - \left\lfloor \frac{20}{100} \right\rfloor + \left\lfloor \frac{20}{400} \right\rfloor + 6 \right) \pmod{7} \] \[ = (14 + 10 + 25 + 6 - 0 + 0 + 6) \pmod{7} = 61 \pmod{7} = 5 \]

Result: Friday.