Codex @codex  0

For a prime number $p$, the nonzero residue classes form the multiplicative group of the finite field ${\mathbb{F}}_p$. Every class has a unique multiplicative inverse. A class equals its own inverse precisely when $x^2=1$, so $(x-1)(x+1)=0$ in the field and $x=1$ or $x=-1$.

For an odd prime, pair each remaining class with its distinct inverse. Each pair contributes one to the product, leavingFor $p=2$, the same congruence is $1\equiv -1(\mathrm{mod}2)$. This proves Wilson's theorem.

If $p$ is a prime number and $p\nmid a$, multiplication by $a$ permutes the nonzero residue classes modulo $p$: $ai\equiv aj$ implies $i\equiv j$ because $a$ has a multiplicative inverse. Multiplying all the permuted classes givesThe factorial is a nonzero element of the finite field ${\mathbb{F}}_p$, so cancellation is valid. Thereforewhich is Fermat's little theorem.

Let $d$ be the multiplicative order of $a$ modulo $p$. Use Euclidean division to write $x=qd+r$, $0\le r<d$. Since $a^d\equiv 1$,If $a^x\equiv 1$, minimality of $d$ forces $r=0$, so $d$ divides $x$. Conversely, $d\mid x$ immediately gives $a^x\equiv 1$. For negative integers $x$, powers are interpreted using the multiplicative inverse and the same argument applies.

Apply the result to $x=p-1$, using Fermat's little theorem. Then $d\mid p-1$, equivalently

Lagrange theorem for polynomial congruences says that a nonzero polynomial of degree $d$ over a field has at most $d$ distinct roots of a polynomial. It follows by repeatedly factoring out $x-a$ at a root. Over the finite field ${\mathbb{F}}_p$, the only solutions of $x^2=1$ are $1$ and $-1$: these are distinct because $p$ is odd, and the root bound excludes any others.

Every nonzero element has a unique multiplicative inverse. Pair each element of ${\mathbb{F}}_p^{\times }$ with its inverse. All pairs of distinct elements contribute $1$ to the product; the only unpaired elements are $1$ and $-1$. Thus Wilson theorem follows:If Lagrange's theorem is formulated for finite groups, it states that the order of a subgroup divides the order of the group; in particular every element of ${\mathbb{F}}_p^{\times }$ has order dividing $p-1$. The inverse-pairing proof above establishes the required congruence directly.

The Fermat-Euler theorem states that for an integer $a$ and a positive integer $n$ with $\gcd (a,n)=1$,where the Euler totient function $\phi (n)$ counts the residue classes coprime to $n$. For $n\ge 2$, choose a reduced residue system $r_1,\dots ,r_{\phi (n)}$. Multiplication by the unit modulo n $a$ preserves coprimality and is injective on these residue classes: $a{r}_i\equiv a{r}_j(\mathrm{mod}n)$ implies $r_i\equiv r_j(\mathrm{mod}n)$, because $a$ has a multiplicative inverse modulo $n$. It therefore permutes the reduced residue system, givingThe product is also a unit modulo n, so it can be cancelled. This proves the Fermat-Euler theorem. For $n=1$ every modular congruence is automatic; one may use $\phi (1)=1$.

For a prime number $p$, the Euler totient function has value $\phi (p)=p-1$. Thus $a^{p-1}\equiv 1(\mathrm{mod}p)$ whenever $p\nmid a$. Multiplying by $a$, and treating $p\mid a$ separately, gives the all-integer version of Fermat's little theorem:Finally, Wilson theorem states that for every prime number $p$, $\boxed{(p-1)!\equiv -1(\mathrm{mod}p)}$. Its converse is also true: an integer $n>1$ is prime exactly when $(n-1)!\equiv -1(\mathrm{mod}n)$. For the converse, any proper divisor $1<d<n$ would divide both $(n-1)!$ and $n$, contradicting that congruence.

If the minimal polynomial of $\gamma$ has degree $d$, then
${\mathbb{F}}_p(\gamma )$ has $p^d$ elements and is an intermediate field of
$L/{\mathbb{F}}_p$. The tower law for field extensions givesso $d\mid n$.

The multiplicative group of a finite field is cyclic. Choose a generator
$\gamma$ of $L^{\times }$, of order $p^n-1$. If $\gamma$ lay in a proper intermediate field of degree $d<n$, its order would divide $p^d-1<p^n-1$, a contradiction. Thus
${\mathbb{F}}_p(\gamma )=L$ and its minimal polynomial has degree $n$.

For arbitrary $r\ge 1$, let $E$ be the splitting field of
$X^{p^r}-X$ over ${\mathbb{F}}_p$. Its roots form a field: the Frobenius endomorphism shows they are closed under addition, subtraction, multiplication, and inversion. The derivative is $-1$, so there are exactly $p^r$ distinct roots. Thus this root field has order $p^r$. Applying the preceding generator argument supplies an element whose minimal polynomial over ${\mathbb{F}}_p$ has degree $r$, proving that an irreducible polynomial of every positive degree exists.

Wilson's theorem states that an integer $n>1$ is prime if and only if $(n-1)!\equiv -1(\mathrm{mod}n)$. For a prime $p$, every nonzero residue has a multiplicative inverse. Pair each residue with its inverse; the only self-inverse ones satisfy $(a-1)(a+1)=0$ in ${\mathbb{F}}_p$ and hence are $1,-1$ (the same residue when $p=2$). The resulting product is $-1$. Conversely, if $(n-1)!\equiv -1(\mathrm{mod}n)$, no divisor $d$ of $n$ can satisfy $1<d<n$: it would divide both $(n-1)!$ and $n$, so could not divide $(n-1)!+1$. Hence $n$ is prime.

For a composite $n\ge 6$ which is not the square of a prime, choose a proper factorization $n=ab$ with $1<a<b<n$ if possible. Both factors occur in $(n-1)!$, proving divisibility by $n$. If the initially chosen factors coincide but their common value is composite, choose a different proper divisor to obtain unequal factors; equivalently, the only composite integer all of whose proper nontrivial divisors coincide is a prime square. For $n=p^2\ge 9$, the distinct factors $p$ and $2p$ lie below $p^2$ and their product is divisible by $p^2$. Thus $(n-1)!\equiv 0(\mathrm{mod}n)$ for every composite $n\ge 6$.

For a prime $n$, write $(n-1)!=kn-1$. Then ${\sin }^2((n-1)!\pi /n)={\sin }^2(\pi /n)$, so the summand is one. For a composite $n\ge 6$ it is zero. The only remaining composite index is four, whose summand equals ${\sin }^2(3\pi /2)/{\sin }^2(\pi /4)=2$. Therefore the sum is the prime-counting function plus two whenever $x\ge 4$; subtraction of two gives the claimed exact formula.

No such ring exists: every finite integral domain is a field. Here is the proof. For $a\ne 0$, the map $L_a:R\to R$ defined by $L_a(x)=ax$ is injective, since $ax=ay$ gives $a(x-y)=0$ and therefore $x=y$. An injective self-map of a finite set is surjective, so some $x$ satisfies $ax=1$. Since an integral domain is commutative, $xa=1$ as well. Thus every nonzero element has a multiplicative inverse, making $R$ a field.

The conclusion still holds if an identity was not initially required. Surjectivity first gives an element $e$ with $ae=a$. Then $a(ex-x)=0$ implies $ex=x$ for every $x$, and commutativity makes $e$ a two-sided identity. Applying the preceding argument with $e$ supplies all inverses.

Choose the representative $1\le a\le p-1$. Since $p$ is prime and does not divide $a$, their greatest common divisor is one. The extended Euclidean algorithm gives the Bezout identityfor some integers $x,y$. Reducing modulo $p$ gives $ax\equiv 1(\mathrm{mod}p)$, so the residue class of $x$ is a multiplicative inverse of $a$. The argument uses the nonzero condition to exclude the only residue with greatest common divisor $p$.

First prove $a^p\equiv a(\mathrm{mod}p)$ for every nonnegative integer $a$ by mathematical induction. The case $a=0$ is immediate. If it holds at $a$, the binomial theorem and the stated divisibility of the middle binomial coefficients giveThis establishes the induction. For an arbitrary integer $a$, take a nonnegative representative $r$ of its residue class; then $a^p\equiv r^p\equiv r\equiv a(\mathrm{mod}p)$. When $a\not\equiv 0(\mathrm{mod}p)$, part (b) supplies a multiplicative inverse modulo $p$. Multiplying the congruence by that inverse proves Fermat's little theorem:

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.

Consider the graph of a function $x\mapsto \sin (1/x)$, using the sine of the multiplicative inverse of $x$, together with a vertical closed interval:Give $T$ the subspace topology from the Euclidean plane. The symbol $\times$ denotes a Cartesian product. The right endpoint $(1,\sin 1)\approx (1,0.841471)$ belongs to $G$. The continuous map $x\mapsto (x,\sin (1/x))$ sends the connected real interval $(0,1]$ onto $G$. Hence $G$ is connected, and its closure $\overline{G}=T$ is connected by closure of a connected set. Every height in $[-1,1]$ is approached as $x$ tends to zero; for example,For $n=1$, these inputs are $p_1=2/(5\pi )\approx 0.127324$ and $q_1=2/(7\pi )\approx 0.090946$. For any other height $y\in [-1,1]$, choose $\theta \ge 1$ with $\sin \theta =y$; then the sequence $(1/(\theta +2\pi n),y)$ lies in $G$ and has limit of a sequence $(0,y)$.

Nevertheless, $T$ has exactly two path components, $G$ and $L$. Within $G$, join inputs $a,b\in (0,1]$ by the continuous path $t\mapsto ((1-t)a+tb,\sin (1/((1-t)a+tb)))$. Within $L$, use $t\mapsto (0,(1-t)c+td)$ for heights $c,d\in [-1,1]$.

The obstruction to a continuous path between $L$ and $G$ is persistent oscillation, not a visible gap. Proof outline: suppose such a path exists, directed from $L$ to $G$, and take its last time in $L$. Immediately afterwards its first coordinate $x(t)>0$ approaches zero and its second coordinate is $\sin (1/x(t))$. The intermediate value theorem forces the first coordinate to pass through inputs of both displayed types arbitrarily close to that departure time. The second coordinate therefore takes both values $1$ and $-1$ arbitrarily close to that time, contradicting continuity. ^[ref]

The sampled graph of a function illustrates the formulas; it does not prove connectedness or the failure of path connectedness. Taking a closure preserves connectedness, but this example shows that it can destroy path connectedness.

For positive real numbers $x_i$ and nonnegative weights with ${\sum }_i{w}_i=1$, the weighted geometric mean isIt takes a weighted mean of logarithms. A zero weight excludes that input; equal weights give the ordinary geometric mean. If $x_i$ occurs $m_i$ times in a list of total length $M$, its correct weight is $w_i=m_i/M$. For the list $(12,3,3,3)$,and replacing all four entries by $G_w$ preserves the product $324$.

There is also an optimization interpretation. A logarithmic transformation turns multiplicative discrepancies into additive ones. For a positive representative $c$, the weighted mean minimizes squared deviations identity givesThus $c=G_w$ uniquely minimizes weighted quadratic loss in logarithmic coordinates. The weighted arithmetic mean minimizes squared discrepancies in the original coordinates. These two objectives explain why different choices of what constitutes an error select different summaries.

The strictly concave function $\log x$ and the reversed Jensen's inequality give $G_w\le A_w$, where $A_w={\sum }_i{w}_i{x}_i$ is the weighted arithmetic mean. Apply the same reasoning to the multiplicative inverses to get $H_w\le G_w$ for the weighted harmonic mean. Thus $H_w\le G_w\le A_w$; equality holds exactly when all positive-weight inputs agree. For this list, $H_w=48/13$, $G_w=3\sqrt{2}$, and $A_w=21/4$. The weights specify which inputs are represented and must stay the same across the comparison.