Thread: Why do finite fields or galois fields must have primenumber primenum power elements?

Why do galois field must have prime number or its powers as number of elements?
It would be helpful if the explanation is very simple ie verbal in nature. (I actually does not understand most of the math notations in algebra like Z/pZ.)
I am having engineering background (not that good in algebra). Here I require groups and fields for coding theory.

-Devanand T

Hi, dexterdev. There are two nice proofs of what you're talking about at Finite field - Wikipedia, the free encyclopedia in the section "Detailed proof of the classification." If you're trying to avoid things like Z/pZ and vector space, maybe you'll find the second argument more appealing. For the second proof you need to be familiar with Cauchy's Theorem: it says that if A is a finite group and p is a prime divisor of the order of A, then A has an element of order p.

Don't be afraid of the notations and things you don't know in algebra. If you really want to understand, you look it over enough and are willing to ask questions, you will get it.

Take a look at the arguments and feel free to ask any follow up questions. Good luck!

every field has a multiplicative identity, 1.

since a field is closed under addition, we can keep adding 1's:

1
1+1
1+1+1
1+1+1+1, etc.

now 1 is not allowed to be the same as 0. but that doesn't stop one of these other sums from perhaps being 0.

since the number of possible sums of 1 is FINITE, in a finite field, two of them at some point have to be the same: say k*1 = m*1 (where k*1 is shorthand for 1+1+...+1 (k times)).

note k and m are just plain old integers. since they are different, by assumption, we can pick k to be the larger one, and we have:

(k - m)*1 = 0. where k - m is some positive integer. so we know for sure in ANY finite field that there does exist some integer (call it n for now), with 1+1+...+1 = 0 (n 1's).

since we have at least one positive integer, we can speak of the smallest such positive integer with this property (any set of positive integers has a smallest element).

that number (the smallest positive number n with 1+1+...+1 (n times) equal to 0) is called the characteristic of a finite field.

so, every finite field has a positive characteristic. we can actually say more: the characteristic of a finite field must be prime.

for suppose not: suppose char(F) = n = km, where 1 < k,m < n.

then (k*1)(m*1) = (km)*1 = n*1 = 0. i claim this means that k*1 cannot have a multiplicative inverse, even though it is non-zero:

supoose it did, call it u:

then u(k*1) = 1, so

(u)(k*1)(m*1) = (1)(m*1)

(u)(0) = m*1

0 = m*1, contradicting that n is the characteristic of F, since m < n. since n cannot therefore be composite, and the rules for a field say it cannot be 1, n must be prime.

but it is easy to see now that the subset of any finite field {k*1 : k in Z} is a subfield of our finite field. this subfield is called "the prime field of F", let's call it K.

F is a vector space over K, and as F is finite, it must be of finite dimension (we can only pick finitely many basis elements for any basis), say m.

now K^m is also a vector space over K, with the same dimension, and any two vector spaces with the same dimension are isomorphic (as vector spaces). this means there is a bijection between them, and as both sets are FINITE, they have the same cardinality (size). well K^m has p^m elements, where p = char(K) = |K|.

thus F (our original finite field) also must have p^m elements.

so you'll never find a field with 6 elements, they don't exist.

the rules for a field are rather restrictive. what happens, on a naive level, is that if we could have other factors of |F| besides p, is that it would lead to "zero-divisors". zero-divisors are very bad (for division) because you can no longer "cancel" same multiplications:

to see what i mean: suppose we consider {0,1,2,3,4,5}, where 6 = 0 (the integers mod 6). in a field, we would have that:

2k = 2m implies k = m (because we can "divide by 2", that is: multiply by "2 inverse", or "cancel the 2's").

but look:

2(3) = 2(0) = 0 (since 6 = 0), but 3 is certainly NOT 0. 2 and 3 are zero-divisors in this system, which mean that they have "some of the bad properties of 0" (in particular, you can't "divide by them"). the only way around this, is to only allow powers of p to divide the size of the field (prime powers are "safe", they don't lead to zero-divisors).

**********

how this relates to coding theory: if we are going to have an effective code, we need to be able to encode AND decode, faithfully. we also need finite structures that give this to us so we can establish the strength of our coding system (we can calculate how long it will take for a code to be broken for a finite system, but an infinite system there is no upper bound, which poses practical problems in implementation). typically, in public/private key systems, we use a simple "additive system" for numerical encoding (translating the ciphertext to a number), and then use exponentiating (which is really just multiplication in disguise) to create the "keys". in other words, we need a field, to "undo the coding".

the general mathematical structure in which you have "one thing to do" that can always "be undone" is a group. there are some niceties to be observed (such as the associative law) but most things we deal with mathematically can be thought of as functions of one sort or another, and composition of functions is indeed associative. this concept is very general, and has deep roots in the theory of equations, geometry, and combinatorics. it's hard to understand what is going on in finite fields without it, so you really should learn at least the basics.

Thank you Brothers, will read these explanations. For notations I come up with new questions. I will read the basics ofcourse.

-Devanand T