in reply to Re^2: Illegal Modulus zero
in thread Illegal Modulus zero

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]

Replies are listed 'Best First'.
Re^4: Illegal Modulus zero
by ivancho (Hermit) on May 21, 2005 at 08:37 UTC
    oooh, heavyweight maths, delicious.. ++

    just want to point out a couple of things - first, a minor ommission, at the top you want norm(z) < norm(y)
    second, I was commenting on the impossibility to define that for general groups - looking at the cyclic group generated by y and its coset generated by x, there's no obvious element to be called 'the remainder'. When you go to rings, things are different, indeed.

    my algebra is a little rusty by now, but I think you need your principal ideal ring to be an integral domain as well, before you get UFD ( ie, no Z_6 and the like ), this relating to your second paragraph.. Looking further down, I see that you talk about domains only, so fair enough, and we don't want to look at ugly non-domain PIRs anyway..

    I think the issue with multivariate polynomials is that they are UFDs, but definitely not PIDs ( e.g. <x,y^2> ), but in any case, now I'm just getting depressed realizing how much I've forgotten, so I'll drop it here, and go back to my leaking recursive closures...

[reply]

      Thanks for spotting the error.

      As for integral domain, I think you are right. However, let me note that a norm on the ring implies that there are no zero-divisors.

[reply]
        ugh, of course... sorry, I took your line 'the ring is a principial ideal ring, and thus, a UFD' out of context..

        there's something very surreal in having such a discussion on perlmonks...

[reply]

In Section Seekers of Perl Wisdom