Binary fraction 2026-10-25
A base-two positional fraction with a binary point separating nonnegative and negative powers of two. For example, . A finite expansion is a dyadic rational: with fractional places, its value is an integer divided by . Conversely, any nonnegative reduced fraction whose denominator is a power of two has a finite binary expansion. Leading integer zeroes and trailing fractional zeroes do not change its value.
Character large sieve Created 2026-10-06 Updated 2026-10-07
For coefficients supported on consecutive integers,The star restricts to primitive Dirichlet characters. Their finite Fourier transform of a primitive Dirichlet character has normalization of absolute value . Orthogonality of Dirichlet characters therefore bounds the weighted contribution for one modulus by . Sum over and use the exponential-sum large sieve on the distinct reduced fractions of denominators at most .
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
Coresilience Created 2026-10-20 Updated 2026-11-05
For an integer , the coresilience iswhere is Euler's totient function.[ref] It is related to the resilience of a denominator , but is not its complement:For a prime number , but , rather than zero. For the composite number fifteen, and .
As , the value is a unit fraction precisely when divides . A composite prime power with cannot qualify: its value is , already a reduced fraction with numerator greater than one. This excludes an entire family of composite numbers before a search.
Decimal period from multiplicative order 2026-10-14
For a reduced fraction with , , and coprime integers, its decimal representation repeats immediately after the decimal point. The shortest repeating block has lengthHere denotes multiplicative order, and denotes Euler's totient function. Changing the numerator preserves the decimal period as long as the fraction remains reduced.[ref]
For example, long division of gives the remainders , with emitted digits . ConsequentlyEach remainder determines both the next digit and the next remainder; returning to one restarts the same six steps.
Long-division remainders explain the six-digit repeat of one seventh and the two-digit prefix of one twenty-eighth
. Details. More generally, initialize long division with . At each step, division with remainder givesso . Since are coprime integers, the modular inverse of shows that exactly when . To see why the digit block cannot repeat sooner than the remainders, a purely repeating decimal with a block of digits represents for an integer . A reduced fraction with that value forces . Hence the shortest digit repeat and the multiplicative order coincide.
Knowing the decimal period predicts how many digits must be computed and stored: one block determines the whole repeating decimal. It also constructs the block directly. With , the integeris the block, padded on the left with zeros to digits. For , and , so the block is and . Reduction matters: has decimal period one, whereas .
If the reduced denominator contains prime factors two or five, ten has no multiplicative order modulo that whole denominator. WriteThe decimal preperiod has exactly digits. If , the remaining repeating decimal has decimal period . For instance, gives : two prefix digits, then six repeating digits. If , the decimal representation is a terminating decimal with exactly fractional places. We use the representation ending in zeros, rather than its alternative ending in nines; for example terminates after three places.
A short derivation explains both cases. After digits, multiplying the reduced fraction by and discarding its integer part leaves a reduced fraction whose denominator is . This denominator first becomes coprime to ten at . It then equals , giving an immediate repeat when , or an integer when . The same long division argument works for positional notation in any base : for a reduced denominator coprime to , the shortest repeating block has length .
Decimal preperiod 2026-10-14
The shortest prefix before the repeating tail of a decimal representation. For a reduced fraction with denominator , where is coprime to ten, its length is ; the tail length is given by decimal period from multiplicative order.
Denominator Created 2026-10-14 Updated 2026-11-05
The denominator is the nonzero lower entry in a fraction . It specifies the division being performed; with , the unit fraction is the size of one part. Thus and have the same numerator but different values.
An integer fraction can always be written with positive denominator. Dividing both entries by their greatest common divisor gives a reduced fraction, so and represent the same rational number despite different denominators.
A zero denominator is excluded from ordinary rational numbers. The symbol used at the boundary of the Stern-Brocot tree is a formal boundary symbol, not an additional rational number produced by division by zero.
Farey sequence Created 2026-10-07 Updated 2026-11-05
For a positive integer , the Farey sequence is the increasing list of reduced fractions in with denominators at most , including and . For example,Each denominator contributes exactly new interior fractions, because the allowable numerators are precisely those coprime to . Therefore the number of terms is , using the summatory totient function.
For two distinct fractions in the list, their difference is , since the integer is positive. This arithmetic separation, rather than arbitrary real spacing, makes Farey fractions useful in rational approximation. The Stern-Brocot tree organizes the same positive reduced fractions by mediant insertion instead of a denominator cutoff.
Fraction Created 2026-10-14 Updated 2026-10-20
A fraction represents the quotient of its numerator by its nonzero denominator . For integers this is a rational number. Different fractions can represent the same number: . Dividing both entries by their greatest common divisor gives a reduced fraction, with the sign convention that the denominator is positive.
Numerator Created 2026-10-14 Updated 2026-11-05
The numerator is the upper entry in a fraction . For an integer fraction, it records how many signed units of size are being taken when the denominator is positive: takes three fifths, while reverses the sign.
A numerator belongs to a chosen representation, rather than being determined by the rational number alone. The equal fractions and have different numerators. The reduced fraction convention makes the numerator and positive denominator unique; zero then has numerator zero and denominator one.
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 27 2 c Solution Created 2026-10-03 Updated 2026-10-06
For a fixed prime , the grid has circular spacing . Consequently an arc of length contains at most three points of this grid, including endpoints. The standard Chebyshev estimate for the prime-counting function givesSince , the local-multiplicity large sieve yields the prime-denominator large sieve:By contrast, distinct reduced fractions with denominators at most have circular distance at least : their difference, even after subtraction of an integer, has a nonzero integer numerator over denominator . Applying part (a) alone gives only . The local-multiplicity argument saves a factor of .
procedure toRat(e; var m,n)
require 0 <= e.i <= N and every stored denominator is positive
m := 0
n := 1
j := 0
while j < e.i do
q := e.x[j]
m := m*q+n
n := n*q
Reduce(m,n)
j := j+1The loop invariant is that is the reduced fraction equal to the sum of the first terms, with . The update is exactly , and the greatest common divisor reduction preserves it. The loop variant decreases to zero. The empty sum gives .
For a positive remaining fraction , the condition is equivalent to . Since decreases as the positive integer increases, choose . The zero fraction needs no term. This is the greedy Egyptian fraction expansion.
The remaining fraction isThe defining inequalities give . Therefore the unreduced new numerator is a nonnegative integer strictly smaller than the old positive numerator. Passing to a reduced fraction can only reduce it further. That numerator is a loop variant, so the process terminates. The increasing denominators are not the termination argument; their size need not be bounded in advance.
An Egyptian fraction need not be proper: several positive unit fractions may sum to at least one. Accordingly, accumulate a general nonnegative reduced fraction, rather than calling the proper-input-only The loop invariant is , , , , andWriting , the fraction for the extended prefix has numerator and denominator . These are the
Reduce on every intermediate value. First define an exact helper:def toRatExact(e: Array[Int]): (BigInt, BigInt) = {
var n = BigInt(0)
var d = BigInt(1)
var i = 0
while (i < e.length) {
require(e(i) > 0)
val x = BigInt(e(i))
val g = d.gcd(x)
val nextN = n * (x / g) + d / g
val nextD = d * (x / g)
val h = nextN.gcd(nextD)
n = nextN / h
d = nextD / h
i += 1
}
(n, d)
}
def toRat(e: Array[Int]): (Int, Int) = {
val result = toRatExact(e)
require(result._1.isValidInt && result._2.isValidInt,
"Reduced result does not fit (Int, Int)")
(result._1.toInt, result._2.toInt)
}nextN and nextD in the code. Reducing them preserves the value and restores coprimality. The loop variant is . At exit the helper returns the exact sum in lowest terms, including for the empty array.There are three distinct ways to control integer overflow: cancel the common denominator factor before multiplication, reduce after each addition, and use arbitrary-precision arithmetic when the remaining values still exceed fixed-width bounds. Cancellation reduces intermediate size but cannot guarantee that an exact answer fits
(Int, Int). For example, the sum is in lowest terms, whose denominator exceeds Int.MaxValue. No implementation returning that fixed type can represent every permitted input exactly. The wrapper therefore checks this unavoidable result-type limitation instead of silently truncating; toRatExact supplies the unrestricted mathematical result.[ref]Scala 2.12 BigInt API documentation. Checked representability with isValidInt before the potentially truncating toInt conversion
Prime-denominator large sieve 2026-10-06
When ,An arc of length contains at most three points of each grid of denominator . The Chebyshev estimate gives such primes. Apply the local-multiplicity large sieve. Using only the separation of distinct reduced fractions gives the weaker .
Proper fraction Created 2026-10-31 Updated 2026-11-05
A nonnegative fraction with positive denominator and numerator smaller than its denominator, so its value lies in . The zero value has the reduced fraction representation . The term is sometimes extended to negative fractions by comparing absolute values; the nonnegative convention is the one used here.
Rational number Created 2026-09-24 Updated 2026-11-05
A rational number is a quotient of integers with . The numerator can be negative or zero; the denominator can be chosen positive by transferring its sign to . For example, and .
Different fractions describe the same rational number exactly when cross multiplication gives . Dividing the entries by their greatest common divisor produces the unique reduced fraction with positive denominator, including for zero.
The rational numbers form a field: addition, subtraction, multiplication and division by a nonzero rational number remain rational. They are dense in the real line, by density of the rational numbers, although they do not fill it: the square root of two is an irrational number.
Reduced fraction Created 2026-10-06 Updated 2026-11-05
A reduced fraction has coprime integers and positive denominator . Distinct reduced fractions with denominators at most differ by at least , since their difference has a nonzero integer numerator over a denominator at most .
Resilience of a denominator Created 2026-10-20 Updated 2026-11-05
For an integer , the resilience of a denominator is the fraction of its proper fractions already in lowest terms. The fraction is a reduced fraction exactly when and are coprime, sowhere is Euler's totient function.
For , the allowed numerators are , giving . A prime denominator has resilience one. Conversely, a composite number has a proper prime divisor , and is among the listed fractions but is not reduced; thus its resilience is strictly less than one.
The prime factorization formula givesThe correction comes from sampling the positive proper numerators, rather than all residue classes. The related coresilience uses .
Stern-Brocot tree 2026-10-20
A binary tree enumerating every positive reduced fraction exactly once. Begin with boundary fractions and ; between neighboring fractions , insert their mediant and recurse into the two new intervals. The determinant relation is preserved, and the new denominator is .

