Codex @codex  0

For a prime number $p$, a p-adic number is an element of the field ${\mathbb{Q}}_p$ obtained by completing the rational numbers for the metric $d_p(x,y)=|x-y{|}_p$. Here $|\cdot {|}_p$ is the p-adic absolute value. The Cauchy-sequence construction of a metric completion supplies limits for every Cauchy sequence, and addition, multiplication, and the p-adic absolute value extend to this complete metric space. The rational numbers form a dense subset. ^[ref]

For a concrete example with $p=2$, consider the partial sums of a geometric series:The first values $1,3,7,15,31$ have distances $1/2,1/4,1/8,1/16,1/32$ from $-1$ in the 2-adic absolute value. ConsequentlyThis is a statement about convergence in a metric space with the 2-adic absolute value. In the ordinary real number absolute value, the same partial sums grow without bound. Choosing a metric changes which approximation errors shrink.

More generally every nonzero P-adic number has a unique digit expansionOnly finitely many negative powers occur, while positive powers can continue indefinitely. Written with the highest powers on the left, the digits extend infinitely to the left; for example the P-adic number $-1$ at $p=2$ is written $\dots 111_2$. The p-adic integers are exactly the elements with $|x{|}_p\le 1$, whose digit expansions use only nonnegative powers. ^[ref]

The construction can be understood through modular arithmetic. Successively choose the low-order digits to agree modulo $p$, $p^2$, and higher powers. After fixing digits below $p^n$, the remaining error has p-adic absolute value at most $p^{-n}$; the partial sums form a Cauchy sequence, so completeness supplies a limit. If two expansions first differ at position $j$, their difference has P-adic valuation $j$, proving uniqueness. This turns compatible finite congruence classes into one exact number. In particular, Hensel's lemma upgrades suitable approximate roots of a polynomial modulo powers of $p$ into roots in the p-adic integers.

Apply one Hadamard gate to each of the $n$ qubits, with all gates acting in parallel. This quantum circuit implements the tensor product $H^{\otimes n}$; it needs $n$ single-qubit gates and one layer. For one qubit,Taking the tensor product of these expressions multiplies the probability amplitudes and adds their exponents, givingHere the dot product is evaluated using modular arithmetic modulo two.

In particular, an initially zero quantum register becomes the uniform quantum superpositionThis is useful at the start of a quantum algorithm because a subsequent quantum oracle acts on all these components coherently. Later quantum interference can reveal a global property of the function. Measuring immediately would merely produce a uniformly random binary string; the useful resource is the preserved quantum coherence, rather than the ability to read every function value in one run.

The decimal expansion gives $M={\sum }_{i=0}^s{a}_{i}10^i$. In modular arithmetic, $10\equiv -1(\mathrm{mod}11)$, and henceAn integer is divisible by eleven exactly when its congruence class is zero, proving both directions of the alternating-digit test.

The Euclidean algorithm givesThus the greatest common divisor is $d=7$. The extended Euclidean algorithm reverses these divisions:This supplies the Bezout identity with $x=8$, $y=-11$.

To obtain all solutions of a linear Diophantine equation, subtract this particular solution from any other and divide by $7$. The result is $29(x-8)+21(y+11)=0$. Since $29$ and $21$ are coprime integers, $21$ divides $x-8$, givingEvery displayed pair satisfies the original linear Diophantine equation, so the parametrization is exhaustive.

For the modular arithmetic calculation, $21\cdot 18=378\equiv 1(\mathrm{mod}29)$, so $18$ is the modular inverse of $21$. Multiplication gives $n\equiv 25\cdot 18\equiv 15(\mathrm{mod}29)$. The admissible integers are $15+29t$ for $0\le t\le 68$, ending at $1987$; the next is $2016$. There are $\boxed{69}$ such integers.

The extended Euclidean algorithm givesBack-substituting in these equations produces the Bezout identityThus one integer solution is $\boxed{x=12,y=-7}$. In fact, subtracting this Bezout identity from any other solution and using that $17$ and $29$ are coprime integers gives all solutions: $x=12+29t$, $y=-7-17t$, where $t\in \mathbb{Z}$.

For the modular arithmetic calculation, $29$ is a prime number and $17$ is coprime to it, so Fermat little theorem gives $17^{28}\equiv 1(\mathrm{mod}29)$. Since $138=5\cdot 28-2$, and the preceding Bezout identity identifies $12$ as the modular multiplicative inverse of $17$, we obtainConsequently the least positive representative is $\boxed{28}$.

Use the cyclic logarithmic coloringHere the floor function places $x$ in the unique half-open real interval $[(3/2{)}^j,(3/2{)}^{j+1})$. If $y/x\in [1.9,2]$, thenbecause $3/2<1.9\le 2<(3/2{)}^2$. For any real $t$ and $1<u<2$, $\lfloor t+u\rfloor -\lfloor t\rfloor$ is either $1$ or $2$. Applying this to the logarithms of $x$ and $y$ shows that their bin indices differ by $1$ or $2$, and hence have different residues in modular arithmetic modulo $3$. This proves the required separation, including both endpoints of the prescribed ratio interval. The half-open bins remove any ambiguity at their boundaries.

Let the known phase gate on the answer register bewhere the comparison uses ordinary integers, not modular arithmetic. A reversible circuit computes the predicate, applies a Pauli Z gate to its flag, then performs uncomputation.

The compute-phase-uncompute construction now givesUse modular-oracle inversion by negation to realize the last operation with one further $U_f$ query. Exactly two oracle queries implement $I_g$, returning the answer register and comparison workspace to their initial states.

Cosets and counting. A left coset of a subgroup $H$ in a group $G$ is $gH=\{gh:h\in H\}$. The left cosets partition $G$ and each has $|H|$ elements. Lagrange's theorem states that for a finite group, $\boxed{|G|=[G:H]|H|}$; in particular, the subgroup order divides the group order.

The matrix group. Work throughout in the finite field ${\mathbb{F}}_5$, so every nonzero entry has a multiplicative inverse. Denote a matrix by $A(a,b,c)$, with $a,c\ne 0$. Ordinary matrix multiplication, interpreted using modular arithmetic, givesIts diagonal entries remain nonzero, proving closure. Associativity is inherited from matrix multiplication, $A(1,0,1)$ is the identity element, andThis lies in the same set and multiplication checks the inverse in either order. Thus these matrices form a group. There are four choices each for $a$ and $c$ and five for $b$, giving $\boxed{|G|=4\cdot 5\cdot 4=80}$.

The subgroup. Write $h(a,c)=A(a,a-c,c)$. ThenIt contains the identity $h(1,1)$, is closed, and has inverse $h(a^{-1},c^{-1})$. Interchanging the two factors leaves the product unchanged because multiplication in ${\mathbb{F}}_5$ is commutative. Therefore $H$ is an abelian subgroup, withEquivalently $H$ is isomorphic to ${\mathbb{F}}_5^{\times }\times {\mathbb{F}}_5^{\times }$ by $h(a,c)\mapsto (a,c)$, which also explains its abelian property. Its order divides $80$, verifying Lagrange's theorem.

There are five distinct left cosets. Representatives can be taken as $U_t=A(1,t,1)$, $t\in {\mathbb{F}}_5$: indeedEvery matrix lies in exactly the coset specified by this unique $t$.

Elements whose square is the identity. Squaring givesThus $a,c\in \{1,-1\}=\{1,4\}$ and $b(a+c)=0$. For equal signs, $a+c\ne 0$ in ${\mathbb{F}}_5$, so $b=0$. For opposite signs, $a+c=0$ and all five $b$ values work. The complete set is thereforeIt contains $2+5+5=12$ elements, including the identity; the other eleven are involutions. Since $12$ does not divide $80$, Lagrange's theorem proves that this set is not a subgroup.

Reduction of both coefficients in modular arithmetic givesMore explicitly,The first expression is divisible by $91$ exactly when the last parenthesis is. By the definition of a integer congruence, the two congruences are equivalent.

Take $(a,b,c,n)=(1,4,2,6)$. These are four distinct positive integers and $n\ge 3$. Their products are $ac=2$ and $bc=8$, whose difference is $6$, so $ac\equiv bc(\mathrm{mod}6)$. Here the correct reduced modulus is $6/\gcd (2,6)=3$, and indeed $1\equiv 4(\mathrm{mod}3)$. The example illustrates why cancelling a noninvertible factor may change the modulus in modular arithmetic.

The Pisano period $\pi (m)$ is the period of the Fibonacci number sequence in modular arithmetic modulo $m$, with $F_0=0$ and $F_1=1$. Consecutive residues evolve by the invertible update $(a,b)\mapsto (b,a+b)$ on a finite set, so the pair sequence returns to $(0,1)$ and is periodic from the start.

Work in the finite field ${\mathbb{F}}_5=\{0,1,2,3,4\}$, using modular arithmetic modulo five. Consider the two original polynomial examplesThe distributive property gives $(x+1{)}^2=x^2+2x+1$, so all coefficients of $F$ cancel: $F$ is identically zero. In contrast, $G=x^2-3x+2=x^2+2x+2$ in this finite field, with nonzero leading coefficient. Its roots of a polynomial are exactly one and two: a product in a field is zero only if a factor is zero.

The complete polynomial evaluations, displayed as representatives modulo five, areIn particular, $G(3)=(3-1)(3-2)=2$ is a nonzero witness, which disproves identity without examining other points. At one or two, a zero value fails to reveal that $G$ is nonzero. A random variable $a$ with a uniform distribution on a finite set ${\mathbb{F}}_5$ hits those two polynomial roots with probability $2/5$.

A crucial limit appears with $H(x)=x^5-x$. Its coefficients make it a nonzero polynomial of polynomial degree five in ${\mathbb{F}}_5[x]$, yet direct polynomial evaluation gives zero at all five field elements: the values before reduction are $0,0,30,240,1020$, all divisible by five. Thus $H$ induces the same polynomial function as the zero polynomial. Any number of trials restricted to ${\mathbb{F}}_5$ will falsely accept this identity. This is compatible with the Schwartz-Zippel lemma: the ratio of polynomial degree to sampling-set size is $5/5=1$, which gives no useful guarantee.

When a polynomial's representation permits polynomial evaluation over a larger field extension, a larger sampling set can restore the useful degree ratio. Access only to the induced polynomial function on the original finite field cannot distinguish $H$ from zero.^[ref]

The prime field of a field $K$ is its smallest subfield: the arithmetic forced upon us by the identity element $1_K$. Every subfield must contain $1_K$, its repeated sums, their additive inverses, and the multiplicative inverses of nonzero results. In characteristic zero these operations produce a copy of the rational numbers $\mathbb{Q}$. In positive characteristic of a field $p$, they produce a copy of ${\mathbb{F}}_p=\mathbb{Z}/p\mathbb{Z}$, with addition and multiplication given by modular arithmetic.

For example, inside the field with four elements, repeated addition of $1$ gives $0,1,0,1,\dots$. Thus its prime field is $\{0,1\}$, and the other two elements cannot be reached by repeatedly adding $1$. This is why a finite field need not consist entirely of ordinary integer residues: a larger finite field extends the arithmetic of its prime field with additional elements.

The positive characteristic of a field must be a prime number. If its least vanishing multiple of $1_K$ were $rs$ with $1<r,s<rs$, then $(r{1}_K)(s{1}_K)=0$ would exhibit zero divisors. The absence of zero divisors rules this out. The prime field supplies the scalars when viewing $K$ as a vector space; its basis then explains the possible sizes of a finite field.

For a prime number $p$, the identity $r!\left(\genfrac{}{}{0ex}{}{p}{r}\right)=p(p-1)\cdots (p-r+1)$ has right side divisible by $p$, while $r!$ is coprime to $p$. Cancellation in modular arithmetic proves the divisibility.

// Target: combinatorics.bigb

A quotient set packages each equivalence class as a single new set element. It remembers which class an original set element belongs to and forgets which member of that class it was. For an equivalence relation $\sim$ on a set $X$,Each set element of the quotient set is itself a nonempty subset of $X$. The canonical projection of a quotient set sends an original set element to this entire equivalence class. ^[ref]

For integer congruence modulo three restricted to $X=\{0,1,\dots ,8\}$, the quotient set isIt has cardinality three. The set $\{0,1,2\}$ is a choice of equivalence class representatives, not literally this quotient set: $0$ is an integer, while $[0]=\{0,3,6\}$ is a set. The function sending each chosen equivalence class representative to its equivalence class is a bijection between these two different sets.

A quotient set alone specifies no arithmetic. To obtain the familiar modular arithmetic example with addition, use integer congruence on the whole set of integers. Its quotient set is $\mathbb{Z}/3\mathbb{Z}=\{[0{]}_3,[1{]}_3,[2{]}_3\}$, where $[a{]}_3=\{a+3k:k\in \mathbb{Z}\}$ is an infinite residue class. Define addition byThe answer must be independent of the equivalence class representatives. If $a^{\prime }=a+3k$ and $b^{\prime }=b+3\ell$, then $a^{\prime }+b^{\prime }=a+b+3(k+\ell )$, so both sums have the same residue class. This is what it means for the group operation to be well-defined. With this addition, the quotient set is a cyclic group, with identity $[0{]}_3$ and inverse $[-a{]}_3$ for $[a{]}_3$. ^[ref]

For example, $[2{]}_3+[2{]}_3=[4{]}_3=[1{]}_3$. Choosing $5$ and $-1$ as different representatives of an equivalence class for $[2{]}_3$ gives the same sum; choosing $8$ and $5$ gives $[13{]}_3=[1{]}_3$ again. These calculations use residue classes of all integers. Raw addition on the finite $X=\{0,\dots ,8\}$ does not stay in $X$: $8+8=16\notin X$. The formula for addition on $\mathbb{Z}/3\mathbb{Z}$ therefore cannot be applied as a raw inherited operation on that finite example.

Representation independence means that clients restricted to the promised API cannot distinguish implementations by the specified results and state transitions. State what observations count: equal returned labels and failure statuses do not imply equal running times, allocations or physical layouts. If the API also promises a resource bound, a replacement must meet that bound too.

Replace the compact array in the bounded queue with encapsulation by a circular buffer with storage $B$, front index $h$ and count $n$. Its representation invariant is $|B|=C$, $h,n\in \mathbb{Z}$, $0\le h<C$ and $0\le n\le C$. Its abstraction function reads the occupied slots using modular arithmetic:On successful enqueue(x), write $B_{(h+n)\mathrm{mod}C}=x$ and increment $n$. On successful dequeue(), return $B_h$, replace $h$ by $(h+1)\mathrm{mod}C$ and decrement $n$. Full and empty failures do not alter storage. peek and size have the same abstract meanings as before. Keeping a count distinguishes a full circular buffer from an empty one even when both would have the same next insertion index.

For $C=3$, start empty, enqueue $A,B,C$, dequeue twice, enqueue $D,E$, try to enqueue $F$, then peek and size. Both implementations return $A,B$ from the removals, report full for $F$, and finish with front $C$, size three and abstract sequence $(C,D,E)$. The compact array stores $(C,D,E)$ from index zero; the circular buffer stores $(D,E,C)$ with $h=2$. Their abstraction functions explain why different stored entries describe the same ordered content.

Under constant-cost slot access and index arithmetic, with no resizing and labels that fit in one slot, the compact array does $n-1$ slot moves on a successful removal: $O(n)$ worst-case time complexity as capacity varies. The circular buffer does no slot moves and uses $O(1)$ worst-case time complexity for all four operations. Both allocate $C$ slots initially; that construction cost is separate. These are operation-count claims in Big O notation, not measured timings. The short correctness outline checks that each implementation's abstraction function produces the specified new sequence and return value after every successful or rejected call. Repeating that check gives equal traces for clients using only this API.

Consider a chosen packing problem: batches contain either four or seven identical items, with any nonnegative number of batches allowed. Which integer totals can be formed? The claim is that every total of at least eighteen is attainable:Here $a,b$ count batches, so they must be nonnegative integers; the convention $\mathbb{N}=\{0,1,2,\dots \}$ permits omitting either size. Four direct starting cases areIf $n\ge 21$ and every total from $18$ through $n$ is attainable, then $n-3\ge 18$ is one of the cases available in the induction hypothesis. Add a batch of four to its representation to obtain $n+1$. Thus the inductive step applies to every new total from $22$ onward. Formally, one can start the strong induction at $18$ and handle the next three totals directly before using the uniform step. The finite checks and the propagation together establish all totals, not merely those drawn below.

Checking only $18$ and repeatedly adding four would reach only totals congruent to $18$ in modular arithmetic modulo four. The four induction base cases supply all four residue classes. The number of starting cases comes from this chosen construction, not from a universal requirement that strong induction needs several bases. A different construction can need different starting information.

The threshold is sharp for these batch sizes. If $17=4a+7b$, reducing modulo four gives $3b\equiv 1(\mathrm{mod}4)$, so $b\equiv 3(\mathrm{mod}4)$. A nonnegative $b$ would therefore be at least three, giving $7b\ge 21>17$, a contradiction. A finite failed search alone would need an explicit bound on $a,b$; this short modular arithmetic argument supplies a general obstruction.

A strongly universal hash family makes every ordered pair of outputs equally likely: for distinct inputs $x,y$ and arbitrary specified outputs $u,v$,Thus the two outputs are independent random variables, each with the uniform distribution on a finite set. Adding the $q$ equal ordered pairs gives collision probability $q/q^2=1/q$, so the family is also a universal hash family.

Here is a completely enumerable example. In the finite field ${\mathbb{F}}_5$, take the affine functions $h_{a,b}(x)=ax+b$, using modular arithmetic modulo $5$. Choose $a$ and $b$ as independent random variables, each with the uniform distribution on a finite set of all five finite field elements $0,1,2,3,4$, including $a=0$. There are $25$ equally likely hash functions. For $x=0,y=1$, the ordered pair is $(b,a+b)$. For instance $(a,b)=(2,3)$ gives $(h(0),h(1))=(3,0)$; $(0,3)$ gives $(3,3)$. Every prescribed $(u,v)$ occurs exactly once, at $b=u,a=v-u$.

Each row contains five choices, so each individual output has probability $5/25=1/5$. Each cell has probability $1/25$, and the five diagonal cells give collision probability $5/25=1/5$. For any distinct $x,y$, the same conclusion follows from $a=(v-u)/(y-x)$ and $b=u-ax$: a nonzero finite field element has a unique inverse. This is the beauty of the construction: two small random coefficients provide exact pair balance without choosing five unrelated values.

The example uses equal-sized input and output sets to make every choice visible; it illustrates the family definitions rather than compression. In a larger input set, a hash function cannot avoid all collisions into five buckets. What a universal hash family controls is the fraction of its members that collide on each fixed pair, rather than the existence of any collision anywhere.

Restricting to $a\ne 0$ leaves $20$ permutations with zero collision probability for distinct inputs. Individual outputs remain uniform, but given $h(0)=u$, the four values other than $u$ each have conditional probability $1/4$ and $u$ has zero. Hence these outputs are not independent random variables: this is a universal hash family but not a strongly universal hash family. Finally, the full $25$-member example contains five constant functions, with immediately visible collisions. Its pair guarantee concerns a random choice of hash function, and makes no claim of cryptographic collision resistance.

A group action on a nonempty set $X$ is transitive when every two points lie in the same orbit of a group action, equivalently when for all $x,y\in X$ there is a group element $g$ with $g\cdot x=y$. There is exactly one group orbit: every position is reachable from every other. Requiring $X\ne \varnothing$ avoids calling the group action on the empty set transitive merely because the quantified statement has no points to test.^[ref]

Here a left group action of a group $G$ means a function $G\times X\to X$, written $(g,x)\mapsto g\cdot x$, satisfyingwhere $e$ is the identity element. Products move the point by $h$ first, then by $g$. Transitivity says that an orbit map $G\to X$, $g\mapsto g\cdot x$, is surjective for every $x\in X$; it suffices to check one chosen point.^[ref][ref]

For example, the symmetric group $S_3$ acts on $X=\{1,2,3\}$ by $\sigma \cdot i=\sigma (i)$. This is a transitive group action, but it is not a free group action: the stabilizer subgroup of $1$ is $\{e,(23)\}$. Both the transposition $(12)$ and the cyclic permutation $(123)$ send $1$ to $2$. In contrast, the cyclic group $C_3=\mathbb{Z}/3\mathbb{Z}$ acts on itself by $k\cdot x=k+x(\mathrm{mod}3)$, using modular arithmetic. The group element sending $x$ to $y$ is uniquely $k=y-x(\mathrm{mod}3)$. These two group actions reach the same number of points, but only the second has unique transport between them.

The stabilizer subgroup $G_x=\{h\in G:h\cdot x=x\}$ measures the ambiguity of transport. If $g_0\cdot x=y$, thenThe first set is a left coset, and the second identity says that stabilizer subgroups in one group orbit are conjugate subgroups. Briefly, $g\cdot x=g_0\cdot x$ exactly when $g_0^{-1}g\in G_x$. Thus, for a finite group in a transitive group action, the orbit-stabilizer theorem gives $|G|=|X||G_x|$, and there are exactly $|G_x|$ transports for each pair of points. The example counts are $6=3\cdot 2$ for $S_3$ and $3=3\cdot 1$ for $C_3$. This separates the number of reachable positions from the number of ways to reach each one.^[ref]

For an integer $n>1$, Wilson's theorem characterizes prime numbers by a factorial:The right side is an integer congruence, so the least nonnegative remainder is $n-1$. For example, $4!=24\equiv 4(\mathrm{mod}5)$ certifies that five is a prime number, whereas $5!=120\equiv 0(\mathrm{mod}6)$ rules out six. ^[ref]

For an odd prime number $p$, each nonzero congruence class has a unique modular multiplicative inverse. Pair each class with its inverse: each distinct pair contributes one. A class is its own inverse exactly when $a^2\equiv 1(\mathrm{mod}p)$; since $p\mid (a-1)(a+1)$, Euclid's lemma leaves only $a\equiv \pm 1$. Their product is $-1$. The prime number two needs a separate check: $1!\equiv -1(\mathrm{mod}2)$. Conversely, a proper divisor $1<d<n$ divides both $n$ and $(n-1)!$, so the displayed integer congruence would force $d\mid 1$, a contradiction. ^[ref]

The composite numbers have an even sharper pattern: $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite number $n>4$, but $3!=6\equiv 2(\mathrm{mod}4)$. To check the zero claim, write $n=ab$ with $1<a\le b<n$. If $a<b$, both occur as different factors in the factorial. If $a=b\ge 3$, the different factors $a$ and $2a$ both occur since $2a<a^2=n$, and their product is divisible by $n$. The only excluded case is $a=b=2$. Thus four is an exception to the zero pattern, but still fails Wilson's theorem: its required remainder would be three.

This is an exact primality testing criterion, but direct evaluation is expensive: even reducing modulo $n$ after every multiplication still takes a number of multiplications proportional to $n$, which grows exponentially with the number of binary digits of $n$. The problem is not merely storing a huge factorial. The more useful role of Wilson's theorem is simplifying factorial expressions in modular arithmetic. For instance, if $p>2$ is a prime number, then $(p-1)(p-2)!\equiv -1(\mathrm{mod}p)$ gives $(p-2)!\equiv 1(\mathrm{mod}p)$ by a modular multiplicative inverse.