The Legendre symbol being one means $a$ is nonzero and a square modulo $p$. Take one root $r\ne 0$. Factoring $x^2-r^2=(x-r)(x+r)$ in the field shows that any root is $r$ or $-r$. Since $p$ is odd these are distinct. Thus there are exactly $\boxed{2}$ solutions.

For $n\ge 1$, the zero residue contributes zero. Multiplication by any nonzero $\alpha$ permutes the nonzero residues, so the sum $S$ satisfies $S={\alpha }^{n}S$ in ${\mathbb{F}}_p$. If $p-1\nmid n$, choose a primitive root $\alpha$; then ${\alpha }^n\ne 1$, forcing $S=0$. If $p-1\mid n$, every nonzero term equals one, so $S=p-1=-1$ in the field.

The printed display also mentions $n=0$, although its introductory assumption is $n\ge 1$. For that extra case the sum of the $p$ integer values $x^0$ for $1\le x\le p$ is $p\equiv 0$, so that branch is consistent too. The result is

A primitive root modulo $p$ is a generator of the cyclic multiplicative group $(\mathbb{Z}/p\mathbb{Z}{)}^{\times }$, so it has order $p-1$. If $g$ is one generator, the generators are exactly $g^k$ with $\gcd (k,p-1)=1$. Hence there are $\boxed{\varphi (p-1)}$. For $p=2$ the group is trivial and its unique element is its generator, consistently with $\varphi (1)=1$.

There are $p^n$ choices for the translation. Choose the columns of an invertible matrix successively: the first is any nonzero column, the second avoids its span, and at stage $j+1$ one avoids a $j$-dimensional span of size $p^j$. ConsequentlyThe successive linear independence conditions are exactly the criterion that the columns form a basis.

Every pair factors as $(A,b)=(I,b)(A,0)$, and a linear map which is also a translation fixes zero and has linear part $I$, hence is the identity. Thus $G=NH$ and $N\cap H=\{1\}$. The conjugation formula in (c) says that the action needed for reconstruction is simply the usual matrix action $A:t\mapsto At$ on the additive group $F^n$. Therefore

The map $A\mapsto (A,0)$ is an injective group homomorphism, so its image is the required copy of ${\mathrm{GL}}_n(F)$. Translations are the subgroup $N=\{(I,b):b\in F^n\}$, isomorphic to the additive group of $F^n$. For any affine map,Thus conjugation preserves translations, proving $N⊴G$.

Compose the second map first. Direct substitution givesThe result is affine because the product matrix is invertible. The identity is $(I,0)$ and the inverse is $(A^{-1},-A^{-1}b)$. Associativity follows from composition of maps, or by expanding this product three times. Distinct pairs give distinct maps, since evaluating at zero gives $b$ and evaluating the difference on basis vectors gives all columns of $A$. Thus these pairs faithfully describe a group.

Given $N⊴G$ and $H\le G$, the conditions are $\boxed{G=NH,N\cap H=\{1\}}$. Every element then has a unique expression $nh$. The extra datum is the action $\alpha :H\to \mathrm{Aut}(N)$ given by conjugation, ${\alpha }_h(n)=hn{h}^{-1}$. On pairs $(n,h)$ the reconstructed multiplication isFor example $S_3=⟨(123)⟩⋊⟨(12)⟩$. The order-three subgroup is normal, the intersection is trivial, and their sizes multiply to six. Conjugation by $(12)$ inverts $(123)$, so the action is nontrivial. Consequently this is not the direct product of these subgroups: $C_3\times C_2$ is Abelian, whereas $S_3$ is not.

For $\alpha \ne 0$, Lagrange's theorem in the multiplicative group of order $q^m-1$ gives ${\alpha }^{q^m-1}=1$; at zero the desired identity is immediate. Thus all elements satisfy ${\alpha }^{q^m}-\alpha =0$.

For an irreducible degree-$m$ polynomial $f\in F[X]$, the quotient $L=F[X]/(f)$ is a field of dimension $m$, hence has $q^m$ elements by part 1. Its element $\alpha =[X]$ therefore satisfies ${\alpha }^{q^m}-\alpha =0$. The evaluation homomorphism $F[X]\to L$ has kernel $(f)$, so

By the allowed cyclicity theorem, $K^{\times }$ has a generator $z$. Every nonzero element of $K$ is a power of $z$, and zero also belongs to $F(z)$. Thus $K\subseteq F(z)\subseteq K$, giving $\boxed{K=F(z)}$. This is a primitive element argument for finite fields using the multiplicative group, not a claim that the additive group is cyclic.

Write $q=p^r$, where $p$ is the characteristic. In a splitting field of $X^{q^m}-X$ over $F$, let $K$ be its set of roots. The derivative of this polynomial is $-1$, so all $q^m$ roots are distinct. The Frobenius power is additive and multiplicative: $(x+y{)}^{q^m}=x^{q^m}+y^{q^m}$ and $(xy{)}^{q^m}=x^{q^m}{y}^{q^m}$. Thus roots are closed under addition, negatives and multiplication; for a nonzero root, $(x^{-1}{)}^{q^m}=x^{-1}$. They include $0,1$ and form a field.

Every $a\in F$ satisfies $a^q=a$, by Lagrange's theorem on $F^{\times }$ and separately at zero. Iterating gives $a^{q^m}=a$, so $F\subseteq K$. The constructed field therefore contains $F$ and has exactly $\boxed{q^m\text{ elements}}$.

Regard $K$ as a vector space over $F$. Since $K$ is finite, a maximal linearly independent list has finite length $d$ and is a basis. Every element is uniquely a linear combination of its $d$ basis vectors, with $q$ choices for each coefficient. Hence $\boxed{|K|=q^d}$, with $d=[K:F]$. This includes $d=1$ when the extension is trivial.

State-dependent execution times can bias the finite set of completed outputs. A simple counterexample takes $p=q$ uniform on two states and $M=1$, so every proposal is accepted. Suppose processing the first state takes one unit of time and processing the second takes two. Stop at a deadline between one and two units, discarding any unfinished computation. The only possible completed output is the first state; conditional on obtaining a sample, its law is concentrated there rather than uniform.

This demonstrates that a wall-clock cutoff can select outputs according to their processing cost, unlike the fixed proposal budget in (d). It does not imply a permanent asymptotic bias of averages over an indefinitely growing completed sequence: the finite-horizon stopping and censoring are the issue. Without assumptions relating runtime to states, exact finite-sample unbiasedness cannot be guaranteed.

A fixed proposal-count budget does not bias the accepted values. For each trial, acceptance has probability $a$, and conditional on acceptance its label has law $p$ independently of the other trials. Conditional on the full accept/reject pattern among the first $N^{\ast }$ proposals, the successful labels are independent with common law $p$. Therefore $K\sim \mathrm{Binomial}(N^{\ast },a)$, and conditional on $K=k$, the $k$ retained samples are independent draws from $p$. When $K=0$ there is simply no sample. This concerns a budget fixed independently of the proposal values; it does not assert that an empirical average is defined on an empty output.

Each $N_i$ is geometric on $\{1,2,\dots \}$ with success probability $a=Z_p/(M{Z}_q)$. HenceLinearity of expectation proves the estimator is unbiased. Moreover the joint probability factors:Thus $\boxed{N_i\text{ and }{X}_i\text{ are independent}}$, not merely uncorrelated. Fresh independent trials make the simulated cycles independent as well.