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 , equivalently
Thus 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 .
Prime-valued sum 2026-10-20
A sum whose resulting value is a prime number. This is a condition on the value, rather than a requirement that the summation index run over prime numbers. Counting subsets with a prime-valued sum can use subset sum counts followed by a primality filter on the possible totals.
Primitive binary quadratic form Created 2026-09-24 Updated 2026-11-05
An integral binary quadratic form is primitive when . This condition concerns its polynomial coefficients, rather than the values of a particular representing pair. For example, is primitive, while has a common divisor two and represents only even integers.
Primitivity is invariant under proper equivalence. Expanding an integer change of variables expresses every new polynomial coefficient as an integer linear combination of the old ones, so every common divisor of the old coefficients divides the new ones. The integer inverse gives the converse. Their greatest common divisor, called the content, is therefore unchanged.
A primitive representation separately means in . Even a primitive form can have nonprimitive representations: for . A representation of a prime number, however, must use a coprime pair, since a common divisor would force to divide that prime. This observation drives the discriminant criterion for prime representation by a binary quadratic form.
Primitive-root modulus classification Created 2026-09-24 Updated 2026-11-05
With the one-element unit group convention at , a positive integer modulus admits a primitive root exactly when
where is an odd prime and .
For existence, the finite subgroup of a field multiplicative group is cyclic theorem supplies a primitive root modulo . At least one of and satisfies the primitive-root lifting criterion: if , then
Thus lifting a primitive root to odd prime powers gives every . The Chinese remainder theorem for unit groups identifies with because is trivial. The moduli two and four are checked directly.
For exclusion, a cyclic group has at most two solutions of . If a modulus has two distinct odd prime factors, or is divisible by both four and an odd prime number, independent sign choices under the Chinese remainder theorem give at least four such units. A pure power with also has the four distinct roots and . These cover every omitted case.
When a primitive root exists, their number is . If generates the unit group of size , its power has multiplicative order , so exactly the coprime exponent classes generate. Here is Euler's totient function.
Primorial Created 2026-09-24 Updated 2026-11-05
The primorial up to a real bound is the product of all prime numbers not exceeding :
For example, , while . Each prime factor occurs once, so a primorial is a squarefree integer. It stays constant between successive primes, and for by the empty product convention.
Its natural logarithm is the Chebyshev theta function, . This converts multiplicative bounds on primorials into additive estimates over primes. In particular, the elementary primorial bound gives for .
p-valuation 2026-10-03
For a prime number , a p-valuation is a separated filtration on a group such that every satisfies
A group equipped with one is called a p-valued group.
Quadratic reciprocity Created 2026-09-24 Updated 2026-10-13
Quadratic reciprocity compares two questions: is the prime number a quadratic residue modulo , and is a quadratic residue modulo ? Let be distinct odd primes. In terms of the Legendre symbol,
The two Legendre symbols have opposite signs exactly when both primes are modulo ; otherwise they are equal. Their values are nonzero because the primes are distinct. Equal signs can mean two quadratic residues or two quadratic nonresidues: reciprocity compares the answers rather than declaring either answer positive.[ref]
For a direct computation, the nonzero quadratic residues modulo are respectively , , and . Squaring just suffices because and have the same square modulo an odd prime .
The pair has a sign flip, whereas has two negative signs. These small quadratic residue tables make the distinction tangible.
Figure 1.
Small prime square-residue tables distinguish opposite and equal Legendre symbol signs
. Each row uses half the nonzero inputs; the missing entries are unnecessary. The comparisons and are exact finite examples of quadratic reciprocity, not evidence by themselves for every prime pair. Details.
The first supplementary law for quadratic reciprocity handles numerator , and the second supplementary law for quadratic reciprocity handles numerator :
For an odd prime , is a quadratic residue exactly when , while is a quadratic residue exactly when . The remaining odd congruence classes modulo , namely , make a quadratic nonresidue. These laws fill the cases excluded from swapping distinct odd primes.[ref]
Quadratic residue Created 2026-09-24 Updated 2026-10-18
For an odd prime , a nonzero congruence class is a quadratic residue when for some integer . Here "quadratic residue" excludes zero: zero is a square of a number, but is neither a quadratic residue nor a quadratic nonresidue under this convention. Some treatments include zero among quadratic residues; the distinction matters when counting them or discussing their subgroup.[ref]
Modulo seven, squaring the six nonzero congruence classes gives
Thus the set of quadratic residues is , and the quadratic nonresidues are . In particular, has exactly the two solutions : and . Modulo eleven the quadratic residues are instead . Two is therefore a quadratic residue modulo seven and a quadratic nonresidue modulo eleven: being a quadratic residue depends on the modulus.
Figure 1.
The square map modulo seven and eleven: two inputs in every nonzero square fiber
. Each pair maps to one quadratic residue. The six nonzero inputs modulo seven give three outputs; the ten modulo eleven give five. The zero fiber is the single input zero, and each quadratic nonresidue has an empty fiber. Details.
Why do the square roots come in pairs? If , the prime number divides , so it divides one factor: or . For nonzero these are distinct, because is an odd prime. Every nonempty nonzero fiber of a function of therefore contains exactly two inputs. Pairing the nonzero congruence classes gives exactly quadratic residues and quadratic nonresidues. Including zero gives different squares, with one rather than two square roots for zero.
The quadratic residues form a subgroup of the multiplicative group of a finite field , with index of a subgroup two. Indeed, one is a square, , and ; the inverses exist because the inputs are nonzero in the prime field. Equivalently, the squaring group homomorphism has kernel of a group homomorphism and image of a function . The apparent loss of a sign in squaring becomes a precise division of the nonzero arithmetic into two equal parts.
This structure turns a search for square roots into a yes-or-no test: Euler's criterion detects quadratic residues through modular exponentiation, and the Legendre symbol records the result as a sign. For a general integer modulus, the modular congruence still makes sense, but the two-root count and the prime field argument need not survive. For example, has four solutions ; the Chinese remainder theorem separates the sign choices modulo three and five.
Rabin cryptosystem Created 2026-09-24 Updated 2026-11-05
The Rabin cryptosystem uses modular squaring with public modulus , where and are distinct odd prime numbers kept secret. The raw encryption map sends a message representative to
Knowing the prime factorization lets the receiver compute modular square roots modulo each prime and combine them by the Chinese remainder theorem. For a message coprime to , its ciphertext has exactly four roots modulo , corresponding to the two sign choices modulo each prime. A full encryption scheme therefore needs a specified message encoding or other rule to select the intended root; raw modular squaring by itself is four-to-one on the units.[ref]
For example, and give . Its four roots are modulo . The relation to integer factorization is especially direct: two roots that differ by more than an overall sign reveal a nontrivial factor through a greatest common divisor. The Rabin-Williams scheme is a more specific variant, rather than another name for every Rabin cryptosystem.
Rabin-Williams scheme 2026-11-05
The Rabin-Williams scheme is a family of modified Rabin cryptosystem constructions using a modulus with distinct prime numbers and . These congruences make sign and doubling adjustments useful for producing quadratic residues before taking modular square roots. In signature variants, the private integer factorization permits root extraction while the public verification uses squaring.
The arithmetic mechanism can be seen without fixing a full message encoding. For a unit modulo , exactly one of is a quadratic residue modulo both primes: the two signs change both Legendre symbols, while multiplication by changes only one of them. For the toy modulus and , the adjustment has square root , since .
A complete digital signature scheme must additionally specify message hashing or redundancy, the selected root, and how the adjustment is encoded and verified. The congruence calculation alone is not such a scheme. A specific modified-Rabin message-recovery construction is given in the primary handbook, rather than being identical to raw four-root Rabin encryption.[ref]
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 , then
Thus 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]
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: .
Figure 1.
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 is
To 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 , so
This 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 .
Recursively inseparable-set proof of Tennenbaum theorem Created 2026-09-28 Updated 2026-11-05
Let be disjoint computably enumerable recursively inseparable sets, represented by existential arithmetic formulas with bounded computation witnesses and . In a non-standard model of arithmetic , the assertion
holds at every standard bound . The overspill lemma gives a nonstandard bound where it still holds. This no-clash condition matters: an arbitrarily chosen nonstandard computation stage need not preserve the external disjointness of the two enumerations.
Inside , form the internally finite set and code it by the product of its corresponding prime numbers. Its standard trace contains and avoids , since the finite standard witnesses for either enumeration lie below . If the arithmetic operations of were computable, division by each standard prime would decide membership in this trace: search for and a standard remainder satisfying , where is the fixed code. The division algorithm in Peano arithmetic guarantees termination. This would give a computable set separating from , a contradiction.[ref]
At discriminant of a binary quadratic form , the reduced positive definite binary quadratic forms are exactly
The enumeration of reduced binary quadratic forms bound gives . For , the required odd and the divisibility leave precisely those two triples after the boundary sign convention. Both are primitive, so .
For a prime number , represents exactly when both Legendre symbols and are one; represents exactly when both are minus one. The square-completion identities
prove the necessary signs modulo five and seven: four is a square at both primes, whereas twelve is a quadratic nonresidue at both.
For sufficiency, either matching sign pair gives by quadratic reciprocity. The discriminant criterion for prime representation by a binary quadratic form then supplies a primitive form of discriminant representing . It reduces to one of the two listed forms, and their distinct sign conditions determine which. For example, , whereas .
Reduction modulo a prime in an integral matrix group Created 2026-09-28 Updated 2026-11-05
For a prime number , reducing every entry modulo defines a group homomorphism from an integral matrix group to the corresponding matrix group over . The target is finite. If an integral matrix is not the identity, choosing not to divide one nonzero entry of ensures that its reduction is also nonidentity.
Repdigit Created 2026-10-14 Updated 2026-10-20
A repdigit is a positive integer whose base- expansion repeats one nonzero digit . For , and , the finite geometric series gives . For example, has decimal digits, all equal to five.
Every prime number not dividing divides infinitely many such repdigits. If it divides , every length works. Otherwise, if it does not divide , the Fermat little theorem gives divisibility for lengths that are multiples of , and division by is justified by its modular inverse. If , the sum is congruent to modulo , so lengths divisible by work instead. A prime dividing but not divides none, since . This distinction prevents invalid cancellation of the geometric-sum denominator.
Ridout theorem Created 2026-09-24 Updated 2026-11-05
Let be an algebraic irrational number, let be a finite set of primes, and let . There are only finitely many reduced fractions whose denominator is S-smooth number and which satisfy
This is the denominator-restricted consequence of the finite-place Schmidt subspace theorem.
Riemann zeta function Created 2026-09-24 Updated 2026-11-05
The Riemann zeta function is initially defined by the Dirichlet series
Unique prime factorization gives its Euler product
Expanding each factor as a geometric series chooses an exponent for each prime number, so each positive integer appears exactly once. Absolute convergence justifies this rearrangement. This identity makes the Riemann zeta function a bridge between the distribution of prime numbers and complex analysis.
The function extends meromorphically to the complex plane, with its only pole at , simple with residue . For example, continuation gives even though the defining positive-term series diverges there. The functional equation of the Riemann zeta function relates values at and through the Riemann xi function.[ref]
For , its negative logarithmic derivative has coefficients given by the Von Mangoldt function. Perron's formula transfers analytic information about its zeros into estimates for prime-counting functions. The Riemann hypothesis specifies the location of its Nontrivial zeros of the Riemann zeta function.
Ring of integers of Q of pth root p Created 2026-10-03 Updated 2026-11-05
For a prime number and , the polynomial is Eisenstein at , and
The discriminant-index formula for an integral lattice reduces the proof to the prime . At the unique prime ideal above , one has and , which rules out an integral element with .
Rosser–Schoenfeld totient bound Created 2026-10-07 Updated 2026-11-05
For every integer , the Rosser–Schoenfeld totient bound states
where is Euler's totient function, is the Euler--Mascheroni constant and the logarithms are natural logarithms. The original theorem bounds above; its positive right side can be inverted to obtain this lower bound.[ref]
Thus the fraction of congruence classes modulo which are units is . It can be much larger: for a prime number it equals .
For a positive integer with , the Euler's totient product formula also gives : the product for omits some factors from the product for . A certified lower estimate for the ambient value therefore controls every divisor ratio, including , without evaluating at small values.
RSA cryptosystem Created 2026-09-24 Updated 2026-11-05
In the two-prime RSA cryptosystem, choose distinct odd prime numbers , set , and choose an integer coprime to . A private exponent satisfies . The public key is ; the private key permits the inverse modular exponentiation. For a message representative ,
Correctness holds even when is not coprime to : modulo each prime the zero case is immediate, while the nonzero case follows from Fermat's little theorem; the Chinese remainder theorem recombines the two congruences.
For example, , , and give ; encrypts to and decrypts back to . These tiny parameters only illustrate the arithmetic. The raw deterministic exponentiation is textbook RSA; practical encryption uses an encoding scheme rather than encrypting an unencoded message directly.[ref]