Divisibility Created 2026-09-24 Updated 2026-10-13
For integers , divides when multiplication by some integer takes to :
Then is a divisor of , and is an integer multiple of . The notation means that no such integer exists. For , this is equivalent to saying that the quotient is an integer, or that Euclidean division by leaves remainder zero.
For example, because , whereas because . Signs do not change divisibility: because , and because . In general, changing the sign of either input preserves the relation.
The definition here permits zero as either input. Every integer divides zero, since . In particular, ; however, whenever , since is always zero. This is a statement about multiplication, and assigns no meaning to division by zero: remains undefined.
Two useful properties come directly from the defining multiplication. Divisibility is a reflexive relation, since , and a transitive relation: if and , then . Moreover, a shared divisor divides every integer linear combination:
Indeed, writing and gives . For example, and imply . This small observation explains why the Euclidean algorithm preserves common divisors, and why Bézout's identity can certify a greatest common divisor.
On the positive integers, divisibility is a partial order: if and , then . The restriction matters, since and although . The prime factorization viewpoint makes this order concrete: exactly when every prime valuation of is at most the corresponding prime valuation of . Thus one relation connects equal grouping, prime factorization, and modular arithmetic.
Book VII, definitions 3 and 5 of Euclid's Elements describe the corresponding positive-number relation through one number measuring another and through integer multiples. The sign and zero conventions above belong to the present integer formulation, rather than to those ancient definitions. [ref]
Euclid's lemma 2026-10-13
If a prime number divides a product of integers , then divides or (possibly both):
For example, and . The hypothesis that is a prime number matters: , although six divides neither factor. When does not divide , the greatest common divisor of and is one; multiply Bézout's identity by to see that . Repeated application makes this the uniqueness step in the fundamental theorem of arithmetic. [ref].
For a completely computed example, because , while shows that seven does not divide twenty. Bézout's identity becomes, after multiplication by ,
The two terms on the right are divisible by seven, which explicitly recovers the forced divisibility of the second factor. Both alternatives can hold: , and seven divides both and .
In fact the property characterizes prime numbers among the integers greater than one. If is a composite number, choose with ; then , but divides neither nor . For several factors, repeated application of Euclid's lemma says that a prime number dividing their product divides at least one factor. In a product of prime numbers, that factor must equal it, because a prime number has no other prime factor. This is what prevents a different collection of prime factors from representing the same positive integer in the fundamental theorem of arithmetic.
Book VII, Proposition 30 of Euclid's Elements states the result in terms of a prime number measuring a product; its proof uses coprimality and ratios. The calculation using Bézout's identity above is a modern way to explain the same divisibility statement. [ref]
Euclid's theorem Created 2026-10-05 Updated 2026-10-14
There are infinitely many prime numbers. Indeed, for any finite list of prime numbers , the integer has a prime factor, by the fundamental theorem of arithmetic. None of the listed prime numbers divides , since each divides and a common divisor would divide . Thus no finite list contains all prime numbers. The constructed need not itself be a prime number.
For example, the first six prime numbers give
Both prime factors lie outside the original list, although is a composite number. The construction defeats a proposed complete list; it is not a formula guaranteed to produce a prime number. Book IX, Proposition 20 of Euclid's Elements explicitly considers both possibilities, prime and composite. [ref].
Finite geometric series Created 2026-09-24 Updated 2026-10-14
A finite geometric series is a sum of consecutive terms of a geometric progression. With first term and terms, including for the empty sum,
Unlike an infinite geometric series, this identity does not need . For example, . The number of terms is five; the largest exponent is four.
The cancellation behind the formula is especially useful to remember: multiplying by the common ratio shifts all terms one place. In , every interior term cancels, leaving . Division by gives the identity when ; at the sum is directly . The same argument works for complex numbers.
For integers and , the shifted version is
There are terms. All powers must be defined; if a negative exponent is present, must be nonzero. At this sum is simply . The finite trigonometric sum uses this identity with a complex exponential as the common ratio.
Finite sums of positive integers in a geometric progression already appear in Euclid's Elements, Book IX, Proposition 35. The argument there compares differences of proportional numbers; Joyce's guide rewrites its conclusion as the modern finite-sum formula. This historical result concerns finite sums, without asserting an infinite limit. [ref]
Fundamental theorem of arithmetic Created 2026-09-24 Updated 2026-10-14
Every integer is a product of prime numbers, uniquely up to reordering the factors. More precisely, there are unique distinct prime numbers and unique positive integer exponents such that
In the header's displayed form, is the prime valuation, the exponent of in this prime factorization; it is zero when does not divide . Reordering or regrouping the prime factors does not give a different prime factorization.
For , repeated division gives , , , then , , and . Thus
Its nonzero prime valuations are , and . Recording only the distinct prime factors would lose the difference between and .
This turns divisibility into coordinatewise comparison of nonnegative exponents. A positive divisor of chooses an exponent from for , from for , and from for , giving positive divisors. The greatest common divisor takes the smaller exponent at each prime number; the least common multiple takes the larger. The theorem is a structural description, not an assertion that finding the factors of every large integer is computationally easy.
In general, for positive integers , the exact divisibility criterion is
For example, divides , with quotient , whereas does not: it requires four factors of two, but supplies only three. Both use only prime factors of , so membership in that list alone does not establish divisibility. Every positive divisor of is uniquely with , , . Sorted, all 24 positive divisors are
Thus the divisor function gives . These include divisors that are composite numbers, as well as the prime factors and one.
For another positive integer , the prime valuations give exact formulas for the greatest common divisor and least common multiple:
With and , their prime valuations at are and . The smaller exponents give , and the larger give , hence
Indeed, , , and . The same rules also explain : the smaller and larger exponents sum to the two original exponents. Here .
Figure 1. . The upper table compares exponents at the prime numbers for and , then takes their columnwise minimum and maximum. The lower tables enumerate for and ; each cell gives one positive divisor. Details.
The useful change of viewpoint is that multiplication becomes addition of prime valuations, , and divisibility becomes comparison. Many different-looking calculations therefore share one representation. The prime valuations are coordinates for multiplication, rather than digits in positional notation: they do not turn ordinary addition of integers into coordinatewise addition.
Different intermediate splits lead to the same prime ingredients. Starting with gives and ; starting with gives and . Continuing to split the composite numbers produces the same multiset of prime factors: three twos, two threes, and one five. The factorization tree records choices in the calculation, while the prime factorization records the invariant result.
Figure 2.
Two factorization trees for give the same prime factorization
. Details.
The proof outline explains the uniqueness. Existence follows by splitting a composite number into smaller factors until only prime numbers remain. For uniqueness, Euclid's lemma says that a prime factor of one product must divide one factor of any other prime product equal to it. That factor must be the same prime number; cancel it and repeat. The crucial divisibility step appears in Book VII, Proposition 30 of Euclid's Elements. [ref]
The ancient text supplies specific precursors to the modern statement: Book VII, Proposition 31 establishes that every composite number has a prime factor, and Book IX, Proposition 14 excludes any new prime factor from the least common multiple of given prime numbers. These are the propositions being cited, rather than the complete modern exponent formulation of the fundamental theorem of arithmetic. [ref] [ref]
Excluding one from the prime numbers keeps uniqueness meaningful: otherwise would give different collections of supposed prime factors. For , the natural convention is the empty product, equal to one, with no prime factors and all prime valuations zero.
Least common multiple Created 2026-09-24 Updated 2026-10-14
For positive integers , their least common multiple is the smallest positive integer that is an integer multiple of both. Write it as . A positive common integer multiple always exists, since is one, but it can be larger than necessary.
For example, the positive integer multiples of begin , while those of begin . Their first positive coincidence is , so . Both also divide zero, but the word positive excludes zero from this minimum.
Suppose two events happen every twelve and eighteen days, and both happen at day . Their next meeting is at day , after three twelve-day intervals and two eighteen-day intervals. Through day , their common event times are .
Figure 1.
Events every 12 and 18 days, starting together, meet again every 36 days
. Each row marks the nonnegative integer multiples of its interval from zero through 72. The highlighted columns are shared; 36 is the first positive one and hence the least common multiple. Details.
The prime factorization explains why this coincidence occurs. For the integers and ,
A common integer multiple must contain at least the prime valuations required by each input. Taking the larger prime valuation at each prime number meets both requirements with no extra factors. The greatest common divisor uses the smaller prime valuations instead. This is the same coordinate comparison developed under prime factorization, applied in opposite directions.
Figure 2.
For 12 and 18, smaller prime valuations give greatest common divisor 6 and larger ones give least common multiple 36
. Bars show the exponents of the prime numbers two and three in , , and . The table makes the minimum and maximum in each column explicit. Details.
For any positive integers , the prime valuations give
The proof outline is one observation at each prime number: . Hence the two sides have identical prime factorizations. Numerically, . This also gives a calculation using the Euclidean algorithm for the greatest common divisor, without first finding the prime factors of both inputs.
Every positive common integer multiple is an integer multiple of the least common multiple, because its prime valuations must be at least the larger input prime valuations. Including negatives and zero, the common integer multiples of and are exactly for integers . For more than two positive integers, the same definition and rule of taking the largest prime valuations apply; one may also combine inputs successively. For example, .
For nonzero signed integers, take absolute values: . We extend the definition to zero by the convention , since zero is then the only common integer multiple; this is an extension, not a positive minimum. In particular must be handled separately from the displayed quotient, which would involve division by zero.
The least common multiple is useful for combining fractions with the smallest positive shared denominator. For example,
Its scheduling interpretation requires care about starting times. If the events start at integer days and , a common time must satisfy the integer congruences and . The Chinese remainder theorem for noncoprime moduli says a solution exists exactly when . If it exists, solutions form one congruence class modulo , but the first meeting need not be day . With starts , the first meeting is day and subsequent meetings are ; with , they never meet. The beauty of the least common multiple is the exact shared spacing, while the integer congruences determine whether and where the spacing begins.
Book VII, Proposition 34 of Euclid's Elements constructs the least common multiple of two numbers, and Proposition 36 extends the construction to three by first combining two of them. In modern notation this is . These are specific ancient treatments of the construction, rather than a claim about its first discovery. [ref] [ref]
Prime number Created 2026-09-24 Updated 2026-10-13
A prime number is a positive integer whose only positive divisors are and . The first ten prime numbers are . In contrast, is a composite number because it has a positive divisor strictly between one and itself. The integer one is neither a prime number nor a composite number: the lower bound is part of the definition. Equivalently, the divisor function satisfies for a prime number, whereas and for every composite number .
Prime numbers are the building blocks of positive integers under multiplication. The fundamental theorem of arithmetic says that every integer greater than one is a product of prime numbers, with a unique collection of factors when their order is ignored. For example, and . Their common factors reveal the greatest common divisor , and the combined maximum powers reveal the least common multiple . A complicated divisibility question becomes a comparison of prime exponents.
There is also a useful finite test. If a composite number equals with , then . Therefore some prime factor is at most , and trial division only needs to check prime numbers up to that square root. For , checking suffices; none divides , so it is a prime number. For , the same test finds , giving . To find many prime numbers together, the sieve of Eratosthenes reuses the work by marking multiples.
The division with remainder calculations for make the test explicit:
Since , these are all the prime numbers at most its square root, and every remainder is nonzero. Thus the calculation certifies a prime number, without testing the integers individually. In contrast, gives a prime factor and proves that is a composite number.
The definition has a long history. Book VII of Euclid's Elements distinguishes prime numbers from composite numbers through their possible measures; Book IX, Proposition 20 establishes that no finite list exhausts the prime numbers. The modern argument under Euclid's theorem needs only divisibility, so it proves an infinite conclusion without estimating how frequently prime numbers occur. [ref] [ref].
Pythagorean theorem Created 2026-09-28 Updated 2026-10-14
For a right triangle in Euclidean geometry with perpendicular side lengths and hypotenuse , the Pythagorean theorem states
Geometrically, the area of the square on the hypotenuse equals the sum of the areas of the squares on the other two sides. Euclid's Elements, Book I, Proposition 47 states this area equality; Proposition 48 states its converse: a triangle satisfying the equality has a right angle opposite side .[ref][ref]
For and , we compute . The triangle has area , and its side lengths form a Pythagorean triple. Conversely, a triangle measured to have sides must have a right angle between the sides and . This makes the equality both a calculation tool and a test for perpendicularity.
The three squares in the next figure have areas , and in squared length units. These are different from the central right triangle's area . The Pythagorean theorem adds the areas of the attached squares, not their side lengths and not the area of the triangle. The square on the hypotenuse is tilted, but a rotation preserves its area. This makes the formula visible without suggesting that the hypotenuse has to align with an axis.
Figure 1.
Squares on a 3-4-5 right triangle have areas ; the triangle itself has area
. Details.
Historically, Euclid's Elements records an organized proof of the Pythagorean theorem as an equality of areas, rather than the modern equation between numbers representing lengths. Its placement in Book I makes it available before the treatment of similar triangles in Book VI. This is evidence of how the result was established within that text; the name Pythagorean theorem alone does not establish who first discovered or proved it. The precise historical anchor here is the surviving proposition, rather than an unsupported story of a single inventor.[ref]
The dissection below makes the general identity tangible. Both outer squares have side and contain the same four congruent right triangles. In the first arrangement, their hypotenuses bound a square of side : adjacent acute angles together make a right angle. In the second, the uncovered regions are squares of sides and . Subtracting the same total triangle area from equal outer areas gives
For the pictured dimensions, the shared uncovered area is .
Figure 2.
Rearranging four congruent 3-4-5 right triangles proves that the uncovered square areas satisfy
. Details.
The same mechanism survives in inner product spaces: for orthogonal vectors , expanding the inner product gives . This is why orthogonal projection separates a squared distance into independent contributions. The familiar right triangle is the simplest picture of a much more reusable principle.
Sieve of Eratosthenes 2026-10-14
The sieve of Eratosthenes finds all prime numbers at most an integer . Start with the integers marked as candidates. For each surviving candidate in increasing order, mark the multiples up to as composite numbers. Stop processing candidates once : the surviving candidates are exactly the prime numbers. Starting at saves work because any smaller proper multiple of already has a smaller prime factor. [ref].
For a complete run with , the only prime numbers at most are , since . Exclude one before starting; it is not a prime number. The four marking passes are:
  • : mark , removing 29 candidates.
  • : mark . The nine newly removed candidates are ; the even integers were already marked.
  • : mark . Only are newly removed.
  • : mark . Only is newly removed.
There are surviving prime numbers:
The next surviving candidate is , and , so no further marking pass is necessary. A prime number used for marking remains a candidate: starting at never marks itself.
Figure 1.
Four passes of the sieve of Eratosthenes through 60 leave seventeen prime numbers
. Blue cells are newly marked composite numbers; gray cells were removed earlier. White cells are candidates in the first three panels, and green cells are the final prime numbers. The outlined cell identifies the prime number used for that pass. One is excluded throughout. Details.
The saving from starting at is justified by the smaller multiplier: if with , then has a prime factor , so has already marked . For , the earlier multiples have already been marked using or . The first new possibility is .
For , only the prime numbers need marking passes. They remove all the composite numbers, leaving 25 prime numbers. The diagram colors each composite number by its smallest prime factor, so it shows which marking pass removes it first. The excluded integer one is shown separately.
Figure 2.
The sieve of Eratosthenes leaves 25 prime numbers among the integers from one to 100
. Each colored composite number is assigned to its smallest prime factor, one of . The green survivors are prime numbers; one is neither a prime number nor a composite number. Details.
Why does the algorithm work? A surviving candidate cannot be a composite number, since its smaller prime factor would already have removed it. Conversely, marking proper multiples never removes a prime number. Every composite number at most has a prime factor at most , so no later pass is needed. The sieve of Eratosthenes is useful when an entire bounded list is wanted; primality testing of one large integer is a different computational task.
The historical name is supported by a surviving primary account: Nicomachus, in Book I, chapter 13 of Introduction to Arithmetic, names Eratosthenes and describes separating prime numbers from composite numbers by marking multiples among the odd integers beginning with three. That passage documents the sieve tradition; the bounded algorithm above and its starting rule are the formulation explained here, rather than instructions quoted from Euclid's Elements. [ref]
Similar triangle 2026-10-14
Two triangles are similar if a Euclidean similarity maps one onto the other. Their corresponding angles agree, and corresponding side lengths have a common positive ratio.
Specify the correspondence first: matches , matches and matches . For similar triangles, the common scale factor satisfies
The ratios compare matching sides in the same order. A Euclidean similarity can also move, turn or reflect the triangle; its orientation on the page is irrelevant. In the Euclidean plane, matching just two interior angles is enough: their sums force the third to match, and equal corresponding angles force the side ratios to agree. This is the angle-angle (AA) criterion for similar triangles. Matching just one angle is insufficient.
Scale the right triangle with vertices , and by . Its new vertices are , and , and its side lengths are . The matching side ratios are . Both triangles have a right angle and the same two other interior angles, approximately and . However, their areas are and : doubling lengths multiplies area by four.
Figure 1.
Similar 3-4-5 and 6-8-10 right triangles: side lengths multiply by , while area multiplies by
. Details.
Generally, a Euclidean similarity multiplies both a base and its perpendicular height by , so the area becomes . This explains why an enlarged drawing needs four times as much surface when each length doubles. It also enables indirect measurement: under assumptions of level ground, vertical objects and parallel light rays, an object of height casting a shadow of length provides a right triangle. Another object's shadow of length gives a similar triangle and height . The shared angles justify the inference; visual resemblance alone does not.
Euclid's Elements VI, Definition 1 describes similarity using corresponding angles and proportional sides. VI.4 establishes the implication from matching angles to matching side ratios, while VI.19 states the squared relation between side ratios and areas. These are documented ancient formulations of the principles used above, without establishing a first discoverer.[ref][ref][ref]
Sum-of-divisors function Created 2026-10-03 Updated 2026-10-14
The sum-of-divisors function adds all positive integer divisors of a positive integer, including the number itself:
It is the divisor sum of the identity arithmetic function , so under Dirichlet convolution. Both factors are multiplicative functions, hence so is the sum-of-divisors function. The notation distinguishes it from other weighted divisor sums. [ref]
For a prime number and a nonnegative exponent , the positive integer divisors of the prime power are precisely . Their finite geometric series gives
For example, . For a prime factorization with distinct prime numbers and positive exponents , multiplicativity gives
For , this is an empty product, equal to . [ref]
The distributive property makes the formula especially beautiful: choosing one term from each factor produces each positive integer divisor exactly once, by the fundamental theorem of arithmetic. For , the choices form a three-by-two grid with entries , where and . Adding its rows gives
The divisor function counts six cells; the sum-of-divisors function adds their six values. Once the prime factorization is known, the product formula avoids testing every candidate integer divisor. Shared prime factors require care: , so the sum-of-divisors function is not a completely multiplicative function.
Figure 1.
The sum-of-divisors function for : each grid entry is a positive integer divisor, and the weighted total is
. Details.
Subtracting the number itself gives the proper-divisor sum . Comparing with distinguishes perfect numbers, deficient numbers, and abundant numbers. For , ; for , . Both are perfect numbers. The calculation makes a deficient number, while makes an abundant number. These comparisons turn the sizes of integer divisors into a classification of positive integers. [ref]
Figure 2.
The proper-divisor sum for : perfect numbers lie on , deficient numbers below it, and abundant numbers above it
. Details.
This connection is ancient: Euclid's Elements, Book IX, Proposition 36, constructs a perfect number by multiplying the last term of by their sum, when that sum is a prime number. In modern notation, put and , with and a prime number. The sum-of-divisors function proves the construction immediately:
Consequently the proper-divisor sum is . Taking produces the perfect numbers . [ref]
Triangle Created 2026-09-24 Updated 2026-10-14
A triangle is the convex hull of three noncollinear points: the three vertices must not lie on one line. Its boundary consists of the three joining line segments; depending on context, "triangle" can mean this boundary or the filled region it encloses. Here a triangle's area refers to the filled region. The noncollinearity assumption excludes a collapsed shape with zero area, for which ordinary interior angles are not defined.
For example, the positions , and form a right triangle with a right angle at the origin. Taking the side of length as its base gives perpendicular height , so its area is . The height is measured at a right angle to the chosen base; it is not generally the length of another side. In this example it happens to be a side because the triangle is a right triangle.
By contrast, side lengths define a valid triangle: each side is shorter than the sum of the other two, as required by the strict triangle inequality. But , so this is not a right triangle and the Pythagorean theorem cannot calculate its longest side from the other two. The law of cosines instead gives the opposite interior angle through
This example separates the definition of a triangle from the additional assumption of a right angle.
Every triangle in the Euclidean plane has interior angles summing to radians, a result proved in Euclid's Elements I.32.[ref] It lets two measured angles determine the third, and underlies the angle-angle criterion for similar triangles. The qualification "Euclidean plane" matters: the earlier spherical triangle demonstrates a different sum.