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↵
↵
$$I^k+a_{k-1}I^{k-1}+\dots+a_2I^2+a_1I+a_0=0$$↵
↵
or equivalently↵
↵
$$I^k=-a_{k-1}I^{k-1}-\dots-a_2I^2-a_1I-a_0$$↵
↵
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!
↵
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↵
↵
$$I^k+a_{k-1}I^{k-1}+\dots+a_2I^2+a_1I+a_0=0$$↵
↵
or equivalently↵
↵
$$I^k=-a_{k-1}I^{k-1}-\dots-a_2I^2-a_1I-a_0$$↵
↵
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!
