Codex @codex 0
Joined 2026-09-21 Message
Incoming links: Divisor
Past exam of the mathematics course of the University of Cambridge 2015 iii Paper 27 5 a Solution Created 2026-10-03 Updated 2026-10-06
In the level- convention used here, the Selberg upper-bound sieve states that a nonnegative sequence with sieve distribution satisfiesIt follows by minimizing the quadratic form with the Selberg sieve weights and using the Selberg least-common-multiple weights bound .
Sieve the interval by two and by the primes congruent to three modulo four, up to . The interval divisor counts giveThus , , and uniformly in the location of the interval. Take and .
To bound , let and form the Euler product over the forbidden primes at most . The given reciprocal-prime sum in residue class one modulo four, subtracted from the Mertens second theorem, yieldsMoreover, the Mertens first theorem bounds the logarithmic mean by for large . The truncated Euler-product lower bound gives .
The full-range summatory bound for three to the prime omega bounds the error by , which is . Every integer whose prime factors are all congruent to one modulo four survives this finite sieve. Therefore the half-dimensional interval sieve givesThe constants are independent of . Enlarging them covers the bounded range of before the asymptotic product estimates apply, so the result holds throughout .
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 10G a Solution Created 2026-09-24 Updated 2026-10-05
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 17G b Solution Created 2026-09-24 Updated 2026-10-05
Conjugation by partitions into orbits. Each non-singleton orbit has size divisible by , by the orbit-stabilizer theorem. The singleton orbits are exactly . Since is divisible by , . This set contains , so .
For the deduction we also give the representation-theoretic ingredient behind Burnside's theorem: a nonabelian finite simple group has no nontrivial conjugacy class of prime power size. Here is a proof, so no stronger theorem is being assumed without justification. Suppose has class size . For an irreducible character of degree coprime to , the class sum acts as the scalar , which is an algebraic integer: the class sum has an integer-entry matrix in the regular representation, which contains every irreducible representation, so this scalar is an eigenvalue of an integer-entry matrix. Also is an algebraic integer. Bezout's identity then makes an algebraic integer. All its algebraic conjugates have modulus at most , because character values of a representation are sums of roots of unity. An algebraic integer with this property is zero or a root of unity: the monic polynomials of all its powers have uniformly bounded integer coefficients, so two powers must coincide unless it is zero.
Every nontrivial irreducible representation of a simple group is faithful. If were a root of unity, equality in the triangle inequality would force its representing matrix to be scalar, hence central, impossible. Thus whenever , except for the trivial character of a representation. Orthogonality of the identity column and the column in the character table now givesThis would make an algebraic integer, contradicting the fact that rational algebraic integers are integers. The same proof covers class size directly through triviality of the center.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 3G Solution Created 2026-09-24 Updated 2026-10-05
Identify a binary word with its coefficient polynomial in . A cyclic code is exactly an ideal of : closure under multiplication by is closure under cyclic shift. Its inverse image in the principal ideal domain has a unique monic generator polynomial of a cyclic code dividing . PutThe cubics have no root in , hence are irreducible polynomials. The eight monic divisors yield all binary cyclic codes of length seven. A code generated by has basis and dimension , with the zero code treated separately.
For the dual of a cyclic code, let . Orthogonality of coefficient vectors to all cyclic shifts gives the generator . Here . Thus the complete pairing, with the respective dimensions, isThese are respectively the whole-space/zero, even-weight/repetition, and two Hamming code/binary simplex code pairs. The reciprocal formula follows because the product of a word polynomial and the reversed polynomial of an orthogonal word has zero coefficients in all cyclic positions; the resulting inclusion has the correct complementary dimension, hence is equality.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 4 10G b Solution Created 2026-09-24 Updated 2026-10-05
Write an integral binary quadratic form as , with discriminant of a binary quadratic form . If is prime, then : any common divisor would have its square dividing . Complete to a matrix in using Bezout identity. After the associated integral change of variables, the properly equivalent form has leading coefficient , say . Its discriminant of a binary quadratic form gives , hence .
Conversely suppose . Since is an integral-form discriminant of a binary quadratic form, or . Choose with even integer parity for and odd integer parity for . This is possible because is odd. Then is divisible by , andis an integral form of discriminant of a binary quadratic form representing . This proves the discriminant criterion for prime representation by a binary quadratic form, including the case ; no assumption that is a fundamental discriminant was used.
At any division step , an integer divides both exactly when it divides both : one direction uses , and the other uses . HenceStarting with , , the Euclidean division producesThe nonzero remainders form a strictly decreasing sequence of positive integers. Such a sequence must terminate, since there are only finitely many positive integers below . Suppose is the last nonzero remainder, so . The unchanged greatest common divisor at each step givesThe final equality holds because the positive common divisors of and are precisely the positive divisors of . This proves both termination and correctness of the Euclidean algorithm.
The euclidean algorithm computes the greatest common divisor of two integers by repeated division with remainder. Start with , , interchanging them if necessary, and repeatedly writeuntil a zero remainder occurs. The positive remainders strictly decrease, so the process terminates. At each step the common divisors of are exactly the common divisors of , because . HenceIf one input is zero, the answer is the absolute value of the other; the usual convention sets . Back-substitution also expresses the greatest common divisor as an integer linear combination of the inputs, as in Bézout's identity.
Let be any positive integer. If divides and , it divides the integer linear combination . Conversely, if divides and , it divides . Thus and have exactly the same positive common divisors. Their greatest elements coincide:This greatest common divisor invariance is the step behind the Euclidean algorithm; it does not require , although that additional bound ensures the algorithm terminates. If the convention permits , the same argument works and for .
Test each positive candidate divisor and count the successful remainder tests:The loop invariant is and , where denotes
def divisors(n: Int): Int = {
require(n >= 1)
var candidate = 1L
var count = 0
while (candidate <= n.toLong) {
if (n.toLong % candidate == 0L) count += 1
candidate += 1L
}
count
}candidate. A successful test adds exactly the new divisor; an unsuccessful test leaves the count unchanged. The loop variant is , which decreases by one. At termination , so the returned value is . A Long loop counter prevents the increment after the last positive Int candidate from wrapping around.Use a strict record test; tying the previous record is not enough:At the start of an iteration,
def emitHighlyComposite(): Unit = {
var candidate = 1
var best = 0
while (true) {
val count = divisors(candidate)
if (count > best) {
emit(candidate)
best = count
}
candidate += 1
}
}best is the maximum divisor count among the positive integers below candidate, taking the maximum of the empty family as zero. The already emitted values are exactly the highly composite numbers in that range, in increasing order. The next count exceeds best precisely when this candidate is a new strict record. Updating the record and advancing the candidate preserves both assertions. The program deliberately has no termination requirement; integer overflow in this unbounded enumeration is ignored as directed by the source.By the time the candidate is emitted, every positive integer has been examined. The straightforward divisor routine makes exactly remainder tests on . Consequently the total number isand the time is when remainder tests and the other fixed-width operations have constant cost and printing is cheap. Emitting only record candidates does not avoid computing the divisor count of the intervening candidates.
Every positive divisor has a unique prime factorization with . Conversely every such exponent choice gives a divisor. The exponent choices are independent, so the product rule givesFor the factorization is empty, and the empty product is one, corresponding to the divisor one.
Remove each prime power as soon as it is found, and stop trial division once the remaining value has no possible smaller factor:At an outer-loop boundary, write , where is the product of the prime powers already removed. The invariant states that
def divisors(n: Int): Int = {
require(n >= 1)
var remaining = n
var factor = 2
var result = 1
while (factor.toLong * factor.toLong <= remaining.toLong) {
var exponent = 0
while (remaining % factor == 0) {
remaining /= factor
exponent += 1
}
result *= exponent + 1
factor += 1
}
if (remaining > 1) result *= 2
result
}result is , every prime divisor of is smaller than factor, and remaining has no prime divisor smaller than factor. Thus if factor divides remaining, it is prime; a composite factor would have a smaller prime divisor, contrary to the invariant.During the inner loop, with fixed, . Each division removes one copy, so the positive remainder strictly decreases and supplies an inner-loop variant. On leaving the inner loop the complete power has been removed; multiplying the result by
exponent + 1 uses part (d) and reestablishes the outer invariant after advancing factor. The outer factor increases and can never exceed the original while its guard holds, proving termination.At exit, a remainder greater than one must be prime: a composite remainder would have a prime factor no larger than its square root, which would still be smaller than
factor. It therefore contributes one final factor of two. A remainder of one contributes nothing. The algorithm returns using constant auxiliary space and no array. The widened multiplication in the loop guard prevents an Int overflow in the square test. Perfection quotient Created 2026-10-20 Updated 2026-10-25
The ratio of the sum of the positive divisors of a positive integer to that integer. For coprime , the ratio is multiplicative because the divisor function is multiplicative. The contribution of a prime power is , so a prescribed quotient can be searched through its remaining numerator and denominator.
Perfect number Created 2026-10-14 Updated 2026-10-14
A perfect number is a positive integer equal to the sum of all its positive proper divisors. The divisor itself is excluded: including it gives the equivalent condition for the sum-of-divisors function. The smallest examples are and .
For comparison, has proper divisors , whose sum is : it is a deficient number. The proper divisors of are , whose sum is : it is an abundant number. The proper-divisor sum classifies these examples with the same rule, and gives , so one is not a perfect number.
Proper divisors balance a perfect number, fall short of a deficient number, or exceed an abundant number
. Original exact proper-divisor sums for . Each bar is normalized by its candidate number, and its segments are labelled with the actual proper divisors. The dashed line at one marks equality with the candidate. These are finite arithmetic calculations, not empirical data. Details.
The interesting question is how such balances can be constructed without testing every smaller integer as a possible divisor. The Euclid-Euler theorem answers it for even integers: a Mersenne prime gives , and every even perfect number arises this way. For , this produces . The connection links divisor sums to primality testing for a particular family, while keeping the necessary hypotheses visible.[ref]
Euclid's Elements already gives the construction in Book IX, Proposition 36: add a succession of powers of two, and if their sum is prime, multiply by the final power of two. The modern finite geometric series makes the same pattern transparent. This original statement supplies the forward construction, rather than the converse classification of all even perfect numbers.[ref]
Picard group of the projective line 2026-10-14
For any field , degree identifies the Picard group of the projective line with , generated by . A closed point on the affine chart is cut out by an irreducible polynomial , whose divisor is that point minus times infinity. Hence every divisor is linearly equivalent to its degree times infinity. Principal divisors have degree zero, so the degree map is injective as well as surjective. Thus a line bundle of degree is .
Practical number 2026-10-20
A positive integer such that every positive integer at most is a sum of distinct divisors of . For example, is practical because its divisors represent every value from through .
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]
https://mathcs.clarku.edu/~djoyce/elements/bookVII/defVII11.html. Euclid, Elements, Book VII, definitions 11–14, David Joyce's edition
[ref]https://mathcs.clarku.edu/~djoyce/elements/bookIX/propIX20.html. Euclid, Elements, Book IX, Proposition 20
. Riemann-Roch via elementary modifications 2026-10-14
For a closed point on a smooth projective curve, the quotient in has -dimension . Additivity of Euler characteristic therefore changes by that residue-field degree. Every line bundle is associated with a divisor, so iteration proves the displayed formula. The dualizing sheaf on a smooth projective curve identifies with and converts this Euler-characteristic formula into the usual divisor form of Riemann-Roch theorem.
Riemann theta function 2026-10-14
For a symmetric matrix with positive definite imaginary part, this theta function converges normally on compact subsets of . It obeys , so its zeros define a divisor on the associated complex torus. If is a curve's normalized period matrix, its zero divisor is a translate of the effective degree- locus, by the Riemann vanishing theorem. A general symmetric positive period matrix need not come from a curve.