Master divisibility rules and prime number theory through comprehensive SageMath computations. Explore fundamental concepts including divisors, multiples, prime factorization, and primality testing using computational number theory. Interactive Jupyter notebook on CoCalc demonstrates mathematical proofs with step-by-step SageMath code examples for deep understanding.

Published/Number Theory/Divisibility and Prime Numbers with SageMath in CoCalc/Divisibility and Prime Numbers with SageMath in CoCalc.ipynb

⁵⁴ views
ubuntu2404

Kernel: SageMath 10.7

Divisibility and Prime Numbers: Foundations of Number Theory

Learning Objectives

By completing this notebook, you will:

Master the concept of divisibility and its properties
Understand prime numbers as fundamental building blocks
Apply the Euclidean algorithm for GCD computation
Use prime factorization to solve practical problems
Explore connections to cryptography and computer science

Prerequisites

Basic arithmetic operations
Understanding of multiplication and division
Familiarity with Python/SageMath syntax

Historical Context

Number theory, often called the "Queen of Mathematics" by Gauss, has ancient roots:

300 BCE: Euclid's Elements proved infinitely many primes exist and developed the Euclidean algorithm
250 CE: Diophantus studied integer solutions to equations
1640: Pierre de Fermat founded modern number theory with his famous theorems
1801: Carl Friedrich Gauss published Disquisitiones Arithmeticae, systematizing number theory
Today: Prime numbers secure internet communications through RSA encryption

What began as pure mathematics now protects billions of digital transactions daily!

In [3]:

# Initialize SageMath environment
from sage.all import *
import matplotlib.pyplot as plt

print("Number Theory: Divisibility and Primes")
print("="*40)
print("SageMath environment initialized")
print(f"Working with integers in ℤ")

Out[3]:

Number Theory: Divisibility and Primes
========================================
SageMath environment initialized
Working with integers in ℤ

Part 1: Divisibility - The Foundation

Definition

For integers $a$ and $b$ with $a \neq 0$ , we say " $a$ divides $b$ " (written $a \mid b$ ) if there exists an integer $k$ such that:

b = a \cdot k

Equivalently:

$b$ is a multiple of $a$
$a$ is a divisor (or factor) of $b$
$b \mod a = 0$ (remainder is zero)

Properties

Reflexivity: $a \mid a$ for all $a \neq 0$
Transitivity: If $a \mid b$ and $b \mid c$ , then $a \mid c$
Linear combination: If $a \mid b$ and $a \mid c$ , then $a \mid (bx + cy)$ for any integers $x, y$

In [4]:

# Divisibility testing and exploration
def explore_divisibility(a, b):
    """Explore divisibility relationship between a and b"""
    divides = b % a == 0
    quotient = b // a
    remainder = b % a
    
    print(f"Testing: {a} | {b}")
    print(f"  Division: {b} = {a} × {quotient} + {remainder}")
    print(f"  {a} divides {b}: {divides}")
    
    if divides:
        print(f"   {b} is a multiple of {a}")
    else:
        print(f"   {b} is not divisible by {a}")
    print()
    
    return divides

# Test various divisibility relationships
test_pairs = [(3, 12), (4, 15), (5, 20), (7, 21), (6, 25)]

print("Divisibility Examples:")
print("-"*40)
for a, b in test_pairs:
    explore_divisibility(a, b)

Out[4]:

Divisibility Examples:
----------------------------------------
Testing: 3 | 12
  Division: 12 = 3 × 4 + 0
  3 divides 12: True
   12 is a multiple of 3

Testing: 4 | 15
  Division: 15 = 4 × 3 + 3
  4 divides 15: False
   15 is not divisible by 4

Testing: 5 | 20
  Division: 20 = 5 × 4 + 0
  5 divides 20: True
   20 is a multiple of 5

Testing: 7 | 21
  Division: 21 = 7 × 3 + 0
  7 divides 21: True
   21 is a multiple of 7

Testing: 6 | 25
  Division: 25 = 6 × 4 + 1
  6 divides 25: False
   25 is not divisible by 6

In [5]:

# Finding all divisors
def find_divisors(n):
    """Find all positive divisors of n"""
    divisors = []
    for d in range(1, int(n**0.5) + 1):
        if n % d == 0:
            divisors.append(d)
            if d != n // d:  # Avoid duplicate for perfect squares
                divisors.append(n // d)
    return sorted(divisors)

# Demonstrate divisor finding
test_numbers = [24, 36, 100]
print("Finding All Divisors:")
print("-"*40)

for n in test_numbers:
    divisors = find_divisors(n)
    print(f"Divisors of {n}: {divisors}")
    print(f"  Number of divisors: {len(divisors)}")
    print(f"  Sum of divisors: {sum(divisors)}")
    
    # Check if perfect number (sum of proper divisors equals n)
    proper_sum = sum(divisors[:-1])  # Exclude n itself
    if proper_sum == n:
        print(f"  ⭐ {n} is a PERFECT number!")
    print()

Out[5]:

Finding All Divisors:
----------------------------------------
Divisors of 24: [1, 2, 3, 4, 6, 8, 12, 24]
  Number of divisors: 8
  Sum of divisors: 60

Divisors of 36: [1, 2, 3, 4, 6, 9, 12, 18, 36]
  Number of divisors: 9
  Sum of divisors: 91

Divisors of 100: [1, 2, 4, 5, 10, 20, 25, 50, 100]
  Number of divisors: 9
  Sum of divisors: 217

Part 2: Prime Numbers - The Atoms of Arithmetic

Definition

A natural number $p > 1$ is prime if it has exactly two positive divisors: 1 and $p$ itself.

Fundamental Theorem of Arithmetic

Every integer $n > 1$ can be represented uniquely as a product of prime powers:

n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}

where $p_1 < p_2 < \ldots < p_k$ are primes and $a_i > 0$ .

Why Primes Matter

Cryptography: RSA encryption relies on difficulty of factoring large numbers
Computer Science: Hash tables, random number generation
Nature: Cicada life cycles, crystal structures

In [6]:

# Prime checking - multiple methods
def is_prime_trial(n):
    """Check primality by trial division"""
    if n < 2:
        return False
    if n == 2:
        return True
    if n % 2 == 0:
        return False
    
    # Only check odd divisors up to √n
    for d in range(3, int(n**0.5) + 1, 2):
        if n % d == 0:
            return False
    return True

# Compare with SageMath's built-in
print("Prime Checking Comparison:")
print("-"*40)
test_nums = [17, 18, 91, 97, 121, 127]

for n in test_nums:
    trial = is_prime_trial(n)
    sage_check = is_prime(n)
    
    print(f"{n:3}: Trial={trial}, SageMath={sage_check}", end="")
    
    if not trial:
        # Find a factor
        for d in range(2, int(n**0.5) + 1):
            if n % d == 0:
                print(f" (factor: {d}×{n//d})")
                break
    else:
        print("  PRIME")

Out[6]:

Prime Checking Comparison:
----------------------------------------
Trial=True, SageMath=True  PRIME
Trial=False, SageMath=False (factor: 2×9)
Trial=False, SageMath=False (factor: 7×13)
Trial=True, SageMath=True  PRIME
Trial=False, SageMath=False (factor: 11×11)
Trial=True, SageMath=True  PRIME

In [7]:

# The Sieve of Eratosthenes - ancient algorithm (276-194 BCE)
def sieve_of_eratosthenes(limit):
    """Find all primes up to limit using the Sieve of Eratosthenes"""
    if limit < 2:
        return []
    
    # Initialize sieve
    is_prime = [True] * (limit + 1)
    is_prime[0] = is_prime[1] = False
    
    # Sieving process
    for p in range(2, int(limit**0.5) + 1):
        if is_prime[p]:
            # Mark multiples of p as composite
            for multiple in range(p*p, limit + 1, p):
                is_prime[multiple] = False
    
    # Collect primes
    primes = [i for i in range(limit + 1) if is_prime[i]]
    return primes

# Generate primes
limit = 100
primes = sieve_of_eratosthenes(limit)

print(f"Primes up to {limit}:")
print("-"*40)
print(f"Found {len(primes)} primes:")
print(primes[:20], "..." if len(primes) > 20 else "")

# Prime counting function π(x)
print(f"\nPrime counting function π(x):")
for x in [10, 25, 50, 100]:
    count = len([p for p in primes if p <= x])
    print(f"  π({x:3}) = {count:2} primes")

Out[7]:

Primes up to 100:
----------------------------------------
Found 25 primes:
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71] ...

Prime counting function π(x):
  π( 10) =  4 primes
  π( 25) =  9 primes
  π( 50) = 15 primes
  π(100) = 25 primes

Part 3: Prime Factorization

Every composite number can be uniquely decomposed into prime factors. This is like finding the "DNA" of a number.

In [8]:

# Prime factorization implementation
def prime_factorization(n):
    """Find prime factorization of n"""
    if n < 2:
        return []
    
    factors = []
    d = 2
    
    # Check for factor of 2
    while n % 2 == 0:
        factors.append(2)
        n //= 2
    
    # Check odd factors
    d = 3
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 2
    
    # If n is still > 1, it's prime
    if n > 1:
        factors.append(n)
    
    return factors

# Test factorization
test_numbers = [60, 100, 273, 1001, 2025]
print("Prime Factorizations:")
print("-"*50)

for n in test_numbers:
    factors = prime_factorization(n)
    
    # Group factors
    from collections import Counter
    factor_counts = Counter(factors)
    
    # Format output
    factorization = " × ".join([f"{p}^{e}" if e > 1 else str(p) 
                                for p, e in sorted(factor_counts.items())])
    
    print(f"{n:4} = {factorization}")
    
    # Verify with SageMath
    sage_factors = factor(n)
    print(f"       SageMath: {sage_factors}")
    print()

Out[8]:

Prime Factorizations:
--------------------------------------------------
  60 = 2^2 × 3 × 5
       SageMath: 2^2 * 3 * 5

 100 = 2^2 × 5^2
       SageMath: 2^2 * 5^2

 273 = 3 × 7 × 13
       SageMath: 3 * 7 * 13

1001 = 7 × 11 × 13
       SageMath: 7 * 11 * 13

2025 = 3^4 × 5^2
       SageMath: 3^4 * 5^2

Part 4: Greatest Common Divisor (GCD)

The GCD of two numbers is the largest positive integer that divides both. Euclid's algorithm (300 BCE) efficiently computes this:

\gcd(a, b) = \gcd(b, a \bmod b)

In [9]:

# Implement Euclidean algorithm
def euclidean_gcd(a, b, show_steps=False):
    """Compute GCD using Euclidean algorithm"""
    steps = []
    
    while b != 0:
        q, r = divmod(a, b)
        steps.append(f"{a} = {b} × {q} + {r}")
        a, b = b, r
    
    if show_steps:
        for step in steps:
            print(f"  {step}")
    
    return a

# Demonstrate the algorithm
pairs = [(48, 18), (100, 35), (1071, 462)]

print("Euclidean Algorithm for GCD:")
print("-"*40)

for a, b in pairs:
    print(f"\ngcd({a}, {b}):")
    result = euclidean_gcd(a, b, show_steps=True)
    print(f"  Result: {result}")
    
    # Verify with SageMath
    sage_gcd = gcd(a, b)
    print(f"  SageMath: {sage_gcd}")
    
    # Show relationship to factors
    print(f"  {a} = {result} × {a//result}")
    print(f"  {b} = {result} × {b//result}")

Out[9]:

Euclidean Algorithm for GCD:
----------------------------------------

gcd(48, 18):
  48 = 18 × 2 + 12
  18 = 12 × 1 + 6
  12 = 6 × 2 + 0
  Result: 6
  SageMath: 6
  48 = 6 × 8
  18 = 6 × 3

gcd(100, 35):
  100 = 35 × 2 + 30
  35 = 30 × 1 + 5
  30 = 5 × 6 + 0
  Result: 5
  SageMath: 5
  100 = 5 × 20
  35 = 5 × 7

gcd(1071, 462):
  1071 = 462 × 2 + 147
  462 = 147 × 3 + 21
  147 = 21 × 7 + 0
  Result: 21
  SageMath: 21
  1071 = 21 × 51
  462 = 21 × 22

Part 5: Least Common Multiple (LCM)

The LCM is the smallest positive integer divisible by both numbers.

Key Relationship

\gcd(a, b) \times \text{lcm}(a, b) = a \times b

This beautiful relationship connects GCD and LCM!

In [10]:

# LCM computation and verification
def compute_lcm(a, b):
    """Compute LCM using GCD relationship"""
    return (a * b) // gcd(a, b)

# Test the GCD-LCM relationship
print("GCD-LCM Relationship:")
print("-"*60)
print("Theorem: gcd(a,b) × lcm(a,b) = a × b")
print()

test_pairs = [(12, 18), (15, 20), (7, 21), (24, 36)]

for a, b in test_pairs:
    g = gcd(a, b)
    l = lcm(a, b)
    product = a * b
    
    print(f"a={a}, b={b}:")
    print(f"  gcd({a},{b}) = {g}")
    print(f"  lcm({a},{b}) = {l}")
    print(f"  gcd × lcm = {g} × {l} = {g*l}")
    print(f"  a × b = {a} × {b} = {product}")
    print(f"  Relationship holds: {g*l == product} ")
    print()

Out[10]:

GCD-LCM Relationship:
------------------------------------------------------------
Theorem: gcd(a,b) × lcm(a,b) = a × b

a=12, b=18:
  gcd(12,18) = 6
  lcm(12,18) = 36
  gcd × lcm = 6 × 36 = 216
  a × b = 12 × 18 = 216
  Relationship holds: True 

a=15, b=20:
  gcd(15,20) = 5
  lcm(15,20) = 60
  gcd × lcm = 5 × 60 = 300
  a × b = 15 × 20 = 300
  Relationship holds: True 

a=7, b=21:
  gcd(7,21) = 7
  lcm(7,21) = 21
  gcd × lcm = 7 × 21 = 147
  a × b = 7 × 21 = 147
  Relationship holds: True 

a=24, b=36:
  gcd(24,36) = 12
  lcm(24,36) = 72
  gcd × lcm = 12 × 72 = 864
  a × b = 24 × 36 = 864
  Relationship holds: True 

Part 6: Real-World Applications

In [11]:

# Application 1: Synchronization Problems
print("Application 1: Traffic Light Synchronization")
print("-"*50)

# Three traffic lights with different cycles
light_A = 45  # seconds
light_B = 60  # seconds
light_C = 75  # seconds

# When do all lights turn green together?
sync_time = lcm(lcm(light_A, light_B), light_C)

print(f"Light A cycles every {light_A} seconds")
print(f"Light B cycles every {light_B} seconds")
print(f"Light C cycles every {light_C} seconds")
print(f"\nAll lights synchronize every {sync_time} seconds ({sync_time//60} minutes)")

# Show synchronization pattern
print(f"\nSynchronization times (minutes): ", end="")
for i in range(1, 6):
    print(f"{i*sync_time//60}", end=" ")
print("...")

Out[11]:

Application 1: Traffic Light Synchronization
--------------------------------------------------
Light A cycles every 45 seconds
Light B cycles every 60 seconds
Light C cycles every 75 seconds

All lights synchronize every 900 seconds (15 minutes)

Synchronization times (minutes): 15 30 45 60 75 ...

In [12]:

# Application 2: Cryptography (RSA preview)
print("\nApplication 2: RSA Encryption (Simplified)")
print("-"*50)

# Choose two small primes (in practice, these are hundreds of digits)
p = 61
q = 53

# Compute n = p × q
n = p * q

# Euler's totient function
phi = (p - 1) * (q - 1)

print(f"Prime p = {p}")
print(f"Prime q = {q}")
print(f"Public modulus n = p × q = {n}")
print(f"Euler's totient φ(n) = {phi}")

# Find public exponent e (coprime to φ)
e = 17
while gcd(e, phi) != 1:
    e += 2

print(f"Public exponent e = {e} (gcd(e, φ) = {gcd(e, phi)})")

print("\nSecurity relies on:")
print(f"- Difficulty of factoring n = {n}")
print(f"- Without knowing p and q, cannot compute φ(n)")
print(f"- Without φ(n), cannot find private key")

Out[12]:

Application 2: RSA Encryption (Simplified)
--------------------------------------------------
Prime p = 61
Prime q = 53
Public modulus n = p × q = 3233
Euler's totient φ(n) = 3120
Public exponent e = 17 (gcd(e, φ) = 1)

Security relies on:
- Difficulty of factoring n = 3233
- Without knowing p and q, cannot compute φ(n)
- Without φ(n), cannot find private key

In [13]:

# Application 3: Music Theory - Frequency Ratios
print("\nApplication 3: Musical Harmony")
print("-"*50)

intervals = [
    ("Octave", 2, 1),
    ("Perfect Fifth", 3, 2),
    ("Perfect Fourth", 4, 3),
    ("Major Third", 5, 4),
    ("Minor Third", 6, 5)
]

print("Musical intervals as frequency ratios:\n")

base_freq = 440  # A4 note

for name, num, den in intervals:
    ratio = num / den              # Sage Rational
    new_freq = base_freq * ratio   # Sage Rational
    g = gcd(num, den)

    print(f"{name:15}: {num}:{den}", end="")
    if g == 1:
        print(" (simplest form)")
    else:
        print(f" (reduces to {num//g}:{den//g})")

    print(f"  From A={base_freq}Hz → {float(new_freq):.1f}Hz")

Out[13]:

Application 3: Musical Harmony
--------------------------------------------------
Musical intervals as frequency ratios:

Octave         : 2:1 (simplest form)
  From A=440Hz → 880.0Hz
Perfect Fifth  : 3:2 (simplest form)
  From A=440Hz → 660.0Hz
Perfect Fourth : 4:3 (simplest form)
  From A=440Hz → 586.7Hz
Major Third    : 5:4 (simplest form)
  From A=440Hz → 550.0Hz
Minor Third    : 6:5 (simplest form)
  From A=440Hz → 528.0Hz

Interactive Exploration with CoCalc

CoCalc's SageMath environment provides powerful number theory tools:

Built-in Functions: is_prime(), factor(), gcd(), lcm()
Advanced Features: Miller-Rabin primality testing, quadratic sieve factoring
Symbolic Computation: Exact arithmetic, no floating-point errors
Visualization: Plot prime distributions, factor trees

Practice Exercises

Find all perfect numbers less than 10,000 (numbers equal to sum of proper divisors)
Implement the extended Euclidean algorithm to find Bézout coefficients
Explore twin primes (primes differing by 2) up to 1000
Factor Fermat numbers: $F_n = 2^{2^n} + 1$
Investigate Goldbach's conjecture for even numbers up to 100

Summary

We've explored fundamental concepts in number theory:

Divisibility: The basic relationship between integers
Prime Numbers: The building blocks of all integers
Prime Factorization: Unique decomposition theorem
GCD and LCM: Connected by a beautiful relationship
Applications: From ancient algorithms to modern cryptography

These concepts form the foundation for advanced topics in:

Modular arithmetic and congruences
Quadratic residues and reciprocity
Elliptic curves and modern cryptography

Next Steps: Explore modular arithmetic and the Chinese Remainder Theorem!

Divisibility and Prime Numbers: Foundations of Number Theory

Learning Objectives

Prerequisites

Historical Context

Part 1: Divisibility - The Foundation

Definition

Properties

Part 2: Prime Numbers - The Atoms of Arithmetic

Definition

Fundamental Theorem of Arithmetic

Why Primes Matter

Part 3: Prime Factorization

Part 4: Greatest Common Divisor (GCD)

Part 5: Least Common Multiple (LCM)

Key Relationship

Part 6: Real-World Applications

Interactive Exploration with CoCalc

Practice Exercises

Summary

Product

Resources

Company