[swordswinger12]

One minor nitpick: the set of numbers mod 256 form a field. Powers of primes are also fields.

Edit: it seems I conflated two different constructions of a field of order 256. Apologies. It's been a few semesters since abstract algebra >.<

[ColinWright]

I don't think so. In the integers mod 256, 2 doesn't have a multiplicative inverse. We can see that because 2x128=0.

Do you mean the numbers mod 256 that are co-prime with 256 form a field? Even that doesn't work because 1+3=4, so it's not closed under addition.

So I'm not sure what you mean.

Added in edit ...

Given any positive number n, the numbers from 1 to n-1 that are co-prime to n form a group with multiplication as the group operation, but that's still not a field, so I'm still confused as to what you might mean.

[cdavidcash]

He is mistaken. What he meant is that there exists a finite field with exactly 256 elements, so you can "make" {0, ..., 255} into a finite field (in the sense that you can make any set of size 256 into a field by assigning + and * operations), but addition and multiplication in that field won't be the usual modular integer arithmetic. Instead, the operations will be determined by mapping the numbers to polynomials and performing modular polynomial operations and then mapping them back to numbers {0,...,255} (or determined by some other process that is morally equivalent).

[zackzackzack]

He means exactly what he said.

From wikipedia: "The finite fields are classified by size; there is exactly one finite field up to isomorphism of size p^k for each prime p and positive integer k." -http://en.wikipedia.org/wiki/Finite_field

[ColinWright]

Hmm. OK, this is an opportunity to learn something.

The integers mod 256 are closed under addition and multiplication. Distributivity obviously holds, and there is obviously an additive inverse. My question is about the multiplicative inverse.

What's the multiplicative inverse of 2?

To say that there exists a field of size 256 is a different matter, and I'd be interested in learning more.

Added in edit:

Quoting from the same wikipedia article:

Even though all fields of size p are isomorphic to Z/(pZ), for n ≥ 2 the ring Z/((p^n)Z) (the ring of integers modulo p^n) is not a field.

(Parentheses added for reduction of ambiguity)

Further edit: Not sure why this got a downvote, but I don't much care. Maybe people didn't realize that I wrote this before all the other answers streamed in. Still, now I've learned what may have been intended, and a little more besides, so I'm content.

[kenferry]

> What's the multiplicative inverse of 2?

What do you mean by 2? :-)

The typical way to describe the finite field of order 256 is to look at a set of polynomials like this,

c_7 * x^7 + c_6 * x^6 + ... + c_1 * x + c_0

where c_i is an element of Z/2Z, so it's either 0 or 1. Count how many such polynomials of degree <= 7 there are - since each coefficient is either 0 or 1, there are 2^8 = 256.

Ok. Now we can define adding these polynomials in the usual term by term way.

For multiplication, if you tried to just straight up multiply two polynomials of order 7, you might get a polynomial of order 14. So, here's the trick: pick a polynomial of degree 8 that cannot be factored as a product of polynomials of lesser degree. This is the polynomial equivalent of a prime number (prime numbers cannot be factored further either, right?).

Just as we can look at Z/pZ, we can look at the set of polynomials over Z/2Z modulo g, where g is that irreducible poly of order 8. It should not be any more obvious to you that this works than that it is that Z/pZ is well defined, forms a field, etc. But you can verify it in pretty much the same ways as you'd prove it for Z/pZ.

Anyway. So what do you mean by '2'? In this representation, 1+1 is 0.

Sometimes by '2' people mean x. That's because there's a natural coding of these polynomials as bits in a binary word. Since each coefficient is 0 or 1, you can say the ith bit is the coefficient of x^i. With that encoding, 2 is 0b10, is 1 * x^1 + 0, is x. So, the inverse of x is going to be x^254 mod g (where g is that irreducible generating polynomial).

[ColinWright]

Yes, but what he said was:

  : the set of numbers mod 256 form a field.

Without qualification it seems reasonable to assume the usual operations of addition and multiplication, and not to assume that the integers mod 256 are simply being used as an opaque labelling of the elements of a field such as you describe.

And the labelling is opaque, because while it's obvious what polynomial an integer gets mapped to, the multiplication depends on the particular g.

[zackzackzack]

I misread his statement and made it conform to what I know to be true. There is a finite field of size 256, and you could enumerate the elements in the field with all numbers mod 256, but the normal *,+ wouldn't work persay. The inverse of 2 could be any of the other numbers in the field, even itself. Should have been more careful; I usually try to avoid talking about Math on the internet.

[jgrimes]

There is a field of size 256, but it isn't Z/256Z.

"Even though all fields of size p are isomorphic to Z/pZ, for n ≥ 2 the ring Z/(p^n)Z (the ring of integers modulo p^n) is not a field. The element p (mod p^n) is nonzero and has no multiplicative inverse."

[JadeNB]

No, this is incorrect.

As has been pointed out, Z/256Z has zero-divisors, so it's not a field.

"Powers of primes are also fields" doesn't mean anything; integers are integers, not fields. "Powers of primes are orders of finite fields" is correct; so there is a field of order 256, but it's not Z/256Z. (Rather, you get it by finding a degree-8 irreducible polynomial over Z/2Z, and adjoining a root of it. In fact, the article gives the specific polynomial x^8 + x^4 + x^3 + x + 1.)