Codex @codex  0

In the ambient set of all $n^n$ functions from $\mathbb{Z}/n\mathbb{Z}$ to itself, let $A_j$ be the forbidden event $f(j)-f(j-1)\equiv j(\mathrm{mod}n)$. Apply the avoidance form of the inclusion-exclusion principle from part (i).

For a proper subset $J$ of the $n$ cyclic difference constraints, with $|J|=k<n$, the selected edges form disjoint paths around the cycle, including isolated vertices. There are $n-k$ components. On each component, choosing one value of $f$ arbitrarily determines all the other values by the prescribed differences. No consistency condition occurs because the cycle has been broken. ThereforeThis also works for $n=2$, whose two directed constraints use the same pair of vertices: any single constraint leaves one freely chosen value.

If all $n$ constraints hold, summing them around the cycle gives the necessary conditionIt holds when $n$ is odd and fails when $n$ is even, the latter sum being congruent to $n/2$. When it holds, choose $f(0)$ in $n$ ways and determine every other value; the final constraint is then consistent. Thus the full intersection has size $F=n$ for odd $n$ and $F=0$ for even $n$.

There are $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ subsets of size $k$. By the binomial theorem,Hence the number of admissible functions is

For finite sets $A_1,\dots ,A_r$, the inclusion-exclusion principle statesTo prove it, count the contribution of one element. If it belongs to exactly $q\ge 1$ of the sets, it is counted by $\left(\genfrac{}{}{0ex}{}{q}{k}\right)$ intersections of size $k$. Its total weight isusing the binomial theorem. An element belonging to none contributes zero. Summing these weights gives the cardinality of the union and proves the inclusion-exclusion principle. Equivalently, within a finite ambient set $U$, the number avoiding every $A_i$ is the sum over all $J$, with sign $(-1{)}^{|J|}$ and the empty intersection interpreted as $U$.

Use uncountability by interleaving prescribed binary coordinates. For each arbitrary binary sequence $b=(b_k{)}_{k\ge 1}$, define another binary sequence byThere are infinitely many zero coordinates, namely $3k-2$, so $x\in X$. There are also infinitely many coordinates agreeing with the prescribed binary expansion, namely $3k-1$, so $x\in Y$. The coordinates $3k$ recover $b$, making this map an injection of the uncountable set of all binary sequences into $Y$. If $Y$ were a countable set, composing with an injection into $\mathbb{N}$ would make all binary sequences countable, contrary to part (i). Therefore $\boxed{Y\text{ is uncountable}.}$ The construction works for every prescribed binary sequence $(a_n)$; no special distribution property of the digits of $\sqrt{2}$ is needed.

Use $\mathbb{N}=\{1,2,\dots \}$. If a bijection $f:\mathbb{N}\to \mathbb{N}$ maps $S$ onto the even natural numbers, its restriction is a bijection from $S$ onto an infinite set. Moreover, its restriction to the complement of $S$ maps onto the odd natural numbers. Both sets are therefore infinite.

Conversely, suppose that $S$ and its complement are infinite. Applying the increasing enumeration of an infinite subset of natural numbers to each givesFor completeness, successively choose the least unused member. The process never stops because the set is infinite, and it lists every member: an omitted member would have infinitely many selected natural numbers below it, which is impossible. DefineThis is injective on each list, their images are disjoint, and together their images cover $\mathbb{N}$. Thus it is a bijection and maps $S$ onto $2\mathbb{N}$. Both infinitude conditions are necessary and sufficient. If a convention includes zero in $\mathbb{N}$, index each list from zero and use $2j$, $2j+1$ instead.

A set is a countable set if it admits an injective function into the natural numbers; this includes finite sets and countably infinite sets. A countably infinite set can be listed by a bijection from $\mathbb{N}$.

Let $Z$ be the set of infinite binary sequences. Suppose it were countable and list all its members as $s^{(1)},s^{(2)},\dots$, writing $s_n^{(j)}$ for the $n$th entry of row $j$. A finite listing could be repeated to make such a list as well. Define the binary sequence $y$ by $y_n=1-s_n^{(n)}$. It differs from the $n$th row in coordinate $n$, for every $n$. Thus it belongs to $Z$ but is missing from the list, a contradiction. The set $Z$ is uncountable, by Cantor's diagonal argument.

Fermat's little theorem reduces the exponent modulo $22$ because $23$ is a prime number and $5$ is coprime to it. Compute $5^2\equiv 3(\mathrm{mod}22)$, then $5^4\equiv 9(\mathrm{mod}22)$ and $5^5\equiv 45\equiv 1(\mathrm{mod}22)$. Thus $5^5=22k+1$ for an integer $k$, andThe exponent is $5^5=3125$, rather than an iterated left-associated power.

Suppose $x$ is a quadratic nonresidue. On the nonzero residue classes modulo $p$, define the involutionIt is an involution because $T(T(a))=a$. A fixed point would satisfy $a^2=x$, which is excluded by the quadratic nonresidue hypothesis. Thus it partitions the $p-1$ classes into $(p-1)/2$ disjoint pairs $\{a,x{a}^{-1}\}$, each with product $x$. ConsequentlyNow evaluate the same product by pairing every class with its own modular inverse. The only classes equal to their modular inverses solve $(a-1)(a+1)=0$ and hence are $1$ and $-1$. All other pairs have product one. The complete product is therefore $-1$, soTogether with the preceding part, this is Euler's criterion; the pairing argument establishes the converse without assuming it.

For the odd prime $p$, the Fermat-Euler theorem gives $x^{p-1}\equiv 1(\mathrm{mod}p)$. Therefore the residue class $z=x^{(p-1)/2}$ obeys $(z-1)(z+1)\equiv 0(\mathrm{mod}p)$. Since a prime number dividing a product divides one of its factors,If $x$ is a quadratic residue, choose $y$ with $y^2\equiv x(\mathrm{mod}p)$. Then $y$ is nonzero modulo $p$, and Fermat's little theorem givesThis proves the quadratic residue direction of Euler's criterion.

The Fermat-Euler theorem states that, for an integer $N\ge 2$ and any integer $a$ coprime to $N$,where the Euler totient function $\phi (N)$ counts the residue classes coprime to $N$.

Let $r_1,\dots ,r_{\phi (N)}$ be representatives of these residue classes. Multiplication by $a$ gives a permutation of them: each $a{r}_i$ remains coprime to $N$, and $a{r}_i\equiv a{r}_j$ implies $r_i\equiv r_j$ by cancellation using the modular inverse of $a$. Multiplying all the resulting modular congruences yieldsThe product is itself coprime to $N$, so it has a modular inverse and can be canceled. This proves the Fermat-Euler theorem. For $N=1$, the congruence is trivial; no separate argument is needed.

Close the truncated two-sheet double circular cone by the lateral circular cylinder $r=1$, $-1\le z\le 1$. Together these form the boundary of the solid in part (c); no planar caps are required because the cone meets the circular cylinder along both end circles. On the circular cylinder the outward unit normal is $(\cos \theta ,\sin \theta ,0)$, so $\mathbf{F}\cdot \mathbf{n}=1$, and $dS=d\theta dz$. Its flux integral isThe divergence theorem now gives ${\int }_S\mathbf{F}\cdot d\mathbf{S}+4\pi =4\pi$, using the volume integral from part (c). Henceagreeing with tangency. The isolated vertex can be handled by excising a ball of radius $\epsilon$ and passing to the limit: since $|\mathbf{F}|=O(\epsilon )$ there and the added area is $O({\epsilon }^2)$, its extra flux is $O({\epsilon }^3)$ and tends to zero.

In cylindrical coordinates $r=\sqrt{x^2+y^2}$, the bounded solid enclosed by the two conical sheets and the circular cylinder isIts meridional section consists of two triangular regions; revolving them about the $z$-axis gives the solid. The two conical sheets meet at the origin and meet the circular cylinder in its circles at $z=\pm 1$.

Since $\mathbf{F}=(x,y,z)$, its divergence is $3$. Integrate directly with the cylindrical coordinates volume element $rdzdrd\theta$:The same calculation gives $\mathrm{Vol}(V)=4\pi /3$.

At every regular point of the double circular cone, its normal is perpendicular to $\mathbf{F}$ by part (a). Therefore the integrand of the flux integral vanishes pointwise:The vertex, if included, is a single point of zero surface area and does not alter the surface integral. The answer is independent of both the subset and its orientation. Tangency, rather than a cancellation between different parts of the surface, explains the zero flux.

Away from the vertex, use the defining function $H=z^2-x^2-y^2$. Its gradient is normal to the smooth part of the double circular cone, andon the surface. Hence the field is tangent at every regular point of the cone. At the origin the cone has no unique tangent plane, but $\mathbf{F}(0)=0$, which belongs to its tangent cone. An equivalent argument, valid also at the vertex, uses the integral curves of a vector field: $\dot{\mathbf{x}}=\mathbf{x}$ has solution $\mathbf{x}(t)=e^t\mathbf{x}(0)$, and these dilations preserve $H=0$. This is an example of radial dilation tangency to homogeneous zero sets.

A subgroup $N$ is a normal subgroup of $G$ if $gN{g}^{-1}=N$ for every $g\in G$. Define multiplication on its left cosets byTo check that this is well-defined, replace $g,h$ by $g{n}_1,h{n}_2$ with $n_1,n_2\in N$. Thenbecause normality gives $h^{-1}{n}_{1}h\in N$. Thus the product depends only on the two cosets. Associativity follows from that of $G$, the identity is $N$, and the inverse of $gN$ is $g^{-1}N$. These are all the group axioms, so $G/N$ is a group under coset multiplication. The natural projection $g\mapsto gN$ is a surjective group homomorphism with kernel $N$.

The Möbius transformations are bijections, so they preserve which coordinates of a triple are equal. Conversely, part (i) implies transitivity within each equality pattern. For a pattern with fewer than three distinct entries, extend the chosen distinct points to a triple before applying part (i); this works also for $p=2$, when the projective line has exactly three points. There are therefore five orbits of a group action.

We first count $|G{L}_2({\mathbb{F}}_p)|$. Its first column can be any nonzero vector, giving $p^2-1$ choices. The second must be outside the first column's one-dimensional span, giving $p^2-p$ choices. HenceFor the all-equal pattern take $(\infty ,\infty ,\infty )$. Its stabilizer subgroup consists of upper triangular matricesof order $p(p-1{)}^2$. Its group orbit has order $p+1$.

The three exactly-two-equal patterns have representatives $(\infty ,\infty ,0)$, $(\infty ,0,\infty )$ and $(0,\infty ,\infty )$. Each stabilizer subgroup fixes $0$ and $\infty$ individually, so it is the diagonal subgroup of order $(p-1{)}^2$. Each group orbit has order $p(p+1)$; their repeated-coordinate positions keep these three orbits distinct.

For the all-distinct pattern use $(0,1,\infty )$. Its stabilizer subgroup is the scalar subgroup of order $p-1$, and the group orbit has order $(p+1)p(p-1)$. Stabilizers of arbitrary triples are conjugates of the displayed representative stabilizers. In summary the equality-pattern orbits of projective triples haveThe sizes add to $(p+1{)}^3$, and each orbit size times its stabilizer order is $|G|$, as in the orbit-stabilizer theorem.

Identify the projective line with one-dimensional subspaces of ${\mathbb{F}}_p^2$: use $v_t=(t,1{)}^T$ for finite $t$, and $v_{\infty }=(1,0{)}^T$. This convention turns the matrix action into the stipulated Möbius transformation.

Since $x$ and $z$ are distinct projective points, $v_z,v_x$ are a basis. Write $v_y=A{v}_z+B{v}_x$. Both $A$ and $B$ are nonzero, because $y$ is different from $x,z$. The matrix with columns $A{v}_z$ and $B{v}_x$ is invertible and sends the lines of $(1,0{)}^T,(0,1{)}^T,(1,1{)}^T$ to those of $z,x,y$, respectively. This constructs the requested map without separate exceptional formulas at infinity.

A matrix fixing $0$ and $\infty$ is diagonal, say $\mathrm{diag}(a,d)$ with $a,d\ne 0$. To fix $1$ it must also satisfy $a=d$, so the stabilizer subgroup of $(0,1,\infty )$ is precisely $\{\lambda I:\lambda \in {\mathbb{F}}_p^{\times }\}$. Any two solutions differ on the right by one of these matrices. ThusEquivalently, after dividing out scalar matrices the projective general linear group action on the projective line is sharply three-transitive on a projective line.

Write a matrix in the upper unitriangular group as $M=I+A$. Here $A^3=0$, and its only potentially nonzero entry in $A^2$ is $(A^2{)}_{13}=ab$. The binomial theorem therefore gives the unitriangular matrix power formulaFor an odd prime number $p$, both $p$ and $\left(\genfrac{}{}{0ex}{}{p}{2}\right)=p(p-1)/2$ vanish in the finite field ${\mathbb{F}}_p$. Thus $M^p=I$. A nonidentity $M$ has order dividing the prime $p$ (by the same exponent-division argument as in part (i)), and so has order exactly $p$.

For $p=2$, take $a=b=1$ and $x=0$. Then $M^2=I+A^2\ne I$, while $M^4=(I+A^2{)}^2=I$. This element has order $4$, not $2$. Hence every nonidentity element has order $p$ exactly for odd $p$. The counterexample at $p=2$ accounts for the quadratic term in the matrix power formula.