Turns out that I cannot find such thing as "the definition of division with remainder" for rings. It is all good if we specify integers, polynomials, etc, were one division with remainder is already defined, but if I try to do it for rings I get stuck. Here is why, you can start by saying that division with remainder of $x$ by $m$ means finding an expression $$ x = q \cdot m + r $$ where $\cdot$ and $+$ are the multiplication and addition of the ring. This is not enough because you can always choose $$ q= 0, \qquad r=x.$$ The concept of quotient rings almost fixes this, $m$ defines equivalence classes and $q$ is now just the equivalence class of $x$, but it doesn't tell us how to choose the representative $r$ of the class. This is actually reflected by the fact that even for integers, the remainder for negative numbers does not have a standard convention, only a most used one (see Modulo).
For positive integers we require $r<m$, and for polynomials we require the degree of $r$ to be less than the degree of $m$. We used an order and a partial order to fix the choice. So may question is:
Is a partial order always needed? do we need less? do we need more? (category theory answers are welcome, but only if translated to a reasonable language)
Notes:
- "long division" is still vague and only becomes precise one we name integer long division and polynomial long division, even then, it refers to the specific algorithm that performs division with remainder.
- In Wikipedia's page Remainder, again the definition of "remainder" is vague until integer or polynomial is specified.
- In Wikipedia's page Division algorithm remainder is only defined precisely at specific algorithms.
Context: I was trying to write a basic introduction to carryless/polynomial reduction and decided to introduce it as "the division with remainder" that corresponds to carryless/polynomial multiplication and XOR addition and to my surprise I could not find such thing as the definition of "division with remainder" in general.
On $\Bbb{Z}$ we can define division with remainder by, for every $x,y\in\Bbb{Z}$, finding $q,r$ such that $y = qx + r$ satisying $|r| < |x|$.
Now, this doesn't work in arbitrary rings because the absolute value has no meaning, generally. However, what we can do is recreate a notion of absolute value on the ring. This is what is called a "Euclidean domain".
A Euclidean domain is an integral domain $R$ (recall that this is a non-trivial commutative ring without non-zero zero divisors), together with a function $\psi: R\backslash\{0\} \to \Bbb{Z}_{\geq0}$ satisfying: \begin{align} &\bullet\;\; \text{For any } x,y\in R\backslash\{0\}, \text{ if } x \,\vert\, y \;\;\text{ then } \psi(x) \leq \psi(y); \\ &\bullet\;\; \text{For any } x,y\in R\backslash\{0\}, \text{ there are } q,r \in R \;\text{ s.t. } y=qx+r \quad \text{ and } r = 0 \text{ or } \psi(r) < \psi(x). \end{align}
This generalizes "division with remainder" over an arbitrary integral domain. See also https://en.wikipedia.org/wiki/Euclidean_domain
A related notion of division over a ring is a unique factorisation domain. See https://en.wikipedia.org/wiki/Unique_factorization_domain