[eru]

Purely on the mathematical side, you can define division as the inverse of multiplication, and then when you are working modulo a prime number, division works just fine. (But computers usually don't implement it that way.)

As an example when working modulo 17 and you want to work out what division by 3 means. You want to solve equations like: x * 3 = 10 (mod 17). For this case, x = 9; because 9 * 3 = 27 = 10 (mod 17).

In general when working modulo 17, 6 is the multiplicative inverse of 3. Ie 6 * 3 = 1.

Thanks to Fermat's Little Theorem you can find multiplicative inverses very easily, y^(p-2) mod p gives you the inverse of y.

(Most programming languages won't know that you are going to apply a mod afterwards, so they just give you eg rounded or truncated integer division. Which is completely different in general.)

[Tainnor]

Sure, but computer arithmetic is modulo some power of two, which is not a prime. So you don't get a proper field and in particular, all even numbers don't have an inverse.

[eru]

Yes, that is true.

Technically you can get fields with p^n elements, too; but they are constructed in a more complicated way than just taking a modulo.

[Tainnor]

Yes. These sorts of fields are quite useful for crypto, so I believe there is even some hardware support for them in many CPUs, IIRC?

[eru]

https://en.wikipedia.org/wiki/CLMUL_instruction_set might be the closest to what you meant?

I just did some Google Scholar searches, and found a lot about FPGAs etc, but not too much about stock CPUs. But that might reflect more on my search skills than on availability of material.

Some standard CPUs now have instructions to specifically run eg AES.

https://www.snia.org/sites/default/files/files2/files2/SDC20... was probably the most interesting of the bunch I found. It's about error correcting codes, not crypto. (Though interestingly, the holy trinity of error correcting codes, information theory and cryptography all flew once through the common conduit of Claude Shannon.)

[Tainnor]

thanks, hadn't really looked into it much before!

[threatofrain]

Huh? GF(2) is the smallest finite field, and 2 is a prime...? 0 is also excluded when we’re talking about multiplicative inverses.

[Tainnor]

Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1".

Now I'm not aware of any language where there is an integer type that has only two elements, unless you're talking about booleans - but booleans are so special that, while they're of course isomorphic to GF(2), we don't really use the same words (addition and multiplication) but different ones (exclusive disjunction (xor) and conjunction (and)).

So, in any real-life situation, your fixed-size integers won't form a field, because the ring of integers modulo n is only a field when n is prime, and so in particular, division by nonzero elements will be undefined in general.

And yes, of course, you can't divide by zero, but that's also true of the real numbers themselves, so no surprises there...

(I guess a better point would be that division is mathematically "broken" for integers anyway, since integers technically also don't form a field and, depending on the language, you may either get back a truncated result from division or will get a different type (ratio or floating point).)

[eru]

> Yes, I should have been more precise: "modulo some power of two, which is not a prime, unless we're talking about 2^1".

If you want to be even more nit-picky, 2^0 might also work. But whether your definition of a field admits fields with only a single element is just a question of taste, that is even less important or deep than whether your flavour of natural numbers includes 0 or not.

[Tainnor]

I've never seen anybody allow a field with just a single element, usually it says "a field is a ring with 1!=0...". But yeah, I suppose you could allow it, it's just an incredibly boring ring in which you actually can't divide at all, because there is no nonzero element.

[Tainnor]

eh that was wrong, you can of course divide in the zero ring, because the single element is its own inverse.

[threatofrain]

Has anyone yet demonstrated a field with a single element?

[Tainnor]

It's not a question of demonstration but of definition. I've only ever people define fields as requiring two distinct elements 0 and 1. However, every field is also a ring and there can be, up to isomorphism, only a single ring with one element, because you don't really get any choice as to how you define the operations. That's called the trivial ring or zero ring and it basically satisfies all of the axioms for a field too, except for not having two distinct elements. So if it were possible for a field with a single element to exist, it would have to be this one.

It is my understanding that some mathematicians are looking into some objects that are kind of "like" a field with one element, but not in the sense of classical algebra, see: https://en.m.wikipedia.org/wiki/Field_with_one_element

However, I haven't really looked into that.