Prime and composite numbers

Learning Objectives Rigorously define prime and composite numbers and distinguish between them. Prove whether a given integer is prime or composite using efficient trial division. Apply the Fundamental Theorem of Arithmetic to express any composite number as a unique product of prime factors. Use prime factorization to find the total number of positive divisors for any given integer. Calculate the Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of large integers using their prime factorizations. Solve problems involving the properties of prime and composite numbers. Ever wondered how your online messages stay secret? 🤫 It all starts with massive numbers that have only two factors. This tutorial moves beyond basic definitions to explore the profound properties...

TermDefinitionExample Prime NumberA natural number greater than 1 that has no positive divisors other than 1 and itself.17 is a prime number because its only positive divisors are 1 and 17. Composite NumberA natural number greater than 1 that is not prime; it has at least one divisor other than 1 and itself.24 is a composite number because its divisors are 1, 2, 3, 4, 6, 8, 12, and 24. The Number 1A special case that is neither prime nor composite. It is a 'unit' and has only one positive divisor: itself.The number 1 has only one factor, which is 1. Prime FactorizationThe process of expressing a composite number as a unique product of its prime factors.The prime factorization of 90 is 2 × 3 × 3 × 5, which is written in exponential form as 2 × 3² × 5. Fundamental Theorem of Arith...

Efficient Primality Test (Trial Division) To test if an integer n is prime, check for divisibility by all prime numbers p such that p² ≤ n. If n is not divisible by any prime p up to its square root, then n must be prime. This is far more efficient than checking all integers up to n. Number of Divisors Formula If the prime factorization of N is N = p₁ᵃ¹ × p₂ᵃ² × ... × pₖᵃᵏ, then the total number of positive divisors of N is d(N) = (a₁ + 1)(a₂ + 1)...(aₖ + 1). This formula allows you to quickly calculate the total count of factors for any composite number directly from the exponents of its prime factorization. GCD and LCM via Prime Factorization For A = p₁ᵃ¹p₂ᵃ²... and B = p₁ᵇ¹p₂ᵇ²..., GCD(A, B) = p₁ᵐⁱⁿ(ᵃ¹, ᵇ¹)p₂ᵐⁱⁿ(ᵃ², ᵇ²)... and LCM(A, B) = p₁ᵐᵃˣ(ᵃ¹, ᵇ¹)p₂ᵐᵃˣ(ᵃ², ᵇ²)....