Units, zero divisors and ideals of Z/nZ

"""Units, zero divisors, nilpotents and ideals in the rings Z/nZ.

For each n the program sorts the residues 0, ..., n - 1 into units (elements
with a multiplicative inverse) and zero divisors (non-zero a with ab = 0 for
some non-zero b), finds the nilpotent elements (a^k = 0) and the idempotents
(e^2 = e), and lists all ideals by brute force. It confirms, for every n up to
60, that each non-zero residue is exactly one of unit or zero divisor, that the
units number phi(n) = #{a : gcd(a, n) = 1}, that the ideals correspond to the
divisors of n, and that Z/nZ is a domain exactly when it is a field, exactly
when n is prime. Exact and exhaustive for these n only.
"""

from math import gcd

def units(n):
    """Residues a in Z/nZ with some b such that a * b = 1 (mod n)."""
    return [a for a in range(n) if any(a * b % n == 1 % n for b in range(n))]

def zero_divisors(n):
    """Non-zero residues a with a * b = 0 (mod n) for some non-zero b."""
    return [a for a in range(1, n) if any(a * b % n == 0 for b in range(1, n))]

def nilpotents(n):
    """Residues a with a^k = 0 (mod n) for some k >= 1 (k = n suffices)."""
    return [a for a in range(n) if pow(a, n, n) == 0]

def idempotents(n):
    """Residues e with e * e = e (mod n)."""
    return [e for e in range(n) if e * e % n == e]

def ideals(n):
    """All ideals of Z/nZ, found by brute force as sorted tuples.

    An ideal is an additive subgroup closed under multiplication by every
    residue. Every subset generated by one element is checked, and the ideal
    generated by a set is the one generated by the gcd, so this is complete;
    the test file also checks completeness against all subsets for small n.
    """
    found = set()
    for a in range(n):
        ideal = tuple(sorted({a * r % n for r in range(n)}))
        found.add(ideal)
    return sorted(found, key=len)

def is_ideal(subset, n):
    """True when subset is non-empty, closed under +, and absorbs products."""
    s = set(subset)
    return bool(s) and all((x + y) % n in s and x * r % n in s
                           for x in s for y in s for r in range(n))

def is_prime(n):
    """Trial division."""
    return n >= 2 and all(n % p for p in range(2, int(n ** 0.5) + 1))

def main():
    print(" n  units  zero divisors  ideals  idempotents  non-zero nilpotents")
    for n in (2, 4, 6, 7, 8, 9, 10, 12, 15, 30):
        u, z = units(n), zero_divisors(n)
        nil = [a for a in nilpotents(n) if a]
        print(f"{n:>2}  {len(u):>5}  {len(z):>13}  {len(ideals(n)):>6}  "
              f"{len(idempotents(n)):>11}  {nil}")
    split = phi = divisors = domain = True
    for n in range(2, 61):
        u, z = set(units(n)), set(zero_divisors(n))
        split &= u.isdisjoint(z) and u | z == set(range(1, n))
        phi &= len(u) == sum(gcd(a, n) == 1 for a in range(n))
        divisors &= len(ideals(n)) == sum(n % d == 0 for d in range(1, n + 1))
        domain &= (not z) == (len(u) == n - 1) == is_prime(n)
    print("For every n from 2 to 60:")
    print(f"  each non-zero residue is a unit or a zero divisor, not both: {split}")
    print(f"  number of units = phi(n) = #{{a : gcd(a, n) = 1}}: {phi}")
    print(f"  number of ideals = number of divisors of n: {divisors}")
    print(f"  no zero divisors <=> every non-zero a a unit <=> n prime: {domain}")
    print()
    print("Epistemic status: exact, exhaustive checks for n <= 60. In a finite")
    print("commutative ring every non-zero element is a unit or a zero divisor,")
    print("and Z/nZ is a field exactly when n is prime: those are theorems, proved")
    print("in the lesson; the table is evidence and illustration, not proof.")

if __name__ == "__main__":
    main()