Results 1 to 4 of 4

Math Help - Why do finite fields or galois fields must have primenumber primenum power elements?

  1. #1
    Newbie
    Joined
    Jul 2012
    From
    India
    Posts
    8

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    GJA
    GJA is offline
    Member
    Joined
    Jul 2012
    From
    USA
    Posts
    109
    Thanks
    29

    Re: Why do finite fields or galois fields must have primenumber primenum power elemen

    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!
    Last edited by GJA; August 8th 2012 at 07:16 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Why do finite fields or galois fields must have primenumber primenum power elemen

    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 Km 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 Km has pm elements, where p = char(K) = |K|.

    thus F (our original finite field) also must have pm 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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jul 2012
    From
    India
    Posts
    8

    Re: Why do finite fields or galois fields must have primenumber primenum power elemen

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

    -Devanand T
    Last edited by dexterdev; August 8th 2012 at 10:56 PM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Galois fields
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: July 23rd 2012, 08:44 AM
  2. Replies: 0
    Last Post: July 6th 2012, 09:06 AM
  3. Galois fields
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: October 24th 2010, 05:03 AM
  4. fields and elements
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: March 17th 2010, 07:24 PM
  5. finite fields of elements
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 28th 2009, 02:55 PM

Search Tags


/mathhelpforum @mathhelpforum