Visual Tools
Calculators
Tables
Mathematical Keyboard
Converters
Other Tools


Divisibility






When Division Leaves Nothing Behind

Some divisions come out clean — 12÷312 ÷ 3 gives exactly 44, with nothing left over. Others do not — 13÷313 ÷ 3 leaves a remainder of 11. Divisibility is the study of when and why the first case occurs, and the consequences that follow from it. The concept threads through factoring, primes, common divisors, and the internal structure of the integers themselves.

Key Terms

Divisor (Factor)— the integer that divides another exactly
Multiple— the result of multiplying a number by any integer
Prime Number— an integer greater than 1 with no divisors other than 1 and itself
Composite Number— an integer with at least one divisor beyond 1 and itself
Prime Factorization— the unique decomposition into a product of primes
Coprime— two integers sharing no common factor other than 1
Greatest Common Divisor— the largest integer dividing both of two given integers
Least Common Multiple— the smallest positive integer divisible by both of two given integers

See All Arithmetic Definitions →


What is Divisibility?

Six sharing problems, all with whole cookies: which ones split evenly, with nothing left over?
1212 cookies among 33 children; 1212 among 55; 2020 among 44; 3030 among 77; 33 among 1212; and 00 cookies among 66 children.
Handing them out settles it: 12 among 3, 20 among 4 and 0 among 6 come out even; the other three do not.
cookieschildreneach getsleft overeven split?
12340yes
12522no
20450yes
30742no
31203 — not one eachno
0600yes — nothing to share
Every failure leaves cookies over that could only be shared by breaking them.
The expression 3∣123 \mid 12 is true because 12=3⋅412 = 3 \cdot 4. The expression 5∣125 \mid 12 is false because no integer kk satisfies 12=5⋅k12 = 5 \cdot k — the closest are 5⋅2=105 \cdot 2 = 10 and 5⋅3=155 \cdot 3 = 15, neither of which equals 1212.
The expression 4∣204 \mid 20 is true because 20=4⋅520 = 4 \cdot 5. The expression 7∣307 \mid 30 is false because 30=7⋅4+230 = 7 \cdot 4 + 2 — a remainder of 22 survives.
A split is even exactly when the number of cookies is the number of children times a whole number.
Number line scene (single track)03691215+3+3+3+33 | 1212 = 3 · 4Four jumps of 3 landexactly on 12.
Number line scene (single track)05101512+5+5overshoots12 falls in this gap5 ∤ 125·2 = 10, 5·3 = 15No multiple of 5 landson 12: 10 < 12 < 15.
4 groups of 5 — Divisible ✓5555
20 tiles in 4 groups of 5: divisible

Twenty tiles fill four complete rows of five with nothing left over, so 5 divides 20 and 20 = 5 · 4 with k = 4: the definition a | b drawn as a full rectangle. A single leftover tile would break the rectangle and the divisibility with it. Change the number or the divisor and watch the rows fill or fail on the divisibility tiles visualizer.

Divisibility is a statement about rectangles: b tiles can be arranged in rows of exactly a.
The definition
An integer aa divides an integer bb, written a∣ba \mid b, when b=a⋅kb = a \cdot k for some integer kk; then bb is a multiple of aa.
An integer aa divides an integer bb when bb equals aa multiplied by some integer kk, with no remainder:
What is Divisibility?
a∣bmeansb=a⋅k   for some integer ka \mid b \quad \text{means} \quad b = a \cdot k \;\text{ for some integer } k
So 3∣123 \mid 12, 4∣204 \mid 20 and 6∣06 \mid 0 are true; 5∣125 \mid 12, 7∣307 \mid 30 and 12∣312 \mid 3 are false.
Divisibility is a yes-or-no relation between two integers — not a number, and not an operation.
Divisibility is a yes-or-no question. Either aa fits into bb a whole number of times, or it does not. There is no "almost divides" or "partially divides."
The order matters: 3 ∣ 12 is true but 12 ∣ 3 is false — and the bar is not a fraction bar.
Pitfall: Reading the bar as division
Reading 3∣123 \mid 12 as 3÷12=0.253 \div 12 = 0.25 makes a true statement look false. The divisor comes first: 3∣123 \mid 12 asks whether 12÷312 \div 3 is a whole number, and it is, while 12∣312 \mid 3 is false.
What is left over when the split fails, and how it decides divisibility, is the subject of divisibility and remainders.
The rest of the page covers notation, basic properties, divisibility and remainders, divisibility rules, factors and multiples, prime numbers, prime factorization, and the GCD and LCM.

Divisibility Notation

Notation

Divisibility Notation

One vertical stroke carries the whole subtree: the bar that states, the slash that denies, and the remainder spelling that computes the same fact. Every symbol here is catalogued among the arithmetic symbols with its LaTeX code, and the mathematical keyboard types them directly. The table below collects the five spoken phrasings of one statement.
gcd⁡(a,b)\gcd(a,b) and lcm⁡(a,b)\operatorname{lcm}(a,b) are introduced on their own pages; the congruence triple-bar ≡\equiv belongs to modulo.
a∣ba \mid b
a divides b
A statement, not an operation: a∣ba \mid b is true or false — it claims b=a⋅kb = a \cdot k for some integer kk and produces no number, unlike ÷\div, which computes. What is Divisibility? above sets the definition.
CasesFive spoken phrasings share the one mark — divides, is divisible by, is a divisor of, is a factor of, is a multiple of — each shifting emphasis, none changing the fact; the table below lines them up for 3∣123 \mid 12.
Do not confuseDivision's argument order. In 3∣123 \mid 12 the small number leads; in 12÷312 \div 3 it trails — the bar and the division sign read their operands in opposite directions, the subtree's most reliable misreading.
Same glyph elsewhereThe identical stroke is "such that" inside set-builder braces and, doubled, the absolute value fence — position decides the job.
5∤125 \nmid 12
five does not divide twelve
The slashed bar denies: 5∤125 \nmid 12 because no integer kk gives 12=5k12 = 5k. One stroke through the mark manufactures the negation — the same slash-negation family that builds ≠\neq and ∉\notin.
CasesThe negation stays a statement — false claims become true denials; proofs by contradiction lean on it, assuming a∣ba \mid b and deriving a∤ba \nmid b.
Do not confuseA fraction slash. The stroke negates the bar, it does not divide anything — 5∤125 \nmid 12 has no numeric value, while 5/125/12 is a number.
b mod a=0b \bmod a = 0
b mod a equals zero
The computational spelling of the same fact: a∣ba \mid b exactly when the remainder vanishes — one statement, two dialects, as Divisibility and Remainders below works out. The  mod \bmod operator itself is owned by the modulo page.
CasesThe bridge runs both ways: theory prefers the bar (3∣123 \mid 12), computation the remainder test (12 % 3 == 0 in code) — choosing the dialect is choosing the audience.
Do not confuseThe congruence triple-bar. b mod a=0b \bmod a = 0 is an equation about a computed remainder; b≡0(moda)b \equiv 0 \pmod a states the same thing in congruence dress — interchangeable in content, different in grammar.
DownloadPNG2×PDF
Notation · Cheat sheet
Arithmetic Notation at a Glance
The marks from the notation cards across the arithmetic pages: how each is read and what it means. Every group links to the full card on its page.
Fractions
ab\frac{a}{b}
a over b
The vinculum: numerator over denominator, a division held in place.
a/ba/b
a slash b; a over b
The inline spelling for running text and code; same value, no grouping power.
a÷ba \div b
a divided by b
The obelus, the schoolroom division sign: a÷b=aba \div b = \frac{a}{b}.
Mixed numbers
2342\frac{3}{4}
two and three quarters
Adjacency means addition here, and only here: 2+342 + \frac{3}{4}.
3543\frac{5}{4} vs 4144\frac{1}{4}
non-standard form, and its correction
The fractional part must be proper; carry the extra whole.
−234-2\frac{3}{4}
negative two and three quarters
The minus grips the whole package: −(2+34)-(2 + \frac{3}{4}).
DivisibilityThis page
a∣ba \mid b
a divides b
A statement, true or false: b=a⋅kb = a \cdot k for some integer kk.
5∤125 \nmid 12
five does not divide twelve
The slashed bar denies: no integer kk gives 12=5k12 = 5k.
b mod a=0b \bmod a = 0
b mod a equals zero
The same fact as a computation: the remainder vanishes.
Factors
n=p1a1⋯pkakn = p_1^{a_1} \cdots p_k^{a_k}
n as a product of prime powers
Canonical factorisation: pp for primes, exponents count repeats.
d(n)d(n) · τ(n)\tau(n)
d of n; tau of n
The number of positive divisors of nn.
σ(n)\sigma(n)
sigma of n
The sum of the positive divisors: σ(12)=28\sigma(12) = 28.
GCD
gcd⁡(a,b)\gcd(a, b)
the g-c-d of a and b
Greatest common divisor, in function spelling.
HCF, GCF\text{HCF, GCF}
highest, or greatest, common factor
Other names for the gcd: HCF in British and Indian schools, GCF in American schools.
gcd⁡(a,b)=1\gcd(a, b) = 1
a and b are coprime
The equation is the notation; coprimality has no mark of its own.
LCM
lcm⁡(a,b)\operatorname{lcm}(a, b)
the l-c-m of a and b
Least common multiple, the mirror twin of gcd⁡\gcd.
[a,b][a, b]
bracket a, b
Number theory’s shorthand for the lcm; (a,b)(a, b) is the gcd.
LCM vs LCD\text{LCM vs LCD}
least common multiple; least common denominator
The LCD of fractions is the LCM of their denominators.
Modulo
a mod na \bmod n
a mod n
The operator that computes a remainder: 17 mod 5=217 \bmod 5 = 2.
a % na \ \% \ n
a percent n
The remainder operator in code: C, Java, Python, JavaScript.
a≡b(modn)a \equiv b \pmod{n}
a is congruent to b modulo n
A statement: aa and bb leave the same remainder.
Integer part
⌊x⌋\lfloor x \rfloor
floor of x
The greatest integer at most xx: the integer part.
⌈x⌉\lceil x \rceil
ceiling of x
The least integer at least xx.
{x}\{x\}
fractional part of x
What the floor leaves: x−⌊x⌋x - \lfloor x \rfloor, in [0,1)[0, 1).
⌊x+12⌋\lfloor x + \tfrac{1}{2} \rfloor
x rounded to the nearest integer
Rounding built from the floor; ties go up: 2.5→32.5 \to 3.
Same marks, different job
a∣ba \mid bDivides, between integers; such that, inside set braces; absolute value when doubled.
(a,b)(a, b) vs [a,b][a, b]The gcd and the lcm in number-theory shorthand; a point or an interval elsewhere.
{x}\{x\}The fractional part here; a one-element set in set theory.
 mod \bmod vs (modn)\pmod{n}An operator that returns a number; a label on a congruence statement.
σ(n)\sigma(n)The divisor sum here; a standard deviation in statistics.
Arithmetic Notation at a Glance·/arithmeticLearn Math Class
DownloadPNG2×PDF
Layout
PhrasingExample (with 3 ∣ 12)What it foregrounds
"a divides b"3 divides 12the divisor a — the one doing the dividing
"b is divisible by a"12 is divisible by 3the dividend b — the perspective of the number being divided
"a is a divisor of b"3 is a divisor of 12a's role as one of b's divisors
"a is a factor of b"3 is a factor of 12a as a multiplicative building block of b
"b is a multiple of a"12 is a multiple of 3b as a product of a and some integer
Divisibility NotationLearn Math Class

Basic Properties

Several properties follow immediately from the definition and hold for all integers.

Every nonzero integer divides itself: a∣aa \mid a, because a=a⋅1a = a \cdot 1.

The number 11 divides everything: 1∣a1 \mid a for any aa, because a=1⋅aa = 1 \cdot a.

Every nonzero integer divides 00: a∣0a \mid 0, because 0=a⋅00 = a \cdot 0. Zero is a multiple of every number.

Zero divides nothing except itself: 0∣b0 \mid b requires b=0⋅k=0b = 0 \cdot k = 0, so the only value bb can take is 00.

Divisibility is transitive. If a∣ba \mid b and b∣cb \mid c, then a∣ca \mid c. If 3∣123 \mid 12 and 12∣6012 \mid 60, then 3∣603 \mid 60.

Divisibility distributes over addition and subtraction. If a∣ba \mid b and a∣ca \mid c, then a∣(b+c)a \mid (b + c) and a∣(b−c)a \mid (b - c). Since 4∣204 \mid 20 and 4∣124 \mid 12, it follows that 4∣324 \mid 32 and 4∣84 \mid 8.

Divisibility scales with multiplication. If a∣ba \mid b, then a∣(b⋅k)a \mid (b \cdot k) for any integer kk. Since 3∣123 \mid 12, it follows that 3∣363 \mid 36, 3∣603 \mid 60, 3∣1203 \mid 120, and so on.
DownloadPNG2×PDF
Layout
PropertyStatementExample
Reflexivityevery nonzero integer divides itself: a ∣ a7 ∣ 7, since 7 = 7 · 1
Universal divisor1 divides everything: 1 ∣ a for any integer a1 ∣ 100, since 100 = 1 · 100
Zero as multipleevery nonzero integer divides 0: a ∣ 07 ∣ 0, since 0 = 7 · 0
Transitivityif a ∣ b and b ∣ c, then a ∣ c3 ∣ 12 and 12 ∣ 60 ⇒ 3 ∣ 60
Distributionif a ∣ b and a ∣ c, then a ∣ (b + c) and a ∣ (b − c)4 ∣ 20 and 4 ∣ 12 ⇒ 4 ∣ 32 and 4 ∣ 8
Scalingif a ∣ b, then a ∣ (b · k) for any integer k3 ∣ 12 ⇒ 3 ∣ 36, 3 ∣ 60, 3 ∣ 120, …
Basic PropertiesLearn Math Class
Number line scene (single track)0369121518212427303336394245485154576063…3 | 12, 3 | 36, 3 | 60If 3 divides 12, it alsodivides every multiple of 12.

Divisibility and Remainders

For any integers aa and nn with n>0n > 0, the division algorithm guarantees:

Divisibility and Remainders
a=n⋅q+r,0≤r<na = n \cdot q + r, \qquad 0 \leq r < n

The integer qq is the quotient — how many complete copies of nn fit into aa. The integer rr is the remainder — what is left after those copies are removed.

Divisibility corresponds to the case r=0r = 0. When the remainder vanishes, the division is exact and n∣an \mid a. When r≠0r \neq 0, the division is inexact and n∤an \nmid a.

The operation that extracts rr directly is modulo. The statement a mod n=0a \bmod n = 0 is the computational form of n∣an \mid a. The statement a mod n≠0a \bmod n \neq 0 is the computational form of n∤an \nmid a. Divisibility poses the question; modulo computes the answer.

To find the remainder of any division quickly, use the modulo calculator.
Number line scene (single track)0714212830+7+7+7+7remainder = 230 = 7·4 + 27 ∤ 30Four jumps of 7 reach 28,remainder 2 left over.
4 groups of 5 + 3 leftover5555+3
23 = 5 · 4 + 3: four full rows and three left over

The four complete rows are the quotient q = 4 and the three tiles that could not start a fifth row are the remainder r = 3, with 0 ≤ 3 < 5 exactly as the division algorithm requires. The remainder is what stands between a number and the next multiple below it. Slide the number up by one tile at a time and watch the remainder cycle on the divisibility tiles visualizer.

Modulo arithmetic, treated on its own page, is the study of this leftover on its own.

Divisibility Rules

Testing whether one number divides another does not always require performing the full division. For certain common divisors, patterns in the decimal digits of a number provide instant answers.

A number is divisible by 22 if its last digit is even. By 55 if its last digit is 00 or 55. By 1010 if its last digit is 00. By 33 if the sum of its digits is divisible by 33. By 99 if the sum of its digits is divisible by 99.

Pitfall: Testing 3 by the last digit
Checking only the last digit, as for 22 and 55, gets 33 wrong both ways: 1313 ends in 33 but 3∤133 \nmid 13, and 2727 ends in 77 yet 27=3⋅927 = 3 \cdot 9. The digit sum decides: 1+3=41 + 3 = 4 is not a multiple of 33, and 2+7=92 + 7 = 9 is.

Each rule exploits the structure of base-1010 place value. The last digit determines divisibility by 22 and 55 because 1010 is divisible by both. The digit-sum rule for 99 works because 10≡1(mod9)10 \equiv 1 \pmod{9}, as explained on the modular arithmetic page.

These shortcuts are covered in full — with rules for 2,3,4,5,6,8,9,102, 3, 4, 5, 6, 8, 9, 10, and 1111 — on the divisibility rules page.
Learn More

Factors and Multiples

Every divisibility relationship names two roles. When a∣ba \mid b, the number aa is a factor (or divisor) of bb, and bb is a multiple of aa.

Pitfall: Mixing up factors and multiples
Calling 4848 a factor of 2424 swaps the two roles. Since 48=24⋅248 = 24 \cdot 2, it is 2424 that divides 4848: 4848 is a multiple of 2424, and 2424 is a factor of 4848.

The factors of a number are finite. The number 2424 has exactly eight factors: 1,2,3,4,6,8,12,241, 2, 3, 4, 6, 8, 12, 24. Every integer greater than 11 has at least two factors — 11 and itself — and most have more.

The multiples of a number are infinite. The multiples of 33 are 3,6,9,12,15,…3, 6, 9, 12, 15, \ldots — the list extends without end. Every positive integer generates an infinite sequence of multiples.

Factors come in pairs. If aa is a factor of nn, then na\frac{n}{a} is also a factor. For 2424: the pair (3,8)(3, 8) corresponds to 3⋅8=243 \cdot 8 = 24, and the pair (4,6)(4, 6) to 4⋅6=244 \cdot 6 = 24. Searching for factors only up to n\sqrt{n} is sufficient — every factor above the square root is already paired with one below it.
Factor pairsfactors of 24 — found by testing 1 to √24 ≈ 4.901 · 24 = 242 · 12 = 243 · 8 = 244 · 6 = 241234681224factors of 24 (in pairs)(1, 24), (2, 12),(3, 8), (4, 6)search stops at √24
The full treatment, including counting formulas and systematic methods, appears on the factors and multiples page.
A number has finitely many factors, paired around its square root, but infinitely many multiples.
Learn More

Prime Numbers

A prime number is an integer greater than 11 whose only factors are 11 and itself. The number 77 is prime — no integer other than 11 and 77 divides it. The number 1212 is not prime — it has factors 2,3,42, 3, 4, and 66 beyond 11 and 1212.

Primes are the atoms of multiplication. Every integer greater than 11 is either prime or can be built by multiplying primes together. The number 12=22⋅312 = 2^2 \cdot 3 is assembled from the primes 22 and 33. The number 30=2⋅3⋅530 = 2 \cdot 3 \cdot 5 from three primes.

Pitfall: Taking odd numbers for primes
Calling 99, 1515 or 9191 prime because they are odd misses 9=3⋅39 = 3 \cdot 3, 15=3⋅515 = 3 \cdot 5 and 91=7⋅1391 = 7 \cdot 13. Being odd only rules out the factor 22; an odd number still has to be tested against the odd primes.

The first primes are 2,3,5,7,11,13,17,19,23,29,…2, 3, 5, 7, 11, 13, 17, 19, 23, 29, \ldots — an infinite sequence with no largest member. The number 22 is the only even prime; every other even number is divisible by 22 and therefore composite.

The number 11 is not prime. It has only one factor (itself), while the definition requires exactly two. Excluding 11 is not a technicality — it is necessary to preserve the uniqueness of prime factorization.

To test whether a specific number is prime, use the prime number checker.

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100
The sieve finished: only the primes remain unmarked

Every multiple of 2, 3, 5 and 7 has been struck out in turn, and the numbers still standing are exactly those with no divisor other than 1 and themselves. A prime is what the sieve cannot remove. Run the crossing-out one prime at a time on the Sieve of Eratosthenes visualizer.

Primes are the atoms the next section builds every other integer from.

Prime Factorization

THEOREMFundamental Theorem of Arithmetic
The Fundamental Theorem of Arithmetic guarantees that every integer greater than 11 can be expressed as a product of primes, and that this expression is unique up to the order of the factors.

Fact: Where 441441 splits two ways
Among the numbers 1,5,9,13,17,…1, 5, 9, 13, 17, \ldots, each one more than a multiple of 44, the number 441441 splits as 9⋅499 \cdot 49 and as 21⋅2121 \cdot 21, and none of 99, 2121, 4949 splits further within the list. The primes 33 and 77 that would reconcile the two are missing from it.

The number 360360 factors as 23⋅32⋅52^3 \cdot 3^2 \cdot 5. No other combination of primes produces 360360. The number 8484 factors as 22⋅3⋅72^2 \cdot 3 \cdot 7. The factorization is a fingerprint — it identifies the number completely.

Uniqueness is the deeper half of the theorem. Existence is easy: any composite factor can be split again until only primes remain, as the factor tree for 360360 further down shows. That two different ways of splitting always end with the same primes needs a proof, and the proof rests on one property of primes: a prime that divides a product a⋅ba \cdot b divides aa or divides bb.

Prime factorization reveals the divisor structure of a number. The number of factors of n=p1a1⋅p2a2⋯n = p_1^{a_1} \cdot p_2^{a_2} \cdots is (a1+1)(a2+1)⋯(a_1 + 1)(a_2 + 1) \cdots — a formula that reads the answer directly from the exponents.

Pitfall: Multiplying the exponents
Counting the factors of 84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7 as 2⋅1⋅1=22 \cdot 1 \cdot 1 = 2 leaves out almost all of them. Adding 11 to each exponent gives (2+1)(1+1)(1+1)=12(2 + 1)(1 + 1)(1 + 1) = 12, the true count.

A factor of nn is built by deciding how many copies of each prime to take, from none up to the exponent. For 84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7, a factor takes 00, 11 or 22 twos, 00 or 11 three and 00 or 11 seven: for example 21⋅30⋅71=142^1 \cdot 3^0 \cdot 7^1 = 14. Different choices give different factors, by the uniqueness of the factorization.

Factorization also underpins the computation of GCD and LCM. The GCD takes the minimum exponent of each shared prime; the LCM takes the maximum. These connections are developed in the prime factorization methods on the GCD and LCM pages.

To find the prime factorization or all factors of a specific number, use the factoring calculator.
Prime factorization — 360 Prime factorization — 360 360 2 180 2 90 2 45 3 15 3 5 360 = 23 · 32 · 5 360 = 2³ · 3² · 5exponents 3, 2, 1factors of 360:(3+1)(2+1)(1+1) = 24
Factoring 360 down to primes

The factor tree splits 360 until every branch ends in a prime: 360 = 2 · 180 = 2 · 2 · 90, and so on, leaving the leaves 2, 2, 2, 3, 3, 5. Collected, that is 360 = 2³ · 3² · 5. A factor of 360 picks 0 to 3 twos, 0 to 2 threes and 0 or 1 five, so the exponents give the count directly: (3 + 1)(2 + 1)(1 + 1) = 24 factors.

Splitting 360 as 10 · 36 first gives a different tree but the same six prime leaves.

GCD and LCM

Two numbers may share common factors, and the largest of these is their greatest common divisor. The numbers 4848 and 3636 are both divisible by 1,2,3,4,61, 2, 3, 4, 6, and 1212. The largest — 1212 — is gcd⁡(48,36)\gcd(48, 36).

The least common multiple runs in the opposite direction. It is the smallest positive integer that both numbers divide into.

Example
For 44 and 66, the multiples of 44 are 4,8,12,16,…4, 8, 12, 16, \ldots and the multiples of 66 are 6,12,18,…6, 12, 18, \ldots. The smallest number in both lists is 1212, so lcm(4,6)=12\text{lcm}(4, 6) = 12.

The two quantities are linked by a clean identity:

GCD and LCM
a⋅b=gcd⁡(a,b)⋅lcm(a,b)a \cdot b = \gcd(a, b) \cdot \text{lcm}(a, b)

For 44 and 66: 4⋅6=244 \cdot 6 = 24, and gcd⁡(4,6)⋅lcm(4,6)=2⋅12=24\gcd(4,6) \cdot \text{lcm}(4,6) = 2 \cdot 12 = 24.

Pitfall: Multiplying to get the LCM
Taking 4⋅6=244 \cdot 6 = 24 as lcm(4,6)\text{lcm}(4, 6) gives a common multiple, but not the least: 1212 is smaller and both 44 and 66 divide it. The product equals the LCM only when the GCD is 11, as for 44 and 99.

Read the other way, the identity gives the LCM from the GCD: lcm(a,b)=a⋅bgcd⁡(a,b)\text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}. The product a⋅ba \cdot b is always a common multiple of the two numbers, and dividing it by their greatest common divisor brings it down to the least one.

Three methods exist for computing the GCD: listing factors, prime factorization, and the Euclidean algorithm — which uses modulo repeatedly to reduce the problem. The full treatment appears on the GCD and LCM pages.
252 = 105 · 2 + 42105 = 42 · 2 + 2142 = 21 · 2 + 0stopgcd = 21
gcd(252, 105) = 21 by repeated division

Each row divides the previous divisor by the previous remainder: 252 = 105 · 2 + 42, then 105 = 42 · 2 + 21, then 42 = 21 · 2 + 0. The last nonzero remainder, 21, is the greatest common divisor, found without factoring either number. Enter any pair and watch the remainders shrink to zero on the Euclidean algorithm visualizer.

The GCD and LCM pages develop each method in full, including the one this picture runs.

Related Concepts

Divisibility connects outward to several areas that approach the same ideas from different angles.

Modulo is the computational counterpart. Where divisibility asks a yes-or-no question — does nn divide aa? — modulo computes the remainder that answers it. The statement a mod n=0a \bmod n = 0 and the statement n∣an \mid a are two forms of the same fact.

Fractions arise when division is not exact. The expression ab\frac{a}{b} in lowest terms requires dividing both numerator and denominator by their GCD — a divisibility operation. Simplifying fractions is, at its core, factoring out common divisors.

Modular arithmetic extends divisibility into a full arithmetic system where numbers are classified by their remainders. The divisibility rules for 33, 99, and 1111 are consequences of how 1010 behaves under modular arithmetic — shortcuts derived from congruence properties of the base of our number system.

Summary: A Map of the Divisibility Subtree

The sections above have surveyed the full territory of divisibility: the definition itself, the terminology variants, the basic properties, the link to remainders and modulo, and the major sub-topics (rules, factors, primes, GCD, LCM). Each sub-topic has its own dedicated page where the details, methods, and worked examples live. The table below collects those pages with a one-line indication of what each covers — use it as a map for what to explore next.
DownloadPNG2×PDF
Layout
TopicWhat you'll find therePage
Divisibility rulesdigit-based shortcuts for testing divisibility by 2, 3, 4, 5, 6, 8, 9, 10, and 11 without performing the full division/divisibility/rules
Factors and multipleslisting all factors of a number using pair-search up to √n; counting formulas via prime factorization/divisibility/factors
Greatest common divisor (GCD)three methods — listing factors, prime factorization, and the Euclidean algorithm/divisibility/gcd
Least common multiple (LCM)the smallest shared multiple; the identity a · b = gcd(a, b) · lcm(a, b)/divisibility/lcm
Modulo (computational counterpart)the remainder operation that computes the answer to every divisibility question — and powers the Euclidean algorithm and divisibility rules/arithmetic/modulo
Summary: A Map of the Divisibility SubtreeLearn Math Class

Formula Summary

This summary gathers the formulas stated across the page in ten rows. Each row names a rule, with a line on what it says and a link to the section that explains it, then states the rule and checks it on small numbers.

It opens with the definition of one integer dividing another and the basic properties: a number with itself, with one and with zero, chains of divisors, sums, differences and multiples. Then come the division with remainder and the remainder test that computes divisibility, the count of factors read from a prime factorization, and the identity linking the greatest common divisor and the least common multiple, with the formula for the multiple that follows from it.
DownloadPNG2×PDF
RuleFormulaExample
DivisibilityA yes-or-no statement, not a division that produces a number, as what divisibility is explains.a∣ba \mid b means b=a⋅kb = a \cdot k for some integer kk3∣123 \mid 12, since 12=3⋅412 = 3 \cdot 4
Itself, one and zeroEvery nonzero integer divides itself and 00, and 11 divides everything; 00 divides only 00, as the basic properties note.a∣a,1∣a,a∣0a \mid a, \quad 1 \mid a, \quad a \mid 0a=a⋅1,  a=1⋅a,  0=a⋅0a = a \cdot 1, \; a = 1 \cdot a, \; 0 = a \cdot 0
TransitiveA divisor of a divisor divides the number too, one of the basic properties.if a∣ba \mid b and b∣cb \mid c, then a∣ca \mid c3∣123 \mid 12 and 12∣6012 \mid 60, so 3∣603 \mid 60
Sums and differencesA common divisor of two numbers also divides their sum and their difference, from the basic properties.if a∣ba \mid b and a∣ca \mid c, then a∣(b+c)a \mid (b + c) and a∣(b−c)a \mid (b - c)4∣204 \mid 20 and 4∣124 \mid 12, so 4∣324 \mid 32 and 4∣84 \mid 8
MultiplesA divisor of a number divides all of its multiples, the last of the basic properties.if a∣ba \mid b, then a∣(b⋅k)a \mid (b \cdot k) for any integer kk3∣123 \mid 12, so 3∣363 \mid 36 and 3∣603 \mid 60
Division with remainderThe quotient qq and the remainder rr for any integers aa and n>0n > 0; divisibility and remainders reads n∣an \mid a as the case r=0r = 0.a=n⋅q+r,0≤r<na = n \cdot q + r, \qquad 0 \leq r < n30=7⋅4+230 = 7 \cdot 4 + 2
Remainder testThe computational form of the same statement: divisibility poses the question and modulo computes the answer, as divisibility and remainders puts it.n∣an \mid a exactly when a mod n=0a \bmod n = 030 mod 7=230 \bmod 7 = 2, so 7∤307 \nmid 30
Number of factorsRead straight from the exponents of the prime factorization, with 11 added to each exponent.n=p1a1⋅p2a2⋯n = p_1^{a_1} \cdot p_2^{a_2} \cdots has (a1+1)(a2+1)⋯(a_1 + 1)(a_2 + 1) \cdots factors84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7: (2+1)(1+1)(1+1)=12(2 + 1)(1 + 1)(1 + 1) = 12
GCD and LCMThe identity that links the two quantities in GCD and LCM.a⋅b=gcd⁡(a,b)⋅lcm(a,b)a \cdot b = \gcd(a, b) \cdot \text{lcm}(a, b)4⋅6=2⋅12=244 \cdot 6 = 2 \cdot 12 = 24
LCM from the GCDThe same identity read the other way: the product is a common multiple, and dividing by the GCD brings it down to the least one (GCD and LCM).lcm(a,b)=a⋅bgcd⁡(a,b)\displaystyle \text{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}lcm(4,6)=242=12\displaystyle \text{lcm}(4, 6) = \frac{24}{2} = 12
Divisibility formulasLearn Math Class
Divisibility is a yes-or-no question, and these rules answer it without long division wherever they can. The remainder test settles any single case, while the properties carry a known divisor over to sums, multiples and longer chains.

Common Pitfalls

Six mistakes account for many of the wrong answers in divisibility work. Each is marked where it happens in the sections above; here each is worked through in full, with the wrong and the right working side by side.
DownloadPNG2×PDF
1Reading the bar as division
The vertical bar in a∣ba \mid b is read like a division sign or a fraction bar, so 3∣123 \mid 12 is taken to mean 33 divided by 1212. The two numbers swap roles, and true statements look false.
Wrong turn
Error here
3∣123 \mid 12 means 3÷12=0.253 \div 12 = 0.25, which is not a whole number, so 3∣123 \mid 12 is false.
Right path
3∣123 \mid 12 claims 12=3⋅k12 = 3 \cdot k for some integer kk. With k=4k = 4 the claim holds, so 3∣123 \mid 12 is true. The reversed statement 12∣312 \mid 3 would need 3=12⋅k3 = 12 \cdot k, and no integer kk works, so it is false.
Why it happensIn 312\frac{3}{12}, 3/123 / 12 and 3÷123 \div 12 the first number is the one being divided; in 3∣123 \mid 12 the first number does the dividing. The upright bar also looks like the slash of a fraction.
How to checkFor b≠0b \neq 0, a∣ba \mid b can only hold when ∣a∣≤∣b∣|a| \leq |b|. So 12∣312 \mid 3 is false at a glance, and 3∣123 \mid 12 is settled by 12÷3=412 \div 3 = 4.
2Testing 3 by the last digit
The last-digit tests for 22, 55 and 1010 are carried over to 33, and a number is judged by whether its last digit is a multiple of 33.
Wrong turn
Error here
1313 ends in 33, so 3∣133 \mid 13; 2727 ends in 77, so 3∤273 \nmid 27.
Right path
The digit sum decides. 1+3=41 + 3 = 4 is not a multiple of 33, so 3∤133 \nmid 13, and indeed 13=3⋅4+113 = 3 \cdot 4 + 1. 2+7=92 + 7 = 9 is a multiple of 33, so 3∣273 \mid 27, and indeed 27=3⋅927 = 3 \cdot 9.
Why it happensThe last-digit rules are learned first and are the simplest, so the same kind of rule is expected for every divisor. They work only for divisors of 1010: every number is a multiple of 1010 plus its last digit, and 33 does not divide 1010.
How to checkDivide once. 13÷313 \div 3 is 44 with remainder 11, while 27÷3=927 \div 3 = 9 exactly.
3Mixing up factors and multiples
The two words for the two sides of a∣ba \mid b are swapped, so a number larger than bb is listed among the factors of bb, or a smaller one among its multiples.
Wrong turn
Error here
24⋅2=4824 \cdot 2 = 48, so 4848 is listed as a factor of 2424.
Right path
48=24⋅248 = 24 \cdot 2 means 24∣4824 \mid 48, so 2424 is the factor and 4848 is the multiple. The factors of 2424 are 1,2,3,4,6,8,12,241, 2, 3, 4, 6, 8, 12, 24, and 4848 is not among them.
Why it happensBoth words describe the same relationship and come from the same multiplication fact; which side each word belongs to has to be remembered.
How to checkCompare sizes. A factor of a positive integer nn is at most nn, and a positive multiple of nn is at least nn.
4Taking odd numbers for primes
Because every even number other than 22 is composite, odd numbers are assumed to be prime, especially when they do not end in 55.
Wrong turn
Error here
99, 1515 and 9191 are odd, so they are prime.
Right path
9=3⋅39 = 3 \cdot 3, 15=3⋅515 = 3 \cdot 5 and 91=7⋅1391 = 7 \cdot 13 are all composite. The odd primes below 2020 are 3,5,7,11,13,17,193, 5, 7, 11, 13, 17, 19, and the odd numbers 99 and 1515 fall between them.
Why it happensBeing odd removes the factor 22, the test everyone does first, and the remaining tests are skipped.
How to checkTest the primes up to the square root. For 9191, 91≈9.5\sqrt{91} \approx 9.5, so the primes to test are 33, 55 and 77, and 91=7⋅1391 = 7 \cdot 13 shows it is composite.
5Multiplying the exponents
In the factor-count formula the added 11s are dropped, and the exponents of the prime factorization are multiplied as they stand.
Wrong turn
Error here
84=22⋅3⋅784 = 2^2 \cdot 3 \cdot 7 has exponents 2,1,12, 1, 1, so it has 2⋅1⋅1=22 \cdot 1 \cdot 1 = 2 factors.
Right path
An exponent aia_i allows ai+1a_i + 1 choices, from 00 to aia_i copies of its prime. So 8484 has (2+1)(1+1)(1+1)=12(2 + 1)(1 + 1)(1 + 1) = 12 factors: 1,2,3,4,6,7,12,14,21,28,42,841, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42, 84.
Why it happensThe exponent counts the copies of a prime that are present, and the choice of taking none of them, which gives the factors without that prime, is easy to overlook.
How to checkTry a prime power. The factors of 8=238 = 2^3 are 1,2,4,81, 2, 4, 8, four of them, which is 3+13 + 1 and not 33. For 360=23⋅32⋅5360 = 2^3 \cdot 3^2 \cdot 5, multiplying the exponents gives 66, while the true count is 2424.
6Multiplying to get the LCM
The product of two numbers is taken as their least common multiple.
Wrong turn
Error here
lcm(4,6)=4⋅6=24\text{lcm}(4, 6) = 4 \cdot 6 = 24.
Right path
The multiples of 44 are 4,8,12,…4, 8, 12, \ldots and the multiples of 66 are 6,12,…6, 12, \ldots, and the first one they share is 1212. The identity gives the same: lcm(4,6)=4⋅6gcd⁡(4,6)=242=12\text{lcm}(4, 6) = \frac{4 \cdot 6}{\gcd(4, 6)} = \frac{24}{2} = 12.
Why it happensThe product is always a common multiple, and for pairs with GCD 11, such as 44 and 99, it is the LCM, 3636. The shortcut works often enough to seem like a rule.
How to checkDivide the product by the GCD and test the result. Here 24÷2=1224 \div 2 = 12, and 12÷4=312 \div 4 = 3 and 12÷6=212 \div 6 = 2 are both whole, so 1212 is a common multiple smaller than 2424.
Common pitfalls with divisibility·/arithmetic/divisibilityLearn Math Class
Each slip mistakes one idea for a neighbouring one. a∣ba \mid b asks whether bb is a multiple of aa, not for a÷ba \div b; divisibility by 33 depends on the digit sum, not on the last digit; a factor goes into nn while a multiple comes out of it; odd is not the same as prime; each exponent aia_i gives ai+1a_i + 1 choices; and the LCM is the product only when the GCD is 11. A single division, a size comparison, or a small case such as 8=238 = 2^3 catches each slip.

Skills You Should Learn

Each skill opens its step-by-step method page.
Arithmetic methods
  • Find the GCD by prime factorizationFactor both numbers into primes and keep the shared primes with the smaller exponent: gcd⁡(72,120)=23⋅3=24\gcd(72, 120) = 2^3 \cdot 3 = 24.
  • Find the GCD with the Euclidean algorithmReplace the pair (a,b)(a, b) by (b,a mod b)(b, a \bmod b) until the remainder is 00; the last nonzero remainder is the GCD. No factoring needed.
  • Find the least common multipleFind the smallest number that two or more numbers divide: take every prime with its larger exponent, or use lcm⁡(a,b)=a⋅bgcd⁡(a,b)\operatorname{lcm}(a, b) = \frac{a \cdot b}{\gcd(a, b)}.

Divisibility FAQ

What does the notation a | b mean?

+
The vertical bar a | b is read 'a divides b' and means b = a × k for some integer k. It is a statement (true or false), not an operation, and order matters: 3 | 12 is true but 12 | 3 is false. The negation a ∤ b means 'a does not divide b.' This differs from a ÷ b, which computes a quotient.Read more →

How are GCD and LCM related?

+
For any two positive integers a and b: a × b = gcd(a, b) × lcm(a, b). For 4 and 6: 4 × 6 = 24, and gcd(4,6) × lcm(4,6) = 2 × 12 = 24. Knowing one allows you to compute the other from the product. See the GCD page for the ways to compute it.Read more →

Why is 1 not considered prime?

+
A prime must have exactly two distinct factors: 1 and itself. The number 1 has only one factor (itself). Excluding 1 preserves the uniqueness of prime factorization — otherwise 12 could be written as 2² × 3 or 1 × 2² × 3 or 1² × 2² × 3, and so on without end.Read more →

Does zero divide zero?

+
Yes, under the definition used here. The statement 0∣00 \mid 0 asks for an integer kk with 0=0⋅k0 = 0 \cdot k, and every kk works. That does not give 0÷00 \div 0 a value: divisibility only claims that some kk exists, while division needs a single answer, and here no single one exists. Zero divides no other number, since 0⋅k0 \cdot k is always 00. Some textbooks require a nonzero divisor and leave 0∣00 \mid 0 out.Read more →

Is prime factorization unique in every number system?

+
No. Among the numbers 1,5,9,13,17,…1, 5, 9, 13, 17, \ldots, each one more than a multiple of 44, the product of any two stays in the list, yet 441=9⋅49=21⋅21441 = 9 \cdot 49 = 21 \cdot 21, and none of 99, 2121, 4949 splits further inside it. What breaks is the property the integer proof rests on: 2121 divides 9⋅499 \cdot 49 but divides neither 99 nor 4949. Among the integers, a prime that divides a product always divides one of the factors.Read more →