A few days ago, I posted some proofs and a construction of finite fields. It turns out there are a lot more nice constructions and proofs and problems related to finite fields, so I’ll be sharing some of them here.
Theorem: Let be the number of monic irreducible polynomials in . Then
Consider the following zeta function.
There are only monic polynomials of degree so
Monic polynomials have a unique factorization into monic polynomial factors, after some computation, we can arrive at
where are the monic irreducible polynomials of . We can then compute the equality
Recall that . Substituting, we get
Let us examine the coefficient of of the LHS. We compute
We now construct finite fields in a different way.
Theorem: Any field has an algebraic closure and its closure is unique up to isomorphism.
Proof: This is actually a fun exercise and proofs of this result can be found almost everywhere.
Theorem: Let be the algebraic closure of . Let , where is a power of . Then is the unique field with elements contained in .
Proof: We first verify that is a field. Namely, and . clearly has elements because splits into distinct linear factors over and those factors are distinct (compute gcd with derivative).
Now let be some other subfield of with elements. is a group with elements so we have , and we can trivially extend this to for , so . But , so .
We can rephrase the above theorem as follows. is the splitting field of the polynomial over .
Theorem: Let be an arbitrary finite field with elements. Let be an irreducible polynomial of degree and let be one of its roots. Then is a field with elements.
Proof: This is a standard exercise with respect to field extensions.
Anyways, now for some problems.
Problem 1: (IMO Shortlist 1989) Suppose an integer sequence satisfies
for all . Prove that for all .
Solution: Let us compute the Möbius inversion. We get
Recall that elements of satisfy the polynomial . We count the number of elements of order precisely . Namely, we need to subtract off elements of orders with (can you see why?). We can do this with PIE, which is precisely the formula above. So is the number of elements in with order . Now consider the set of minimal polynomials of these elements. They must have degree , otherwise they would also belong in for some , and each of these polynomials has distinct roots in , so we are done.
Problem 2: (IMO Shortlist) Let , . If and , show that .
Solution: We first obtain a formual for . Check that
This means that , or . Set to obtain , so
Let be a prime factor of . Pick some in such that . Notice
so and . Define a map given by . This is a ring homomorphism. Let . are non-zero because . Additionally, . Now compute
Therefore and the order of MUST be (otherwise is impossible), so . Suppose . Then we know that so trivially . Now suppose not. Then are roots of irreducible . Raising the equality to the -th power, we get that . If , then is either or . If , then so we must have the latter, , which implies . But then, , so we trivially obtain .
Problem: (China TST 2008) Let . Let be an odd prime and be a prime divisor of . Prove that if , then .
Like, before, we can take in and define the ring homomorphism . Let and . We clearly have
Compute and using a similar trick in the previous problem, compute
so . Let us focus on the equality . If , then the order is either , , or . If the order is , then and , and squaring yields which is only true in , but . If the order is , then , so or . If , then forces ( is an odd prime). Similarly, if , then . If the order is , then , or , or or , both which eventually give the desired inequality. Notice that this only works if is not a quadratic residue mod . However, if is a quadratic residue mod , then we get either or , both of which yield the desired result.