Ideals

Ideals

An ideal $I$ of a ring $R$ is a subset that is:

1. A subgroup of $(R, +)$
2. Absorbing under multiplication: for all $r \in R$ and $a \in I$, both $ra \in I$ and $ar \in I$

Ideals are to rings what normal subgroups are to groups — they let us form quotient structures.

Ideals in $\mathbb{Z}_n$

In $\mathbb{Z}_n$, every ideal is principal — generated by a single element. The ideal generated by $a$ is:

$\langle a \rangle = \{0, a, 2a, 3a, \ldots\} \pmod{n}$

which equals $\{ka \bmod n : k = 0, 1, \ldots\}$.

Example: Ideals of $\mathbb{Z}_6$

• $\langle 0 \rangle = \{0\}$
• $\langle 1 \rangle = \{0, 1, 2, 3, 4, 5\} = \mathbb{Z}_6$
• $\langle 2 \rangle = \{0, 2, 4\}$
• $\langle 3 \rangle = \{0, 3\}$

Note: $\langle 4 \rangle = \{0, 4, 2\} = \langle 2 \rangle$ and $\langle 5 \rangle = \langle 1 \rangle$.

Maximal and Prime Ideals

• An ideal $I \neq R$ is maximal if no ideal lies strictly between $I$ and $R$
• An ideal $I$ is prime if $ab \in I$ implies $a \in I$ or $b \in I$

In $\mathbb{Z}_n$, $\langle d \rangle$ is a prime ideal if and only if $d$ is prime (or $d = 0$ when $n$ is prime).

Your Task

Implement principal_ideal(a, n) returning the sorted elements of $\langle a \rangle$ in $\mathbb{Z}_n$, all_ideals(n) returning all distinct ideals (sorted by size then lex), and is_prime_ideal(ideal, n) checking the prime ideal condition.