Generalized repunit pseudoprime construction Created 2026-09-24 Updated 2026-11-05
Fix an integer and an odd prime not dividing . Thenis a composite number that is a Fermat pseudoprime to base .
For compositeness, factorBoth factors are integers because is odd, and both exceed one for and . Also , so is coprime to .
By Fermat's little theorem, . Since is invertible modulo , this gives . The displayed sum is odd for either parity of , so . Finally , and raising this identity to the integer power proves .
Jacobi symbol Created 2026-09-24 Updated 2026-11-05
For an odd positive integer , the Jacobi symbol is the product of Legendre symbolsThe fundamental theorem of arithmetic makes this definition unambiguous. Its value is zero exactly when and have a common prime factor; otherwise it is or . For , the empty product convention gives .
If is a quadratic residue modulo and is coprime to , its Jacobi symbol is one. The converse can fail for a composite number: , but two is not a square modulo fifteen because it is not a square modulo three.
Computing the Jacobi symbol does not require first finding the prime factorization. Repeatedly remove factors of two, swap odd numerator and denominator using Jacobi reciprocity, and reduce the numerator modulo the denominator, as in the Euclidean algorithm. This makes it useful in the Solovay-Strassen primality test.
Legendre prime-counting formula Created 2026-10-05 Updated 2026-10-20
For , let be the primes at most . The inclusion-exclusion principle counts unsieved positive integers by . These are and the remaining primes, since every composite number has a prime factor at most its square root. Hence for . This is a prime-counting identity, distinct from the Legendre formula for factorial valuations.
Legendre's formula Created 2026-10-14 Updated 2026-11-05
For a nonnegative integer and a prime number , the Legendre formula computes the prime exponent in a factorial without forming that huge product:Here is the floor function. The sum is finite: every term with is zero. When , all terms vanish, agreeing with and . The prime number hypothesis matters: a composite number does not give the same p-adic valuation or additive prime exponent. For example, the floor sum with is one, whereas divides .
Why count multiples repeatedly? Each multiple of in contributes one factor of ; each multiple of contributes another; and so on. A factor with p-adic valuation occurs in exactly the first counts. Adding those contributions proves the formula.[ref]
Number Theory for Mathematical Contests by David Anthony Santos. David A. Santos, Number Theory for Mathematical Contests, revision 31 October 2007, §8.3, Theorem 245, printed pp. 89–90: factorial valuation and digit form
For the original example ,The five multiples each contribute a second factor of three. The factor contributes a third, so it appears in all three rows. Equivalently, among there are eleven factors of p-adic valuation one, four of valuation two, and one of valuation three: . Thus divides , while does not.
Nested multiples count the factors of three in
. Each colored cell contributes one to the p-adic valuation. Multiples of nine occur in two rows, and occurs in three. Summing by rows gives ; summing by columns gives . Factors not divisible by three contribute zero and are omitted. Details.Repeated Euclidean division provides a practical evaluation: replace by , starting from , and add each new quotient until it is zero. This uses only the successive quotients for the example. The same calculation handles divisibility of binomial coefficients, where the p-adic valuations of the denominator factorials are subtracted.
Linear sieve 2026-10-20
A number-theoretic sieve that visits each composite number exactly once, through its smallest prime factor. Keep a growing list of prime numbers; for each , generate only for stored primes . Each composite has a unique representation admitted by this rule, giving arithmetic updates up to .
Mathematical proof Created 2026-09-24 Updated 2026-10-14
A mathematical proof is a finite deductive argument from stated assumptions to a conclusion. It explains why the conclusion follows for every instance covered by its hypotheses. An informal mathematical proof can omit routine detail while making its assumptions and deductions clear; a formal proof expresses them in a specified formal language with specified inference rules. The distinction between assumptions, propositions, and deductions is introduced in Leighton and Rubinfeld, What is a proof?, sections 1–3.
Checking examples can suggest a pattern, but need not establish a universally quantified claim. For example, the polynomial is a prime number for every integer , as direct trial division verifies. At it equals , a composite number. Those first forty successes do not prove the claim for all natural numbers; one counterexample disproves it. The point is not to discard computation: it can find a conjecture, detect a mistake, or verify a finite exhaustive case analysis. The question is whether the cases checked cover the statement being claimed.
For a positive example, the sum of two even integers is even: writing them as and with gives , and is an integer. This direct argument handles every allowed pair at once. A useful mathematical proof therefore does more than certify an answer: it exposes the mechanism and the exact assumptions that make the answer transferable.
Michael O. Rabin 2026-11-05
Michael O. Rabin analyzed a randomized algorithm for primality testing in his 1980 paper. The Miller-Rabin primality test checks whether a candidate integer satisfies conditions obeyed by primes under modular exponentiation. A failed check certifies compositeness; passing a check gives a probable prime, not a proof of primality.[ref]
For each fixed odd composite candidate, at most one quarter of the admissible bases are strong liars. Independent uniformly chosen bases therefore reduce the probability of accepting that composite to at most after rounds. This probability is over the test's choices for a fixed input; it is not a posterior probability that an arbitrary accepted integer is prime.
Miller-Rabin primality test Created 2026-10-14 Updated 2026-11-05
For an odd integer , write with odd. Choose a base uniformly from . It passes the Miller–Rabin test whenA nontrivial greatest common divisor of or failure certifies compositeness. Exponentiation by squaring computes ; at most further squarings test the other possibilities.
Every prime number passes: arithmetic modulo a prime number is a field, whose only square roots of one are and . The squaring chain ends at one by the Fermat little theorem; its first one is either the initial value or follows minus one.
For an odd composite number, at most one quarter of bases in the stated range pass. Thus independently sampled bases give false probable-prime probability at most , for each fixed composite input. A passing composite is a strong pseudoprime to that base.[ref]
Number-theoretic sieve 2026-10-20
A number-theoretic sieve processes many integers together by marking or updating those sharing a divisor, rather than testing each integer independently. The sieve of Eratosthenes marks composite multiples of successive prime numbers; related sieves accumulate a smallest prime factor, Euler's totient function, or Möbius function for every argument up to a bound. The useful structure is that the multiples of a fixed integer form an arithmetic progression, so one loop can update all affected entries in an array.
For example, initializing an array to true and then marking for each surviving prime number leaves precisely the prime numbers unmarked, apart from the separately excluded zero and one. Every composite number has a prime factor, which proves that every composite is eventually removed. Starting the marking at avoids work already performed by smaller prime numbers. Different sieves use different update rules and time complexity bounds; the name alone does not imply the complexity of the sieve of Eratosthenes.
Number theory Created 2026-09-24 Updated 2026-10-13
Number theory studies integers, their divisibility, and the patterns created by prime numbers. Its questions often have short statements but rigid answers: which integers divide a given one, when does an equation have integer solutions, and when can arithmetic with congruence classes be reversed? The Euclidean algorithm and modular multiplicative inverses connect these questions through explicit calculations.
For example, and . Their shared prime factors give greatest common divisor . The Euclidean algorithm reaches that answer without finding either complete prime factorization. It also produces , an instance of Bézout's identity. This relation certifies every common divisor at once and solves an associated linear Diophantine equation.
Modular arithmetic retains only remainders, but the lost information can be surprisingly controlled. Multiplication by modulo is a permutation of all residue classes, because has modular inverse . Multiplication by modulo collapses fifteen residue classes to three. Thus an apparently small change in the modulus changes whether a calculation can be reversed. The Chinese remainder theorem explains another kind of compression: remainders modulo coprime integers can be combined into one remainder modulo their product.
Simple restrictions help reveal the structure without telling the whole story. Every prime number greater than three is congruent to or modulo : the other four residue classes force divisibility by or . The converse fails because and lie in those classes but are composite numbers. Necessary conditions are useful filters, not substitutes for primality testing.
The subject's appeal lies partly in this tension: prime factorization gives a clean description of every positive integer, while identifying factors and predicting their distribution lead to substantial further questions. Analytic number theory uses tools from analysis to study global patterns, and algebraic number theory extends arithmetic into number fields. Applications include cryptography and error-correcting codes; MIT's discrete applied mathematics course develops modular structures for both purposes. [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, Modular Arithmetic and Elementary Algebra, 2024, introduction
Euclid's Elements already gives a greatest-common-measure construction in Book VII, Proposition 2, and the argument that a finite list cannot exhaust the prime numbers in Book IX, Proposition 20. These are documented ancient treatments, rather than evidence that all of number theory began with one author. [ref]
https://mathcs.clarku.edu/~djoyce/java/elements/bookVII/propVII2.html. Euclid, Elements VII.2, translated text hosted by David Joyce
[ref]https://mathcs.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html. Euclid, Elements IX.20, translated text hosted by David Joyce
Odd number Created 2026-09-24 Updated 2026-11-05
An odd number is an integer not divisible by . Equivalently, it has the unique formThe Euclidean division remainder is one. Examples include ; zero is excluded because it is an even number. The property is independent of primality: is a prime number, is a composite number, and is neither.
It performs a trial division test for a prime number. An integer below is rejected; otherwise the function searches for a divisor from through . A composite number has a prime factor no larger than its square root, so finding no such divisor proves primality. For example,
mystery2(97) returns True, while mystery2(91) returns False, since .This describes the intended mathematical test. For extremely large integers, the floating-point computation
n**0.5 can round or overflow; an implementation intended for arbitrary-size integers should use an exact integer square root. Past exam of the mathematics course of the University of Cambridge 2015 ia Paper 4 1E b Solution Created 2026-09-24 Updated 2026-10-06
Write the composite number as , with . If , both and occur as distinct factors of the factorial , so their product divides that factorial.
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 2 1G Solution Created 2026-09-24 Updated 2026-10-05
The Legendre prime-counting formula counts positive integers surviving a finite prime sieve. For , put and let be the primes at most . By inclusion-exclusion principle, the number of positive integers at most divisible by none of these primes isThe empty product is . Every composite number at most has a prime factor at most , so the survivors are precisely and the primes between and . ConsequentlyFor , the sieving primes are , andAs a direct check, the primes are .
Past exam of the mathematics course of the University of Cambridge 2017 ii Paper 3 1G Solution Created 2026-09-24 Updated 2026-10-05
An Euler pseudoprime is an odd composite number with satisfying , where the right side is the Jacobi symbol. A weaker convention requires only ; it is distinguished below. A strong pseudoprime, with and odd, satisfies or for some .
By the Chinese remainder theorem for unit groups, the unit group modulo is . Modulo , . Thus the only possible sign in is positive. Modulo , writing for a primitive root, the condition is , equivalently . Consequently has multiplicative order dividing in each factor. Its square is either or in each factor, but these signs must agree: modulo , the Legendre symbol is for square and for square , and the same is true modulo . The Euler pseudoprime condition additionally requires the product of those Legendre symbols to be . HenceEach sign has two roots modulo each prime, hence four roots modulo . There are eight pseudoprime bases modulo under the Jacobi symbol convention. Under the weaker sign-only convention there are instead sixteen pseudoprime bases, since the two signs of the squares need not agree; the stated equivalence therefore specifically uses the Jacobi symbol convention.
For the strong pseudoprime condition, . Since the unit group has exponent of a finite group , the only possibilities are or . The six pseudoprime bases are . For example , while has but . Thus the strong-pseudoprime pseudoprime bases are not a subgroup.
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 1 1I b Solution Created 2026-09-24 Updated 2026-10-03
An odd composite number with is a Fermat pseudoprime to base whenFor , the Chinese remainder theorem for unit groups reduces this condition to congruences modulo and . Modulo , Fermat's little theorem givesso exactly when . Modulo , the unit group has order , soThe equation in the cyclic group has solutions, namely .
Past exam of the mathematics course of the University of Cambridge 2020 ii Paper 3 1H Solution Created 2026-09-24 Updated 2026-09-29
Let be the unit group of residue classes modulo , and partition it into the set of bases satisfying the displayed congruence and the set of Euler witnesses that do not. If , multiplication by maps injectively into : indeed, if and also lay in , then the multiplicativity of the Jacobi symbol would giveCancelling the invertible congruence for would say that , a contradiction. Hence , so at least half of the coprime bases are witnesses.
It remains to construct one witness for every odd composite number . If is not squarefree, choose an odd prime number with . The Chinese remainder theorem gives a unit such that for the full power and modulo every other prime-power factor. The binomial theorem givesSince , this is neither nor modulo , whereas the Jacobi symbol is always or . Thus is a witness.
If is squarefree and composite, choose distinct primes . By the Chinese remainder theorem, choose to be a quadratic nonresidue modulo and to satisfy modulo every other prime divisor of . Then , while , so the Euler congruence again fails. This proves the existence of an Euler witness for every odd composite integer.
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 3 1G c Solution Created 2026-09-24 Updated 2026-10-03
Suppose that the positive integer is a decisive number. For every prime number , the composite number satisfies . It therefore cannot be coprime to , so .
The product of all prime numbers below consequently divides . Taking natural logarithms givesChanging the strict endpoint can remove at most one prime term. By part b, for every sufficiently large the right-hand side is at least, for example, . This is impossible for sufficiently large , sinceThus every decisive number lies below one fixed bound, and only finitely many integers can do so.
For the requested On its intended input,
Int-typed operation, remove the first element as well as its later multiples:sieve :: [Int] -> [Int]
sieve [] = []
sieve (p:xs) = [x | x <- xs, x `rem` p /= 0]p is positive, so the remainder is defined. An arbitrary list headed by zero lies outside this convention.To enumerate literally all prime numbers, use unbounded At each stage, the smallest remaining number has no smaller prime divisor and is therefore prime. Removing its larger multiples preserves every later prime and removes any composite number once its least prime divisor is processed. Lazy evaluation makes each requested finite prefix available. This implements the given repeated-filtering form of the sieve of Eratosthenes. A bounded
Integer arithmetic:primes :: [Integer]
primes = go [2..]
where
go :: [Integer] -> [Integer]
go [] = []
go (p:xs) =
p : go [x | x <- xs, x `rem` p /= 0]Int stream can only cover representable values; Integer supplies the all-primes interpretation. 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
.