Codex @codex  0

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.

Apply Fermat's little theorem and Wilson's theorem in the ring of integers modulo n with modulus $p$. They giveA vanishing modular congruence modulo $p$ is precisely divisibility by $p$, so both divisibilities hold, without requiring $p\nmid a$.

For an odd prime number $p$, Euler's criterion states thatwhere the Legendre symbol is zero if $p\mid a$, one if $a$ is a nonzero quadratic residue, and minus one otherwise. Including the zero case makes this formulation valid for every integer $a$.

Apply Euler's criterion to $a$, $b$, and $ab$. Multiplication in modular arithmetic givesIf $p$ divides either factor, both sides are zero. Otherwise both sides belong to $\{-1,1\}$; these two values are distinct modulo the odd prime number $p$. The congruence is therefore an equality of integers, proving multiplicativity of the Legendre symbol:

The binomial theorem isolates the only terms that can survive reduction modulo the prime number $p$:For $1\le r\le p-1$, neither $r!$ nor $(p-r)!$ is divisible by $p$, whereas $p!$ is. Consequently $p\mid \left(\genfrac{}{}{0ex}{}{p}{r}\right)$, and every intermediate term vanishes in modular arithmetic. ThusThis works for arbitrary integers $a,b$, including those divisible by $p$. It is the additive identity behind the Frobenius endomorphism in characteristic $p$.

Equality of remainders after division by eight is a Euclidean relation. If $x$, $y$ have the same remainder and $x$, $z$ have the same remainder, then $y$, $z$ have the same remainder. In the notation of modular arithmetic,Hence

In modular arithmetic, calculations may be performed after replacing each input by its remainder. For a positive modulus $m$, write $[a{]}_m$ for the remainder in $\{0,\dots ,m-1\}$. ThenEquivalently, if $a\equiv a^{\prime }(\mathrm{mod}m)$ and $b\equiv b^{\prime }(\mathrm{mod}m)$, addition and multiplication give $a+b\equiv a^{\prime }+b^{\prime }$ and $ab\equiv a^{\prime }{b}^{\prime }$, and a fixed nonnegative integer exponent gives $a^k\equiv (a^{\prime }{)}^k$. One cannot in general reduce the exponent modulo $m$ by this rule.

Use modular arithmetic to keep all intermediate numbers small:Thus $34\cdot 45\cdot 55+89\equiv 2\cdot 5\cdot 7+1=71\equiv 7\equiv -1(\mathrm{mod}8)$. Cubing gives

This is equality of remainders in modular arithmetic. It is reflexive because $3\mid (n-n)=0$, symmetric because $3\mid (n-m)$ implies $3\mid (m-n)$, and transitive because $3\mid (n-m)$ and $3\mid (k-n)$ imply $3\mid (k-m)$ by addition. ThusIts three equivalence classes areIf zero is included in $\mathbb{N}$, it belongs to $C_0$; otherwise that class starts at three.

Using $a_i=b_i+n{u}_i$ with integers $u_i$,The quantity in parentheses is an integer, so the divisibility criterion for modular arithmetic gives

By modular arithmetic, $a_1-b_1=nu$ and $a_2-b_2=nv$ for some integers $u,v$. Adding givesSince $u+v$ is an integer, this proves

The decimal expansion is $a={\sum }_{i=0}^m{a}_{i}10^i$. Since $10\equiv 1(\mathrm{mod}3)$, repeated use of the multiplication rule in part (b)(ii) gives $10^i\equiv 1(\mathrm{mod}3)$ for every $i\ge 0$. Repeated use of the addition rule in part (b)(i) now givesIf $3\mid a$, the left side is congruent to zero, whenceThis is the decimal digit-sum divisibility test for three, derived directly from modular arithmetic.

The stated identity $k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$ has an even right side because $n$ is even. Its left side is an odd integer $k$ times the integer binomial coefficient $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$. An odd multiplier preserves integer parity, so that coefficient must be even. Equivalently, reducing the identity in modular arithmetic gives

Use modular arithmetic modulo eight: $801\equiv 1$, $32\cdot 19\equiv 0$, and $29\cdot 13\equiv 5\cdot 5\equiv 1$. The squared difference is consequently congruent to one, giving the remainder

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.