The restriction in other rings is indeed that z = x % y such that (norm(z) < y -- Update: corrected error spotted by ivancho) norm(z) < norm(y). Of course, you have some freedom in how you define the norm.

The point is that, if you can define modulus and a norm in such a way, then the ring is a principial ideal ring, and thus, a UFD. (The proof goes this way: norm and remainder => gcd => all ideals are principial => every irreducible elements are prime => unique factorisation.) This is one of the most common proofs you can prove the Fundamental Theorem of arithmetic, that is, the fact that every integer can be decomposed to the product of primes. 

#ifdef MATHMONKS

[download]

The rings where you can define remainder in such a way are called Euclidean rings. Some other restrictions are necessary too, I'm not sure in the exact conditions, but I think it suffices that the ring must be Noetherian, commutative integral domain; and the norm must be positive integer valued (on all nonzero elements of the ring), multiplicative, and only the units can have norm 1; and for every a and 0 != b, there exists a p and q such that a = p * b + q, and norm(q) < norm(b). Note however that not all principial domains are Euclidean, and not all UFDs are principial domains.

Here are some simple examples (but I am likely to make errors here, so correct me if you think I'm wrong, and this is true for the above part too). Z, Z[i], Z[(1+sqrt(3)i)/2], Z[sqrt(2)], and Q[x] are Euclidean rings so UFDs too. Z[x] is not a Euclidean ring, but it is nevertheless an UFD, which can be proved from the Gauss-lemma (or one of the theorems called Gauss-lemma at least:). Z[sqrt(3)] is not a Euclidean ring, and is not UFD either: 4 = 2 * 2 = (1 + sqrt(3)i)(1 - sqrt(3)i). There's some interesting issue with multivariate polynomials, but I don't quite know what it is.

I list two very good books on the topic below. As this material is available in Hungarian, I cannot give you any English titles. (You can try to look in Mathworld though.)

  1. Dr. Szalay Mihály, Számelmélet.
    Tankönyvkiadó, Budapest, 1991.
    (This book also has a newer edition so look for that instead.)

  2. Surányi László, Algebra: Testek, gyűrűk, polinomok.
    Typotex, Budapest, 1997
    (this book refers to the first one at some places, which is not surprising because of the common authors) 

#endif

[download]

In reply to Re^3: Illegal Modulus zero by ambrus
in thread Illegal Modulus zero by Anonymous Monk

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.