Consider the following constructive problem: Given prime $$$p$$$ and integer $$$k$$$, we need to construct operations $$$\oplus$$$ and $$$\otimes$$$ over the integers $$$0$$$ through $$$p^k-1$$$, such that for any $$$0\le x,y,z<p^k$$$, we have

1. $$$0\oplus x=x\oplus 0=x$$$ (additive identity)
2. $$$\exists r:a\oplus r=r\oplus a=0$$$ (additive inverse)
3. $$$1\otimes x=x\otimes 1=x$$$ (multiplicative identity)
4. $$$\exists r:a\otimes r=r\otimes a=1$$$ (multiplicative inverse)
5. $$$x\oplus y=y\oplus x$$$ (commutativity of addition)
6. $$$x\otimes y=y\otimes x$$$ (commutativity of multiplication)
7. $$$(x\oplus y)\oplus z=x\oplus(y\oplus z)$$$ (associativity of addition)
8. $$$(x\otimes y)\otimes z=x\otimes(y\otimes z)$$$ (associativity of multiplication)
9. $$$(x\oplus y)\otimes z=x\otimes z+y\otimes z$$$ (distributivity)

In other words, construct a field of size $$$p^k$$$.

The field $$$\mathbb Z_p$$$ are the integers modulo some prime $$$p$$$. How can we use this to construct a field of size $$$p^k$$$, where $$$k$$$ is some integer greater than $$$2$$$?

Consider some polynomial of degree $$$k$$$, $$$F(x)=a_0+a_1x+a_2x^2+\dots+a_{k-1}x^{k-1}+x^k$$$, such that $$$F(x)$$$ is irreducible modulo $$$p$$$, or that it has no nontrivial factors. What would happen if we introduce a new element $$$I$$$, that is defined to be a root of $$$F(x)$$$, much like how mathematicians introduced $$$i$$$ as a root of $$$x^2+1$$$?

By the definition of $$$I$$$, we must have that

or equivalently

Hence, we can create a new field where elements are of the form $$$v_0+v_1I+v_2I^2+\dots+v_{k-1}I^{k-1}$$$, where $$$0\le v_i<p$$$. Addition is done term-wise, and multiplication is equivalent to convolution. Note that if after a multiplication there $$$I^k,I^{k+1},\dots,I^{2k-2}$$$ terms are nonzero, we can reduce them using $$$I^k=(P-a_{k-1})I^{k-1}+\dots+(P-a_2)I^2+(P-a_1)I+(P-a_0)$$$.

The number of elements in this field is obviously $$$p^k$$$, but how do we verify that it indeed is a field, and that for reducible $$$F(x)$$$ the resulting elements do not form a field?

Observe, that we can treat all elements of this field as polynomials in the ring $$$Z_p[x]$$$ with highest nonzero term of degree at most $$$k-1$$$ during operations, keeping in mind to reduce after a multiplication. But we can do better — during multiplication, because $$$I^k$$$ becomes $$$(P-a_{k-1})I^{k-1}+\dots+(P-a_2)I^2+(P-a_1)I+(P-a_0)$$$, the polynomials are taken modulo $$$x^k-\left((P-a_{k-1})I^{k-1}+\dots+(P-a_2)I^2+(P-a_1)I+(P-a_0)\right)$$$, or equivalently, $$$F(x)$$$! Now all that's left is to prove that $$$Z_p[x]/F(x)$$$, or all elements of $$$Z_p[x]$$$ modulo $$$F(x)$$$, forms a field.

Associativity, commutativity, additive identities ($$$0$$$), multiplicative identities ($$$1$$$), additive inverses, and distributivity are all readily obvious. What's left is to prove that every nonzero element of $$$Z_p[x]/F(x)$$$ has an inverse. In $$$A(x)B(x)\equiv 1\pmod{F(x)}$$$, $$$B(x)$$$ exists if and only if $$$A(x)$$$ is coprime to $$$F(x)$$$, using an extension of the extended Euclidean algorithm to polynomials. Because $$$F(x)$$$ is irreducible, it has no factors other than $$$1$$$ less than itself, so every nonzero element of $$$Z_p[x]/F(x)$$$ is coprime to $$$F(x)$$$ — note that this doesn't hold when $$$F(x)$$$ isn't irreducible!

Hence, we have proven that $$$Z_p[x]/F(x)$$$ is a field, and equivalently, the field we have constructed out of elements of the form $$$v_0+v_1I+v_2I^2+\dots+v_{k-1}I^{k-1}$$$ is a field.

I saw this problem on multiple sources, one of which is chapter 10 of Introductory Combinatorics, but I felt like I made some semi-interesting insights that I was proud of and wanted to share it with Codeforces :)

Have a nice day!