Agrawal–Biswas primality test Created 2026-09-24 Updated 2026-11-05
The Agrawal–Biswas primality test tests a formal polynomial identity in :
For , the identity holds exactly when is a prime number. Testing a formal polynomial is stronger than evaluating it at residues.
The randomized algorithm first handles prime numbers at most thirteen, divisibility by them, and perfect powers. For remaining , choose a monic polynomial of polynomial degree , with independent uniform lower coefficients modulo . Compute the remainder of modulo using exponentiation by squaring. A nonzero remainder proves compositeness. The monic polynomial permits division even when the coefficient ring has zero divisors.
Every prime number passes. After preprocessing, a composite number is rejected with probability at least per trial, so independent trials give error at most . Keeping remainders below polynomial degree makes the computation polynomial time in the bit length of .[ref]
Carmichael function Created 2026-09-24 Updated 2026-10-20
For an integer , the Carmichael function is the exponent of a finite group for the unit group : the least positive integer for which
Here the greatest common divisor condition selects the units. Euler's totient function counts them; the Carmichael function gives their least common return exponent.[ref]
Modulo eight, the units are , and their squares are all congruent to one. Their multiplicative orders are , so although . Modulo fifteen, the units have multiplicative orders . For example, the powers of two return through . Thus although ; the multiplicative order of four is only two.
Figure 1.
Individual unit orders divide the least common return exponent modulo eight and fifteen
. Details.
The three quantities are related by
A common return exponent must be a multiple of every multiplicative order, hence of their least common multiple. Conversely, that least common multiple makes every unit return to one. Lagrange's theorem makes each multiplicative order divide the group order , proving the final divisibility. The Carmichael function applies to all units at once, while the multiplicative order concerns a chosen unit.
For the prime factorization with distinct prime numbers and , the formulas are
These are least common multiples, rather than products: . The convention handles the trivial case separately.[ref]
The Chinese remainder theorem for unit groups explains the least common multiple: a power returns to one in every prime power component exactly when it is a multiple of each component's exponent of a finite group. For an odd prime power, the unit group is a cyclic group of group order . For , the unit group modulo is a direct product of groups , generated by the classes of and five, so its exponent of a finite group is .[ref]
This gives a uniform reduction for modular exponentiation: for a unit and a nonnegative integer , reduce modulo . For example, because . The unit hypothesis matters: , but . Computing the formula assumes the prime factorization is available. The same common-exponent viewpoint explains Carmichael numbers: a composite number passes the Fermat primality test for every unit base exactly when . For example, .
Carmichael number Created 2026-09-24 Updated 2026-10-18
A Carmichael number is a composite number for which
Every unit modulo satisfies the same modular congruence supplied by Fermat's little theorem for a prime number. The name refers to Robert Daniel Carmichael. The coprime qualification is essential: a nonunit can expose a prime factor through a greatest common divisor calculation. A Carmichael number is therefore a Fermat pseudoprime to every coprime base, rather than to every nonzero residue class.[ref]
For example,
The factors are distinct prime numbers. Their predecessor numbers all divide , so Korselt criterion applies. More explicitly, for any integer coprime to , Fermat's little theorem gives
The Chinese remainder theorem combines these into . This proves all coprime bases pass from three short divisibility checks, rather than from a long table of sampled bases.
Figure 1.
Three prime factors certify that every unit passes the Fermat congruence modulo 561
. Original arithmetic certificate for . Exponents divide with quotients ; the Chinese remainder theorem combines the three prime-modulus conclusions. Details.
Equivalently, a composite is a Carmichael number exactly when for every integer , including nonunits. The equivalence follows from Korselt criterion: modulo each prime factor, either is zero or its nonzero power returns to one, and squarefreeness combines those congruences. This does not say a nonunit satisfies . For instance gives , while ; the greatest common divisor already supplies the factor three.[ref]
The Carmichael function supplies another compact description: a composite is Carmichael exactly when . For , and . In contrast, Euler's totient function gives , which does not divide . The least common return exponent, rather than the number of units, controls this test.
The obstruction is useful to know when interpreting a Fermat primality test: even checking every coprime base cannot certify primality. The passing-base fraction for the Fermat test makes this failure quantitative. Stronger primality tests require additional structure, such as the squaring conditions in a Miller-Rabin primality test.
The historical record predates the name. Václav Šimerka's 1885 paper lists on printed page 224, together with factorizations. This is an early published list of examples, independently of their later name.[ref]
Composite number Created 2026-09-24 Updated 2026-10-20
A composite number is an integer greater than one that is not a prime number. Equivalently, it has a factorization with integers . Thus , , and are composite numbers; one is neither a composite number nor a prime number.
Every composite number has a prime factor at most its square root. In , seven is the smaller factor and lies below ; in , equality occurs. This square-root bound makes trial division finite and lets the sieve of Eratosthenes stop marking with prime numbers beyond when listing prime numbers up to .
Computing Legendre symbols by quadratic reciprocity Created 2026-10-14 Updated 2026-10-31
The practical reward of quadratic reciprocity is a smaller modulus: swap a pair of distinct odd primes, record the required sign, then reduce the numerator by modular arithmetic. Use multiplicativity of the Legendre symbol and the second supplementary law for quadratic reciprocity to handle a factor of two. For example,
Here are both modulo , so the first swap changes sign; gives ; the swap involving five has no sign change. An independent square check is . The method determines existence of a square root without itself finding that root.
A composite numerator is allowed in a Legendre symbol; a composite denominator instead calls for a Jacobi symbol. Its Jacobi reciprocity law supports repeated swaps and remainder reductions, in the spirit of the Euclidean algorithm.[ref]
A final Jacobi symbol of one is not a square-existence certificate for a composite number modulus. For example,
yet is impossible: reducing it modulo three would require a square congruent to two, and squares modulo three are only zero or one. The product has hidden two local failures. By contrast, for a prime denominator, a Legendre symbol of one does certify a quadratic residue.
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]
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 is
The 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]
Figure 1. . Filled cells mark membership in the prime support of an integer; empty cells mean the prime number does not divide the row label. The first panel has two coprime integers; the middle has joint coprimality but fails pairwise coprimality; the last has pairwise coprimality. The columns exhaust all prime factors of these eight row entries. This original finite arithmetic diagram shows exact divisibility, not sampled probabilities. Details.
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]
Coresilience Created 2026-10-20 Updated 2026-11-05
For an integer , the coresilience is
where 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.
Euclid-Euler theorem 2026-10-14
An even integer is a perfect number if and only if
This forces to be a prime number, as shown under Mersenne number. It does not say that every prime exponent works, nor classify possible odd integers.[ref]
For the forward direction, put and use coprimality of and . Multiplicativity of the sum-of-divisors function and the finite geometric series give
The prime number hypothesis makes ; replacing it with a composite number changes this factor.
For a short converse outline, write with and an odd integer. The condition gives
Here is a positive integer and a proper divisor of . If , the distinct divisors alone exceed the required sum . Thus and , forcing to be prime and .
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].
Euler pseudoprime Created 2026-09-24 Updated 2026-11-05
An odd integer that is a composite number is an Euler pseudoprime to a base coprime to when
where the right-hand side is the Jacobi symbol. Here this term refers to the Euler-Jacobi condition, rather than merely requiring the left side to be one of .
Every odd prime satisfies this congruence by Euler's criterion, because its Jacobi symbol is the Legendre symbol. A composite passing it is therefore a false positive for that base in the Solovay-Strassen primality test. For example, and pass: gives , and . A failed congruence instead supplies an Euler witness.
Euler's theorem Created 2026-10-03 Updated 2026-11-05
For an integer modulus and an integer with greatest common divisor , Euler's theorem, also called the Fermat-Euler theorem, states
Here Euler's totient function counts the units in the unit group . These congruence classes have modular multiplicative inverses, equivalently their representatives are coprime to . The guaranteed return to one permits exponent reduction for units.[ref]
For a prime number , , recovering Fermat's little theorem in the form when . Multiplying by and separately handling gives for every integer . For a composite number used as the integer modulus, a nonzero congruence class can be a nonunit.
Modulo twelve, the units have representatives , so Euler's totient function gives . Multiplication by five produces
Thus this permutation has two permutation cycles, each of length two. In particular , and the guaranteed return follows. The number of units need not be the length of one permutation cycle. Modulo fifteen, multiplication by seven similarly gives the two permutation cycles and , covering all eight units. The powers of seven follow the permutation cycle containing one; the other permutation cycle shows that these powers do not visit every unit.
Figure 1.
Two unit permutations: multiplication by five modulo twelve and by seven modulo fifteen
. Every arrow multiplies by the indicated unit and reduces modulo the indicated integer modulus. The permutation cycles exhaust each reduced residue system. The permutation cycle containing one records the powers of the multiplier; its length is the multiplier's multiplicative order, which can be smaller than Euler's totient function. Details.
There is a stronger obstruction for a nonunit than just an occasional failed calculation. If a positive integer divides both and , then for every , so cannot be congruent to one modulo . For example, and , rather than one. Such a base has no multiplicative order modulo that integer modulus.[ref]
Euler witness Created 2026-09-29 Updated 2026-11-05
For an odd integer and a base coprime to , an Euler witness is a base for which
By Euler's criterion, this failure cannot occur for an odd prime, so it certifies that is a composite number.
For example, take and . Then , while the Jacobi symbol is . Thus the base two witnesses the compositeness of fifteen without supplying its factors. If instead , the greatest common divisor already gives a proper divisor, so a primality test can reject before computing this congruence.
Existence of an Euler witness for every odd composite integer Created 2026-09-29 Updated 2026-11-05
Every composite number that is an odd integer has an Euler witness. There are two cases.
If divides for a prime number , write with and . The Chinese remainder theorem chooses and . This base is a unit modulo and has Jacobi symbol , because it is one modulo every prime divisor. But with , the binomial theorem gives . Since , this is not one, so the Euler congruence fails.
If is squarefree, it has at least two distinct prime factors. Choose to be a quadratic nonresidue modulo one factor and one modulo every other factor, again by the Chinese remainder theorem. Then , while is one modulo a different prime factor. It therefore cannot equal the Jacobi symbol modulo .
Factorization tree Created 2026-10-14 Updated 2026-10-20
A factorization tree is a rooted tree whose root is an integer . Each nonleaf label is a composite number split into two factors greater than one whose product equals that label; the leaves are prime numbers. Multiplying the leaves recovers . Many factorization trees can have the same root, but the fundamental theorem of arithmetic gives them the same leaf multiset.
Fermat little theorem Created 2026-09-24 Updated 2026-10-14
For a prime number and an integer not divisible by , Fermat's little theorem states the modular congruence
Equivalently, for every integer , including and multiples of ,
The first formulation follows from the second by multiplying by a modular multiplicative inverse of . Conversely, multiply the first by when ; when , both sides of the second are zero modulo . The divisibility condition in the first formulation is essential.[ref]
For , , so and . Also , while : a zero residue class cannot satisfy the first formulation. It does satisfy . A failure at a zero residue class therefore says nothing against a candidate's being a prime number.
The prime number is included. Its only nonzero residue class is one: every odd integer satisfies . Every integer also satisfies , because is even. Testing the first formulation with an even integer would violate its hypothesis.
The useful surprise is that every nonzero residue class returns to one at the same exponent , although its shortest return can be earlier. This gives exponent reduction for units: for a nonnegative integer , when . It also computes a modular multiplicative inverse as modulo , including . Repeated squaring makes these modular exponentiations practical.
In group theory, the nonzero residue classes form the multiplicative group of integers modulo n with , of group order . Lagrange's theorem says that the multiplicative order of divides , giving the guaranteed return. Euler's theorem extends this to a general integer modulus , using the units and Euler's totient function ; the Carmichael function gives the least common return exponent for all units. A nonzero residue class modulo a composite number need not be a unit.
Leonhard Euler's paper presented in 1732 and published in 1738 states a historical formulation: Theorem 1 says that powers with exponent leave zero or one upon division by a prime number . The preceding discussion states the difference-of-powers version and explicitly says that he does not have its proof.[ref]
Fermat number Created 2026-10-07 Updated 2026-10-13
A Fermat number is the positive integer , indexed by a nonnegative integer . The first five are , all prime numbers; the next is the composite number . This family offers a compact lesson in number theory: a very persuasive finite pattern can fail, while an exact divisibility relation settles a gigantic case with little computation.
Figure 1.
Exact Fermat numbers: five initial primes, a composite sixth term, and rapidly increasing decimal lengths
. Details.
Why does the exponent itself have the form ? Suppose is a positive integer with an odd integer factor . The polynomial factorization shows that is a proper divisor of . Consequently, if is a prime number, must be a power of two. That is a necessary condition, rather than a promise that the surviving candidates are prime.
The Fermat number product identity makes distinct Fermat numbers coprime integers. Thus every term has a prime factor absent from all earlier terms, whether or not that term is itself a prime number. This gives an explicit route to infinitely many different prime numbers, without establishing that infinitely many terms of this particular sequence are prime. Meanwhile the prime divisor of a Fermat number criterion filters possible factors through a small multiplicative order calculation.
The family also links arithmetic to Euclidean geometry: a constructible regular polygon can have a number of sides equal to a power of two times a product of distinct Fermat primes. The Gauss-Wantzel theorem gives the precise criterion. For instance, and qualify, but does not. The word "distinct" matters. Carl Pomerance describes this connection in Primality testing: then and now by Carl Pomerance (slide 18).
Historically, Leonhard Euler records Pierre de Fermat's proposed primality pattern, then refutes it by finding the factor of . His paper was presented in 1732 and published in 1738; those are different events, not competing dates for one publication.[ref]
A short modern check needs only two representations of :
In modular arithmetic these give and . Substitution yields , so . This verifies the factor directly; it does not claim to reconstruct Euler's search process.
Fermat test example 2026-10-14
For the Fermat primality test, a passing base satisfies . Passing proves only this modular congruence, not that is a prime number. An odd composite number that passes a coprime base is a Fermat pseudoprime to that base. A Carmichael number passes every coprime base, so even testing all the units would not certify that is a prime number. [ref]
This small table uses only the bases , each reduced modulo first. A numeric entry is : one passes, while any other numeric entry gives a Fermat witness. A "factor" entry records a proper greatest common divisor and stops before modular exponentiation. The prime/composite classification is independently established by trial division or the displayed prime factorization, not by the passing entries. These four bases are illustrative, with no asserted universal coverage or error probability.
Table 1.
Finite-base Fermat primality test examples with explicit greatest common divisor checks
.
Independent classification
2Prime numberZero residue: excluded111
7Prime number1111
15: composite number4Factor 3Factor 51
341: composite number15667Factor 11
561: composite number1Factor 31Factor 11
For , and , so . Yet and , so three is a Fermat witness. One coprime base passes and another fails: being a Fermat pseudoprime depends on the base. Choosing eleven instead reveals the proper factor through .
For , every coprime base passes: each of divides , so Fermat's little theorem gives modulo each prime factor; the Chinese remainder theorem combines the three modular congruences. Equivalently, the Carmichael function gives . Bases two and five have greatest common divisor one and pass, but , and expose factors. The qualification "coprime" is therefore crucial even for a Carmichael number.
The Fermat primality test is useful because a Fermat witness can prove compositeness using repeated squaring without finding a factor. Its failure to certify a passing candidate motivates stronger primality testing methods such as the Miller-Rabin primality test.
Fermat witness 2026-10-14
A Fermat witness for an integer is a nonzero residue class represented by for which . It proves that is a composite number by Fermat's little theorem. Here the definition includes nonunits; some conventions restrict Fermat witnesses to bases coprime to . The Fermat primality test can first compute the greatest common divisor: if , it already has a proper factor. A zero residue class is excluded. [ref]
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 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.