Divisibility and Prime Numbers

Math for CS · Axiom Academy

The foundation of number theory Definition: What Does "Divides" Mean? Divisibility is the most fundamental concept in number theory. It describes how one integer relates to another through multiplication. because there is no integer k where 10 = 7k Divisibility has many useful algebraic properties: Transitivity: If a | b and b | c , then a | c . Example: Since 2 | 6 and 6 | 24 , we have 2 | 24 . Linear Combination: If a | b and a | c , then a | (mb + nc) for any integers m, n . Example: Since 3 | 6 and 3 | 9 , we have . Multiplication: If a | b , then a | bc for any integer c . Example: Since 4 | 12 , we have . Reflexivity: a | a for any non-zero integer a . One divides everything: 1 | n for every integer n . Quick ways to check if a number is divisible by small integers without doing long division: Every integer greater than 1 is either prime or composite based on its divisors. Exactly 2 divisors: 1 and itself Special: 1 has exactly 1 divisor a | b means b = ak for some integer k Divisibility has useful properties: transitivity, linear combinations, multiplication Divisibility rules let us check divisibility by 2-10 quickly Primes are fundamental building blocks in number theory Understanding divisibility is essential for GCD, cryptography, and algorithm analysis

This is the written version of the interactive lesson above. See the full Math for CS course.