Why Are Finite Field Sizes Always Prime Powers?

[ych22]

Hi, I am taking a class in Linear Algebra II as a breadth requirement. I have not studied Algebra in a formal class, unlike 95% of the rest of the class (math majors). My LA2 professor mentioned the following fact in class:

"The number of elements of a finite field is always a prime power and conversely, every prime power occurs as the number of elements in some finite field (which is unique up to isomorphism)."

The exact words are Wikipedia's but that's about what the Prof said.

I only vaguely understand the concept of rings, fields and groups. I cannot understand why the number of elements in a finite field is a power of primes.

 

[ych22]

BTW, I am seeking an intuitive explanation to understand "why the number of elements in a finite field is a power of primes".

 

[Outlined]

Look at the ring Z/nZ, this is a field <=> n is prime

This is easy to see, is n is not a prime then n = km for n, m > 1 so k nor m are invertible in Z/nZ. So Z/nZ is not a field.

On the other hand if n is prime then the equation an + bk = 1 always has a solution for a and b so k is invertible in Z/nZ. So Z/nZ is a field.

 

[Spartan Math]

Outlined only partially answers the question. Of course the rings Z/pZ are finite fields, but they are not the only fields. Perhaps the easiest (and perhaps most intuitive way) to explain this is to use elementary concepts from linear algebra.

Let K be any field and consider the map from the integers to K that sends an integer n to n*1, where "1" is the identity element in K. Now this map happens to be a ring homomorphism (if you don't know what a ring homomorphism is, think of it as a linear transformation that also preserves the identity and ring multiplication) with kernel that is generated by some nonnegative integer m (since EVERY ideal in the integers is principal). Then recall that Z/mZ embeds into K. Now since K is a field, it is of course an integral domain (that is, it has no zero divisors) thus every subring must be an integral domain, hence Z/mZ must be an integral domain, so that m must be prime, thus K contains Z/pZ for some prime p.

Okay, so that above argument is mostly technical and if you didn't know a lot of the words, they're easily googled or looked up in any standard text on abstract algebra.

Onto the part involving linear algebra. So now that we have that K contains Z/pZ, we know that K is a vector space over Z/pZ and thus must be finite dimensional, so let (x_i) for i = 1,...,r be a basis for K over Z/pZ and let (a_j) for j = 1,..,p be the elements of Z/pZ, then since the x_i are a basis for K, the Z/pZ-linear combinations of the x_i are equal if and only if their coefficients are equal, thus there are p^r possible linear combinations, hence K has p^r elements.

I skimmed over some details in the above paragraph, but you should be able to get the general idea: Every finite field contains Z/pZ for some prime p and is a [finite-dimensional] vector space over Z/pZ and the basis elements determine the number of elements of K, which must be a prime power.

Also, there is simpler way to derive this conclusion, but it utilizes some concepts from field theory.

 

[Citan Uzuki]

I like the vector space explanation, and probably it is the most intuitive one. But there's another way to get this result that requires only basic group theory, which I'll outline below.

Let (F, +, ·) be a finite field and let x and y be any two nonzero elements. Let n be the order of x in the additive group (F, +) and m be the order of y in (F, +). Observe that ny = nx(x/y) = 0(x/y) = 0, so m|n. By the same logic, n|m. Hence m=n, and any two nonzero elements have the same order. Now, if that order is composite, say, pq, then px would have order q≠pq, and there would be nonzero elements of different orders, which we have already shown is impossible. Hence every element has the same prime order p. Now, if the order of F is not p^k for some k, then it has a distinct prime factor q, and so by Cauchy's theorem there is an element of order q≠p, which is a contradiction. Hence the order of F is a power of a prime.

 

[ych22]

I like the vector space explanation, and probably it is the most intuitive one. But there's another way to get this result that requires only basic group theory, which I'll outline below.

Let (F, +, ·) be a finite field and let x and y be any two nonzero elements. Let n be the order of x in the additive group (F, +) and m be the order of y in (F, +). Observe that ny = nx(x/y) = 0(x/y) = 0, so m|n. By the same logic, n|m. Hence m=n, and any two nonzero elements have the same order. Now, if that order is composite, say, pq, then px would have order q≠pq, and there would be nonzero elements of different orders, which we have already shown is impossible. Hence every element has the same prime order p. Now, if the order of F is not p^k for some k, then it has a distinct prime factor q, and so by Cauchy's theorem there is an element of order q≠p, which is a contradiction. Hence the order of F is a power of a prime.

Could someone explain "Observe that ny = nx(x/y) = 0(x/y) = 0, so m|n. By the same logic, n|m. Hence m=n, and any two nonzero elements have the same order." in more detail?

What does the notation m|n mean?

 

[Citan Uzuki]

Could someone explain "Observe that ny = nx(x/y) = 0(x/y) = 0, so m|n. By the same logic, n|m. Hence m=n, and any two nonzero elements have the same order." in more detail?

Gah, that's what I get for not proofreading my posts. It should be ny = nx(y/x) = 0(y/x) = 0.

Basically, I'm saying that if x and y are any two nonzero elements, then y is a multiple of x (since y=x(y/x)), so if x added to itself n times is 0 (i.e. if nx=0), then y added to itself n times must be a multiple of 0 and therefore is also 0. Hence the order of y must divide the order of x. The same logic applied in the opposite direction shows that the order of x divides the order of y.

What does the notation m|n mean?

It means that m divides n.

 

[ych22]

Gah, that's what I get for not proofreading my posts. It should be ny = nx(y/x) = 0(y/x) = 0.

Basically, I'm saying that if x and y are any two nonzero elements, then y is a multiple of x (since y=x(y/x)), so if x added to itself n times is 0 (i.e. if nx=0), then y added to itself n times must be a multiple of 0 and therefore is also 0. Hence the order of y must divide the order of x. The same logic applied in the opposite direction shows that the order of x divides the order of y.



It means that m divides n.

Thanks, for a moment I thought I was insane :S