11
$\begingroup$

In the course I'm studying, if I've understood it right, the main difference between the two is supposed to be that finite fields have division (inverse multiplication) while rings don't. But as I remember, rings also had inverse multiplication, so I can't see any difference.

What is the main difference between finite fields and rings?

$\endgroup$
  • 3
    $\begingroup$ Try finding the multiplicative inverse of $p \pmod {pq}$. $\endgroup$ – CodesInChaos Jan 30 '18 at 11:52
  • 3
    $\begingroup$ The difference is that if you like it you can't necessarily put a finite field on it... $\endgroup$ – Mehrdad Jan 30 '18 at 23:18
  • 2
    $\begingroup$ A field is a ring... $\endgroup$ – fkraiem Jan 31 '18 at 8:12
20
$\begingroup$

In general rings do not have inverse multiplication, as you claimed. Think for example about the integers modulo $4$. In this case, $2$ is not invertible as there is no element that multiplied by $2$ gives you $1$ (the unit of the ring). You can check this easily by exhausting the possibilities: $$0\cdot 2 \equiv 0 \bmod 4, \ \ \ 1\cdot 2 \equiv 2 \bmod 4, \ \ \ 2\cdot 2 \equiv 0 \bmod 4, \ \ \ 3\cdot 2 \equiv 2 \bmod 4$$

You can also rely on the following lemma:

The only elements invertible modulo $n$ are those that are coprime to $n$

If $n$ is prime, then all non-zero elements modulo $n$ are coprime to $n$. But if $n$ is not a prime, then you have non-zero elements modulo $n$ that can share nontrivial divisors with $n$.

$\endgroup$
  • 4
    $\begingroup$ $\mathsf{GF}(4)$ is a field since, by definition, it's the degree-$2$ extension of $\mathsf{GF}(2)$. I don't know why are you denoting it by $\mathsf{GF}(\mathsf{GF}(2)^2))$, that notation simply doesn't make sense. $\endgroup$ – Daniel Jan 30 '18 at 14:01
  • $\begingroup$ I lost an edit to my prior comment, I deleted it. It should have been although "integers modulo 4" is not a field ... . That syntax came from some old notes on sub-field mapping. What is the proper shorthand syntax for GF(256), based on degree 2 GF(4) in turn based on degree 2 GF(2)? The class notes would have this as GF(GF(GF(2^2)^2)) This is a common sub-field mapping for hardware inversion 1/x for AES (it saves gates). $\endgroup$ – rcgldr Jan 30 '18 at 15:26
  • 1
    $\begingroup$ Based on this IEEE composite field for AES article, the syntax is $GF(((2^2)^2)^2)$ . $\endgroup$ – rcgldr Jan 30 '18 at 16:11
  • 1
    $\begingroup$ The notation GF(n) normally means "the (unique up to isomorphism) finite field of order n". It does not say anything about a particular representation, unless your source uses the notation in a non-standard way, in which case you should refer to the definitions therein. $\endgroup$ – fkraiem Jan 30 '18 at 23:06
  • 1
    $\begingroup$ On the other hand, for all non zero x, there is a y such that xy=2 mod 4. It's not an inverse, but I find this result interesting anyway $\endgroup$ – Florian Bourse Jan 31 '18 at 8:35
22
$\begingroup$

Since you specified finite fields and other answers didn't talk about it, I am adding the following:

Fields are rings which are commutative and in which all nonzero elements have multiplicative inverse.

But finite fields have another important property that distinguish them from rings: every finite field is completely specified by its order, because they always have exactly $p^n$ elements for some prime $p$ and natural $n$ and any two finite fields of same order are isomorphic.

Notice, saying that two fields are isomorphic means that they are the same, but represented in two different ways.

That is not the case for rings. For instance, this answer provides examples of rings that have $4$ elements but are not isomorphic:

$\mathbb{Z}_4,~ \mathbb{F}_2[x]/(x^2+x),~ \mathbb{F}_2[x]/(x^2+x+1),~ \text{and} ~ \mathbb{F}_2[x]/(x^2)$

$\endgroup$
  • $\begingroup$ Might it be helpful to say that every finite field order is isomorphic to the set of integers congruent mod P for a prime integer P (rather than just that they're isomorphic to each other)? That would make apparent a mapping between the fields (if a member of field F1 is N times the field's additive identity, then the corresponding member of field F2 would be N times its additive identity). $\endgroup$ – supercat Jan 30 '18 at 18:29
  • $\begingroup$ @supercat I am sorry, but I am not sure I understood what you said... Do you mean that for all finite field $F$ there is a prime $p$ such that $F$ is isomorphic to $\mathbb{Z}_p$? $\endgroup$ – Hilder Vítor Lima Pereira Jan 30 '18 at 21:07
  • 2
    $\begingroup$ Not every finite field is isomorphic to $\mathbb{Z}_p$, but every finite field does have some subfield that is isomorphic. $\endgroup$ – Tjaden Hess Jan 30 '18 at 22:14
  • $\begingroup$ @TjadenHess that is true. But I am wondering if that is what supercat meant, because since he/she said "every finite field order is isomorphic" and I don't see how orders can be isomorphic, his/her comment is not very clear for me. $\endgroup$ – Hilder Vítor Lima Pereira Jan 30 '18 at 22:33
  • $\begingroup$ @TjadenHess: Was I misunderstanding what the original poster was saying? The third paragraph says that any two finite fields of the same order are isomorphic; since Z[p] is a finite field of order p, would that third paragraph not imply that any finite field of order p is isomorphic to Z[p]? Can you describe any finite field where that would not be the case? Or maybe you thought I was saying that they were all congruent for the same prime, rather than that for each field there exists a prime for which the isomorphism exists? $\endgroup$ – supercat Jan 31 '18 at 15:27
8
$\begingroup$

Take a set $S$ and an operation, let's call it $\oplus$. Also take another operation, say $\odot$. Also fix an element $\mathcal O\in S$ such that $\forall s\in S: \mathcal O\oplus s=s$ and fix another element $\mathcal I\in S$ such that $\forall s\in S: \mathcal I\odot s=s$.

Now I will list a set of properties and behind some properties I'll write names. If all the previous points apply, then the name can be applied to the named tuple.

  1. (closure under addition) $\forall s_1,s_2\in S: (s_1\oplus s_2)\in S$
  2. (additive associativity) $\forall s_1,s_2,s_3\in S:(s_1\oplus s_2)\oplus s_3=s_1\oplus(s_2\oplus s_3)$. We can now call $(S,\oplus)$ a semigroup.
  3. (additive identity) $\exists \mathcal O\in S:\forall s\in S: \mathcal O\oplus s=s\oplus \mathcal O=s$. We can now call $(S,\oplus,\mathcal O)$ a monoid.
  4. (additive inverses) $\forall s\in S:\exists s'\in S: s'+s=s+s'=\mathcal O$. We can now call $(S,\oplus,\mathcal O)$ a group.
  5. (additive commutativity) $\forall s_1,s_2\in S:s_1\oplus s_2=s_2\oplus s_1$. We can now call $(S,\oplus,\mathcal O)$ an abelian group.
  6. (multiplicative closure) $\forall s_1,s_2\in S:s_1\odot s_2\in S$
  7. (multiplicative associativity) $\forall s_1,s_2,s_3\in S:s_1\odot (s_2\odot s_3)=(s_1\odot s_2)\odot s_3$. We can now call (with 6 and 7) $(S,\odot)$ a semigroup.
  8. (multiplicative identity) $\exists \mathcal I\in S:\forall s\in S:\mathcal I\odot s=s\odot \mathcal I=s$. We can now call (with 6-8) $(S,\odot,\mathcal I)$ a monoid.
  9. (right distributivity) $\forall s_1,s_2,s_3\in S: (s_1\oplus s_2)\odot s_3=(s_1\odot s_3)\oplus (s_2\odot s_3)$
  10. (left distributivity) $\forall s_1,s_2,s_3\in S: s_1\odot (s_2\oplus s_3)=(s_1\odot s_2)\oplus (s_1\odot s_3)$. We can now call $(S,\oplus,\odot,\mathcal O,\mathcal I)$ a ring. Note: In some definitions having a multiplicative identity is optional.
  11. (multiplicative commutativity) $\forall s_1,s_2\in S:s_1\odot s_2=s_2\odot s_1$. We can now call $(S,\oplus,\odot,\mathcal O,\mathcal I)$ a commutative ring.
  12. (multiplicative inverses) $\forall s\in (S\setminus\{\mathcal O\}):\exists s'\in S:s\odot s'=s'\odot s=\mathcal I$. We can now call $(S,\oplus,\odot,\mathcal O,\mathcal I)$ a field.

If you want finiteness as well, then you write finite X in front of any of the names above if $\exists n\in\mathbb N:n=\left|S\right|$, that is, if $S$ is has a finite amount of elements.

As for the main difference between rings and fields: Rings don't require multiplication to be commutative. A common example would be $\mathbb R^{2\times 2}$ (the set of all 2x2 matrices with real-valued entries) with the usual matrix addition and multiplication. This features neither commutativity under multiplication nor can you always find inverse matrices. As for the difference between commutative rings and fields, simply consider $\mathbb Z_n$ with $n=pq$ for some primes $p,q$, ie the set of all nonegative integers smaller than $n$ with addition and multiplication with modular reduction $\bmod n$ at the end. In this ring you cannot find a multiplicative inverse of any number with $\gcd(n,x)>1$, so f.ex. for $x=p$, that is you can't find any $x$ such that $x\cdot p\bmod{pq}=1$. For a very concrete example look at the multiplication table for $n=3\cdot 5=15$ and notice how in the row and the column with the entry $3$ you can only ever get $0,3,6,9,12$ as the result of a multiplication by $3$, but never $1$, so $3$ has no multplicative inverse in $\mathbb Z_{15}$ and thus $\mathbb Z_{15}$ with the above elements and operations is not a field, but a commutative ring.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.