Coprime integers Created 2026-09-24 Updated 2026-11-05
Two integers are coprime when their greatest common divisor is one:For positive integers, this says that the only positive common divisor is one. For signed integers, use , with absolute values; changing either sign leaves coprimality unchanged. With the convention , zero is coprime precisely to , because . Both are coprime to every integer. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781, Section 1.2: greatest common divisors and coprimality
The word concerns shared prime factors, not whether either input is a prime number. For instance and are coprime composite numbers, even though neither is a square-free integer. Conversely, and are square-free integers but are not coprime. Consecutive integers are always coprime: any common divisor of divides their difference one. Thus provide another pair of coprime composite numbers.
For positive integers, let be the prime support of an integer. The equivalent test isThe set intersection of the two prime supports of an integer must be the empty set. Indeed, any positive common divisor greater than one has a prime factor, and any shared prime factor is a common divisor greater than one. Hence coprimality depends on which prime factors occur, rather than on their prime valuations; replacing either input by its radical of an integer preserves coprimality.
For a list of at least two integers, distinguish pairwise coprimality, requiring every pair to be coprime, from joint coprimality, requiring only the greatest common divisor of the entire list to be one. For example,No prime factor belongs to all three prime supports of an integer, yet each pair shares one. By contrast, have pairwise coprimality. The distinction is presented by Poritz under the names pairwise and mutually relatively prime. [ref]
https://math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Yet_Another_Introductory_Number_Theory_Textbook_-_Cryptology_Emphasis_(Poritz)/01:_Well-Ordering_and_Division/1.05:_The_Greatest_Common_Divisor. Jonathan A. Poritz, Yet Another Introductory Number Theory Textbook, Section 1.5
One use is simplifying fractions. For a fraction with integer entries and , divide its numerator and denominator by to obtain a reduced fraction with coprime entries. For example, since , and uses the same . A further common divisor would make too small, so the reduction is complete. In particular, the reduced fraction for zero is .
Another use is reversible modular arithmetic: for an integer modulus , an integer has a modular inverse precisely when are coprime. The proof outline uses Bézout's identity: makes a modular inverse, and any inverse relation forces every common divisor to divide one. For example, gives , whereas has no modular inverse modulo . Thus coprimality is the exact condition allowing division by a residue in modular arithmetic. [ref]
https://ocw.mit.edu/courses/18-200-principles-of-discrete-applied-mathematics-spring-2024/mit18_200_s24_lec15.pdf. Ankur Moitra, MIT 18.200, Lecture 15, Lemmas 1–2 and modular inverses
Divisibility Created 2026-09-24 Updated 2026-10-18
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]
https://geometor.github.io/euclid/heath/VII/index.html. Euclid, Elements VII, definitions 3 and 5, T. L. Heath translation
Elementary lower bound for the Chebyshev theta function Created 2026-09-24 Updated 2026-11-05
The Chebyshev theta function satisfies for every sufficiently large real number . This follows without the Prime number theorem.
Write for the second Chebyshev function. The largest binomial coefficient in row is the central one, and that row sums to , soBy the Legendre formula, the prime valuation of this central binomial coefficient is a sum of terms , each zero or one. Hence the coefficient divides , whose natural logarithm is . Taking logarithms gives , the central-coefficient argument of Chebyshev estimate from central binomial coefficients.
For real , take . Monotonicity gives . Higher prime powers contribute at most to , as proved for the second Chebyshev function. ThereforeAfter division by , the right side tends to , proving the stated lower bound.
Fundamental theorem of arithmetic Created 2026-09-24 Updated 2026-10-20
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 thatIn 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 . ThusIts 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 isFor 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 areThus 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 , henceIndeed, , , and . The same rules also explain : the smaller and larger exponents sum to the two original exponents. Here .
Prime valuations compute the greatest common divisor, least common multiple and all 24 positive divisors of 360
. 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.
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]
https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII30.html. Euclid, Elements VII.30: a prime divisor of a product
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]
https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII31.html. Euclid, Elements VII.31: every composite number has a prime divisor
[ref]https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX14.html. Euclid, Elements IX.14: prime divisors of a least common multiple of primes
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.
Greatest common divisor Created 2026-09-24 Updated 2026-10-20
For integers not both zero, their greatest common divisor is the largest positive integer dividing both. It is unchanged by replacing either input by its negative. The convention is useful, but this exceptional value is not a largest positive common divisor. For positive inputs, the Euclidean algorithm computes the answer, and Bézout's identity expresses it as an integer linear combination of the inputs.
For and , a common divisor can contain at most one copy of the prime number two and one of the prime number three. Taking the smaller prime valuation at each prime number therefore givesThe check is also a Bézout's identity: every common divisor divides this difference, and six itself divides both inputs. More generally, every common divisor divides the greatest common divisor, a stronger statement than merely being no larger than it. The companion least common multiple takes the larger prime valuations, as the diagram there illustrates. For an application, divide the numerator and denominator of the fraction by six to obtain ; these remaining integers are coprime.
Least common multiple Created 2026-09-24 Updated 2026-10-20
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 .
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.
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 giveThe 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]
https://geometor.github.io/euclid/heath/VII/34/index.html. Euclid, Elements VII.34, T. L. Heath translation: two numbers
[ref]https://geometor.github.io/euclid/heath/VII/36/index.html. Euclid, Elements VII.36, T. L. Heath translation: three numbers
Lifting a primitive root to odd prime powers Created 2026-09-24 Updated 2026-11-05
Let be an odd prime and a primitive root modulo . Then is a primitive root modulo every prime power if and only if it is a primitive root modulo . In that caseThe condition at says with . The odd-prime case of the lifting-the-exponent lemma, obtained here by repeated use of the binomial theorem and then raising to an exponent not divisible by , givesHere is the prime valuation. To see the induction step, the first term in has prime valuation , while every later term has strictly greater prime valuation when is odd and .
Lifting-the-exponent lemma 2026-11-05
For an odd prime , integers with and , and a positive integer with , the lifting-the-exponent lemma givesHere is the prime valuation. The divisibility and unit hypotheses cannot be dropped.
Past exam of the mathematics course of the University of Cambridge 2016 iii Paper 124 1 a Solution Created 2026-10-03 Updated 2026-10-14
An additive arithmetic function satisfies for coprime integers ; a completely additive arithmetic function satisfies this for all positive . In either case . The fundamental theorem of arithmetic gives , where means that the prime valuation of at is exactly .
Under the discrete uniform distribution on , the expectation of the indicator function of isThe formula remains valid when . Applying linearity of expectation to the finite prime power decomposition proves the required mean formula:
For the last assertion, write the excess prime-factor multiplicity directly as a sum of nonnegative indicator functions:Here is the prime omega function and is the total number of prime factors. The expectation is bounded independently of , sinceThus Markov inequality gives vanishing probability on every diverging scale:
Prime valuation Created 2026-09-24 Updated 2026-10-13
For a prime number and a positive integer , the prime valuation is the exponent of in the prime factorization of , equivalentlyThus because divides but does not; , and . In particular . Multiplication adds prime valuations, , and the fundamental theorem of arithmetic makes comparison of prime valuations an exact test for divisibility between positive integers. This definition extends to a nonzero integer by taking its absolute value; for zero one commonly sets .
Radical of an integer Created 2026-10-06 Updated 2026-10-20
The radical of an integer is the product of its distinct prime factors, each included exactly once. If the prime factorization is with distinct prime numbers and positive integer exponents , thenThus the radical of an integer remembers which prime factors occur and forgets their prime valuations. At , the empty product gives . The domain of a function here is the positive integers; zero is excluded. [ref]
https://pub.math.leidenuniv.nl/~evertsejh/dio12-ex4.pdf. Jan-Hendrik Evertse, Diophantine approximation, Homework IV, Exercise 20: definition of the integer radical
For example, has distinct prime factors , so . Similarly,using the prime factorizations , and . The prime omega function counts the retained prime factors, while the total number of prime factors counts their occurrences before repetitions are removed.
The radical of an integer is its largest squarefree divisor. Indeed, a squarefree divisor chooses at most one copy of each prime factor, so it divides ; the radical of an integer itself is a squarefree divisor. Consequently,The last statement follows because every nonzero prime valuation is then one. It includes , a squarefree integer. Applying the radical of an integer twice also changes nothing: .
The radical of an integer for : squarefree integers lie on the diagonal, and horizontal families share their prime support of an integer
. Details. For any positive integers , the exact product rule isTo prove it, a prime factor dividing just one input occurs once in the numerator and not in the denominator. A prime factor dividing both occurs twice in the numerator and once in the denominator, since it divides their greatest common divisor. Each prime factor of therefore remains exactly once. For coprime integers, the denominator is , proving the radical of an integer is a multiplicative function. It is not a completely multiplicative function: .
For a worked example with shared prime factors, take and . Their greatest common divisor is , and , soThis explains why prime support of an integer is useful: questions about the presence of prime factors can discard their multiplicities. For example, the squarefree divisors of are exactly the integer divisors of , namely . Also if and only if , because coprimality depends only on shared prime factors.
A further characterization uses mutual divisibility of powers: for positive integers ,If their prime supports of an integer agree, sufficiently large make all the required prime valuations large enough. Conversely, these two divisibility relations force each prime factor of either input to divide the other. For and , one can take and : and .
Square-free integer Created 2026-09-24 Updated 2026-11-05
A positive integer is square-free when no square number greater than one is a divisor of . It suffices to exclude squares of prime numbers; equivalently, every prime valuation is zero or one:Thus the prime factorization of a square-free integer is a product of distinct prime factors, with no repetitions. One is included: its prime factorization is an empty product and all its prime valuations are zero. These equivalent tests are stated in Grinberg's notes. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781, Floor and arithmetic functions, Definition 2.1.2 and footnote 6
For signed integers, extend the definition by requiring to be a square-free integer, where denotes absolute value. Hence and both qualify. Zero does not: every prime number has its square as a divisor of zero. The Möbius function and radical of an integer below use their existing positive integer domains, so apply them to when handling a negative integer.
For example, is a square-free integer, whereas is not, because and . Being a composite number causes no problem: are all square-free integers. A square-free integer need not be coprime to another integer: and are both square-free integers but have greatest common divisor two. In fact the only signed integers coprime to every integer are , since .
Exact square-free integer classification of the integers from one to sixty
. Green cells are square-free integers; each red cell displays a prime number square that divides its label, choosing the smallest such prime number. Only need testing in this range. There are green cells. This original finite arithmetic diagram is an exact enumeration, not a measurement or an assertion about a limiting frequency. Details.For positive integers , the useful product criterion isThe proof outline is just addition of prime valuations: can stay at most one only if neither input repeats a prime factor and no prime factor occurs in both. Thus is a square-free integer, but is not. An equivalent characterization is that every factorization into positive integers has coprime factors. If , the factorization supplies two factors sharing ; conversely, a shared prime factor forces its square to divide . For , the unordered factor pairs all have greatest common divisor one; for , the pair fails.
Two existing arithmetic functions turn the definition into practical tests:The radical of an integer keeps one copy of each prime factor, so it changes precisely the integers with a repeated prime factor. Its definition is given in Evertse's exercise sheet. [ref]
https://pub.math.leidenuniv.nl/~evertsejh/dio12-ex4.pdf. Jan-Hendrik Evertse, Diophantine approximation, Homework IV, Exercise 20
The Möbius function assigns to a square-free integer with distinct prime factors and zero otherwise; squaring forgets the sign. Consequently counts exactly the green cells. This connects a restriction on repeated prime factors with weighted counting and inclusion-exclusion. [ref]Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781, Definition 2.1.2: the Möbius function
Sum of two squares theorem Created 2026-09-24 Updated 2026-11-05
A positive integer is a sum of two squares of integers exactly when every prime factor congruent to three modulo four has an even prime exponent in its prime factorization. The zero-square convention permits ; zero itself separately has .
For necessity, let divide . If , then , contradicting Euler's criterion for minus one at such a prime. Hence , and then as well. Divide both coordinates by and repeat. Each removal subtracts two from the prime valuation of , forcing it to be even.
For sufficiency, two is . A prime number congruent to one modulo four has a square root of minus one by Euler's criterion, and the congruence lattice proof of the prime sum of two squares turns that root into a representation of the prime. Each even power of a prime congruent to three modulo four is already a perfect square, hence a sum of two squares with a zero term. Finally, the Brahmagupta-Fibonacci identity combines the representations across all prime powers in .
Total number of prime factors Created 2026-10-06 Updated 2026-11-05
The total number of prime factors counts every occurrence of a prime factor in the prime factorization of a positive integer . Equivalently, it adds the prime valuations:One may also write over all prime numbers, since only finitely many prime valuations are nonzero. The empty sum gives . By contrast, the prime omega function has and counts distinct prime factors. [ref]
Floor and arithmetic functions by Darij Grinberg. Darij Grinberg, MIT 18.781, Floor and arithmetic functions, Definition 2.1.2: the two prime-factor counts
Expanding into shows , whereas and . The same calculation for the comparison examples givesThe total number of prime factors agrees for and , although their prime supports of an integer differ. Meanwhile and have the same radical of an integer and prime omega function, but different values of the total number of prime factors. These examples show exactly which information each arithmetic function forgets.
One box per prime factor occurrence: the total number of prime factors counts boxes, the prime omega function counts groups, and the radical of an integer multiplies one prime number from each group
. Details. The total number of prime factors is a completely additive arithmetic function:The proof is that multiplication adds each prime valuation, , and summing preserves that equality. No coprimality condition is needed. For example, and both have total number of prime factors three; their product has six. By comparison, the prime omega function is only an additive arithmetic function: here .
There is a useful way to see the total number of prime factors as a count of elementary building blocks: any expression of as a product of prime numbers has exactly factors, by the fundamental theorem of arithmetic. Equivalently, every factorization tree for has leaves. Repeated prime factors increase this count without introducing new kinds of prime number. The difference is the existing excess prime-factor multiplicity:Every summand is nonnegative, so if and only if is a squarefree integer, including . In particular, a prime power with has , and .
Historically, Hardy and Ramanujan's 1917 paper explicitly separated the prime omega function from the total number of prime factors, writing them as and , respectively. Their example has counts three and six. That distinction let them compare two measures of how an integer is built from prime factors. [ref]
https://ramanujan.sirinudi.org/Volumes/published/ram35.html. G. H. Hardy and S. Ramanujan, The normal number of prime factors of a number n, Quarterly Journal of Mathematics 48 (1917), 76–92, Section 1.2, transcribed original text







