7
$\begingroup$

A Euclidean domain $E$ is an integral domain where, for any $a, b \in E$, we can write:

$$a = bq + r$$

with either $r = 0$ or $f(r) < f(b)$, where $f$ is the valuation function attached to $E$.

Can I define the binary operation $\bmod$ such that $a \bmod b = r$ for all Euclidean domains? Will it always behave the same way as the mod function on $\mathbb{Z}$ that I'm used to?

What got me wondering was the observation that I can do this on the Euclidean domain $\mathbb{Q}[x]$ by using quotient rings:

$$ \begin{aligned} \psi_{x^2 + x} &:: \mathbb{Q}[x] \rightarrow \mathbb{Q}[x]/\langle x^2 + x \rangle\\ \psi_{x^2 + x}(x^2 + x + 5) &= x^2 + x + 5 + \langle x^2 + x \rangle = 5 + \langle x^2 + x \rangle\\ \end{aligned} $$

So $r = 5$ and $x^2 + x + 5 \bmod (x^2 + 5) = 5$, as you would expect. It also works for multiplication.

$\endgroup$
5
  • $\begingroup$ Side Note: ​ ​ ​ I found it non-obvious that there are any rings which non-trivially admit such modular reduction. ​ Can you come up with one before reading the answer to the question I asked about that? ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user57159
    Commented Apr 14, 2016 at 18:57
  • $\begingroup$ @RickyDemer: I'm a bit confused -- what do you mean by non-trivial? The example that got me wondering about this was $\mathbb{Q}[x]$. $\endgroup$
    – Eli Rose
    Commented Apr 14, 2016 at 19:05
  • $\begingroup$ By "non-trivial", I mean [[not isomorphic to the integers] and [has an ideal that's neither just {0} nor the whole ring]]. ​ $\mathbb{Q}[x]$ doesn't work because , for example, what would [x-1 mod x] be? ​ ​ ​ ​ $\endgroup$
    – user57159
    Commented Apr 14, 2016 at 19:13
  • $\begingroup$ @RickyDemer: Are you talking about the mod function or binary relation? As a function, I would say that $x - 1 \mod x = -1$. $\endgroup$
    – Eli Rose
    Commented Apr 14, 2016 at 19:16
  • $\begingroup$ I'm talking about the mod function, for which outputs should be non-negative, at least when both inputs are positive. ​ ​ $\endgroup$
    – user57159
    Commented Apr 14, 2016 at 19:17

3 Answers 3

11
$\begingroup$

As you say, you’re using the binary function “mod” of the computer scientists. But in mathematics, one finds that this function is of very limited utility, and we use the equivalence relation $a\equiv b\pmod I$ instead. It’s read, “$a$ is congruent to $b$ modulo $I$”, and it’s a sentence that will be either true or false.

To your specific question, consider the Euclidean domain $\Bbb Z[i]$, the Gaussian integers. If you take a complex modulus like $\zeta=6+3i$, it makes perfect sense to say whether two Gaussian numbers $\alpha$ and $\beta$ are congruent modulo $\zeta$, namely you check to see whether $\beta-\alpha$ is a multiplie of $\zeta$ by another Gaussian number. But there is no good and consistent way of defining a “mod” function here. You can make up an artificial “mod” function in this situation, but it will be neither good nor consistent.

$\endgroup$
5
  • $\begingroup$ Nice counterexample. I guess I'm having a hard time relating this to my knowledge that the binary mod operation does work over $\mathbb{Z}$. (If you choose the smallest positive, I guess). What does $\mathbb{Z}$ have that $\mathbb{Z}[i]$ lacks in this case? $\endgroup$
    – Eli Rose
    Commented Apr 6, 2016 at 5:09
  • 1
    $\begingroup$ @AlfredYerger: $\Bbb Z[i]$ certainly is a UFD. $5$ is not irreducible in $\Bbb Z[i]$, so $5 \times 1$ is not a valid factorization into irreducibles. $\endgroup$ Commented Apr 6, 2016 at 10:24
  • $\begingroup$ Another question I have here: if I choose a convention for mod here, like "the positive real one" in what ways is the resulting function inconsistent? $\endgroup$
    – Eli Rose
    Commented Apr 6, 2016 at 13:11
  • 1
    $\begingroup$ @EliRose : ​ There's not necessarily a positive real one. ​ ​ ​ ​ $\endgroup$
    – user57159
    Commented Apr 6, 2016 at 17:01
  • $\begingroup$ @RickyDemer, precisely. To define “mod” function, you must choose beforehand a full set of representatives of the equivalence classes (cosets) of your relation. I chose my example precisely so that there would be no such set consisting only of real Gaussian integers. One possible set would be all $m+ni$ with $0\le m<5$ and $0\le n<3$, but this is truly artificial, as I think one’ll notice after trying to work with it for a while. $\endgroup$
    – Lubin
    Commented Apr 6, 2016 at 19:40
7
$\begingroup$

To your title: No. Any ring works for a mod operation, you just make things the standard coset way. Let $I\subseteq R$ be an ideal. Then we define

$$a\equiv b\mod I\iff a-b\in I.$$

And this is a well-defined equivalence relation.

For the integers this reduces to

$$a\equiv b\mod n\iff a-b\in (n)\iff a-b=nk$$

for some $k\in\Bbb Z$.

So to the question in the body (which is not the same thing) as to if we can define mod for EDs: yes you can, but they're not the most general setting.

$\endgroup$
10
  • $\begingroup$ Cool! Can we also construct this definition via quotient rings in the manner I was trying to show? $\endgroup$
    – Eli Rose
    Commented Apr 6, 2016 at 3:50
  • $\begingroup$ I'm not sure what you mean, $R/I$ is what a quotient ring is, and it literally means "things of $R$ up to equivalence mod $I$." Perhaps you mean with the remainder? Remainders is only a thing for EDs, that's their defining property. The mod operation is much more general than this, though $\endgroup$ Commented Apr 6, 2016 at 3:53
  • $\begingroup$ In my abstract algebra class, we defined $R/I$ as a group of cosets, so the connection to mod is new to me. (It's a lot nicer). So it seems like you're saying that $R/I$ is isomorphic to the group of equivalence classes of elements of $R$ mod $I$, given the definition above. Is that right? What does "remainder" mean in the way that you use it here? $\endgroup$
    – Eli Rose
    Commented Apr 6, 2016 at 4:04
  • $\begingroup$ @EliRose There is no notion of remainder in general rings, if there were they would all be EDs. The term "mod" is used in groups for things modulo normal subgroups, and in rings as rings modulo ideals, i.e. it's always for coset spaces for special subgroups (in groups normal, in rings ideals). You seem to think it is "connected" to the classical notion of "mod," but in reality this notion is the generalization of mod, it's not connected to it, it literally is it. $\endgroup$ Commented Apr 6, 2016 at 5:33
  • $\begingroup$ Okay, I take your point. (and I wish it had been introduced to me that way). $\endgroup$
    – Eli Rose
    Commented Apr 6, 2016 at 13:13
4
$\begingroup$

In a Euclidean domain, there is no requirement that $r$ be uniquely determined by $a$ and $b$, so you cannot define mod in the way you proposed.

$\endgroup$
10
  • 3
    $\begingroup$ Relating this answer with Adam's below: there's no need to pick canonical representatives to talk about mod. The point is that it's often better to think of mod as a ternary relation, than as a binary operation. $\endgroup$ Commented Apr 6, 2016 at 3:39
  • $\begingroup$ @NoahSchweber Yes, but the original post talks about defining the "binary operation" mod, in which you are picking a canonical representative. $\endgroup$
    – Ted
    Commented Apr 6, 2016 at 3:40
  • $\begingroup$ Sorry, that wasn't meant as a disagreement with your answer, more a comment to the OP: that while you do need to talk about representatives to view mod as a binary function, everything we actually use mod for goes through fine if it's just a relation. Edited for clarity (and +1 btw). $\endgroup$ Commented Apr 6, 2016 at 3:43
  • $\begingroup$ Don't we ordinarily pick a canonical representative when we say "$12$ divided by $5$ has a remainder of $2$", though? I guess in that case I'm choosing the smallest positive pair $(q, r)$ such that $a = bq + r$. $\endgroup$
    – Eli Rose
    Commented Apr 6, 2016 at 3:49
  • $\begingroup$ Or perhaps I'm just choosing the only pair with both positive -- is there another that works? Are there other Euclidean domains where the choice is not so clear? $\endgroup$
    – Eli Rose
    Commented Apr 6, 2016 at 3:52

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .