Factorization, Ideals and More Euclid!

The previous entry ended with a bit of a cliffhanger. We explained the math of the Euclidean Algorithm and then followed that up with a Python implementation for the integers. However, we didn’t prove that the algorithm actually returns a greatest common divisor. We’ll do that right now.

Theorem: Correctness of The Euclidean Algorithm

Proof

We’ll be referencing the Euclidean Algorithm as implemented in the previous entry. Follow the above link for definitions of the variables we’ll be using.

We noted in the previous entry that

$$x_{i+2}=x_i-f_i{x}_{i+1}$$

which, when combined with this mini-lemma “divisor across a sum” tells us that if $d|x_i$ and $d|x_{i+1}$, then $d|x_{i+2}$.

Applying induction, we see that anything which divides $x_0$ and $x_1$ will also divide all the other $x_i$’s.

Let $j+2$ be the index such that $x_{j+2}=0$. Then the algorithm returns $x_{j+1}$. From what we said in the previous paragraph, $x_{j+1}$ is a multiple of the gcd of the input, $a$ and $b$.

Now we show that $x_{j+1}$ divides the gcd of $a$ and $b$, so they are equal (up to multiplication by units).

Since $x_{j+2}=0$ and

$$x_{j+2}=x_j-f_j{x}_{j+1}$$

We see that $x_{j+1}$ divides $x_j$ and, again, by the “divisor across a sum” lemma, we have $x_{j+1}$ divides $x_i$ for all of the $i$’s down to $i=0$. Thus, $x_{j+1}$ divides $a$ and $b$, and therefore will divide their greatest common divisor.

QED

---

In the previous entry, we gave a definition for irreducible element and ring norm. We then showed that having a ring norm implies that we can factor elements into irreducibles. Now we’re going to show that having a norm map does not guarantee unique factorization. This will also provide us an example of irreducible elements which are not prime.

This is a classic example; it’s fairly simple and is found in many text books.

Example: Irreducibles which aren’t prime

Let $R=\mathbb{Z}[\sqrt{-5}]$, the set of complex numbers of the form

$$\{a+b\sqrt{-5}|a,b\in \mathbb{Z}\}$$

We can then define $N:R\to {\mathbb{Z}}_{\ge 0}$ such that

$$N(a+b\sqrt{-5}):=a^2+5b^2$$

Notice that

$$N(a+b\sqrt{-5})=(a+b\sqrt{-5})(a-b\sqrt{-5})$$

so if

$$x=a+b\sqrt{-5}$$

and we let

$$\overline{x}=a-b\sqrt{-5}$$

then

$$N(x)=x\overline{x}$$

Now we want to show that

$$\overline{xy}=\overline{x}\overline{y}$$

which can be done by calculating the left-hand and the right-hand side of the above equation. If

$$\begin{array}{r}x=a+b\sqrt{-5}\\ y=c+d\sqrt{-5}\end{array}$$

then both sides evaluate to

$$\begin{array}{rl}ac& -5bd-\\ (ad& +bc)\sqrt{-5}\end{array}$$

so the result holds. Now we can more easily prove that $N(xy)=N(x)N(y)$, because

$$\begin{array}{rl}N(xy)& =(xy)\overline{(xy)}\\ & =(xy)(\overline{x}\overline{y})\\ & =(x\overline{x})(y\overline{y})\\ & =N(x)N(y)\end{array}$$

Finally, we have to show that $N(x)=1$ if and only if $x$ is a unit. It’s clear that $N(1)=1$. Suppose that $xy=1$. Then we’ve shown that $N(x)N(y)=1$. Therefore, $N(x)=1$. So if $x=a+b\sqrt{-5}$, then we have

$$a^2+5b^2=1$$

Thus, $b=0$ and $a=1$. This means that $1$ is the only unit in $R$.

This means that $N$ is, indeed, a norm map, so every element of $R$ can be factored into irreducibles.

We will now show that $2$, $3$, $1+\sqrt{-5}$ and $1-\sqrt{-5}$ are all irreducible.

Notice that

$$\begin{array}{rl}N(2)& =4\\ N(3)& =9\\ N(1+\sqrt{-5})& =6\\ N(1-\sqrt{-5})& =6\end{array}$$

so if an element is a proper divisor of any of them, then its norm must either be $2$ or $3$. However, it’s not difficult to see that no element has either value as its norm, because then we’d have $a^2+5b^2=2$ or $3$.

Finally, notice that

$$\begin{array}{rl}6& =2\cdot 3\\ & =(1+\sqrt{-5})(1-\sqrt{-5})\end{array}$$

so we’ve factored $6$ into irreducibles in two distinct ways. From this we see that, for example, $2$ cannot be prime, since it divides $6=(1+\sqrt{-5})(1-\sqrt{-5})$, but $2\nmid 1+\sqrt{-5}$ and $2\nmid 1-\sqrt{-5}$.

---

One of the most important lessons to take away from that example is that we have to be careful with factorization. We cannot assume unique factorization, even if we have a norm map (and thus factorization into irreducibles).

You should also note that our proof that $N:\mathbb{Z}[\sqrt{-5}]\to {\mathbb{Z}}_{\ge 0}$ is a norm map works for every square-free negative integer, $-n$. I.e.

$$N:\mathbb{Z}[\sqrt{-n}]\to {\mathbb{Z}}_{\ge 0}$$

where

$$N(a+b\sqrt{-n})=a^2+n{b}^2$$

is a norm map.

We’re now going to introduce a kind of ring which always has unique factorization (by definition).

Definition: Unique Factorization Domain

Unique Factorization Domains are often abbreviated as “UFD’s”.

Lemma: Factorization into Primes is Unique

Proof

The proof is little more than induction applied to the definition of a prime element. Let

$$\begin{array}{rl}x& =u\cdot \prod _{i=1}^m{q}_i\\ & =v\cdot \prod _{j=1}^n{p}_j\end{array}$$

be two factorizations of an arbitrary non-zero non-unit element $x$, where $u$ and $v$ are units and $q_i$ and $p_j$ are prime elements. Then we have $q_1|p_j$ for some $j$.

$q_1|p_j$ implies $q_{1}d=p_j$, and since $p_j$ is prime, we know that either $p_j|d$ or $p_j|q_1$. Suppose that $p_j|d$. Then

$$d|p_j|d$$

so $p_j{\equiv }_{u}d$, which means that $q_1$ is a unit. This contradict our assumption that $q_1$ is prime.

Then, a similar argument shows that $d$ must be a unit, so $q_1{\equiv }_u{p}_j$. We can continue this for $q_2$, $q_3$, … , $q_m$. When we’ve done this, we have to have $m=n$, otherwise we would have a product of primes equal to a unit, which cannot happen.

Thus, we see that each $q_i$ is equal to some $p_j$ times a unit.

QED

Definition: Principal Ideal Domain

Principal Ideal Domains are often abbreviated as “PID’s”.

Theorem: A PID is a UFD

The proof will involve several steps. We would typically break them down into lemmas and “mini-lemmas”, but here we’ll simply include them as different parts of one proof.

Proof

Part 1: Let $\{I_n{\}}_{i=1}^{\mathrm{\infty }}$, where $I_i\subseteq I_{i+1}$ be an increasing sequence of ideals of $R$, then $J:=\bigcup _{i=1}^{\mathrm{\infty }}{I}_i$ is an ideal of $R$. (This result holds for an arbitrary ring)

Proof: Let $x$ and $y$ be in $J$, then there are indices $m$ and $n$, such that $x\in I_m$ and $y\in I_n$, so $x+y\in I_{max(m,n)}$, and thus $x+y\in J$. We can similarly show that for any $x\in J$ and $r\in R$, we have $rx\in J$. So part 1 holds.

Part 2: Since $R$ is a PID, any infinite increasing sequence of ideals, $\{I_i{\}}_{i=1}^{\mathrm{\infty }}$ will have an $N\in \mathbb{N}$, such that $j\ge N$ implies that $I_j=I_N$.

Proof: By the previous paragraph’s result, we know that $\bigcup _{i=1}^{\mathrm{\infty }}{I}_i$ is an ideal of $R$. Since $R$ is a PID, $\bigcup _{i=1}^{\mathrm{\infty }}=⟨x⟩$, for some $x\in R$. Then there must be an $N\in \mathbb{N}$, such that $x\in I_N$. This establishes part 2.

Part 3: Every non-zero, non-unit element of $R$ can be factored into irreducible elements.

Proof Suppose not, then let $r_0=r_1{y}_1$, where at least one of $r_1$ and $y_1$ is neither a unit nor irreducible. Without loss of generality, let’s let that be $y_1$. Then, we can repeat this process and express $y_1=r_2{y}_2$, where we can let $y_2$ be neither a unit nor irreducible. We can repeat this process arbitrarily often, so that we get

$$r_0=\left(\prod _{i=1}^{m+1}{r}_i\right)y_{m+1}$$

for any $m\in {\mathbb{N}}_{>0}$

but this generates a sequence of strictly increasing ideals, $\{I_m{\}}_{m=1}^{\mathrm{\infty }}$, where

$$I_m:=⟨\frac{r_0}{\prod _{i=1}^m{r}_i}⟩$$

which contradict part 2. This establishes part 3.

Part 4: Let $r\in R$ be irreducible, then $⟨r⟩\subseteq I$ implies either $I=⟨r⟩$ or $I=R$. (This means that $⟨r⟩$ is a maximal ideal).

Proof: Since $R$ is a PID, we know that $I=⟨x⟩$ for some $x\in R$. That means that $r=yx$, for some $y\in R$ (because $⟨r⟩\subseteq ⟨x⟩$). Since $r$ is irreducible, $x$ is either a unit or irreducible. If $x$ is a unit, then $⟨x⟩=R$. On the other hand, if $x$ is not a unit, then $y$ must be a unit, so $x=r{y}^{-1}$, which implies that $x\in ⟨r⟩$. This implies that $⟨x⟩=⟨r⟩$. This establishes part 4.

Part 5: Irreducible elements of $R$ are prime.

Proof: Suppose $r$ is an irreducible element of $R$ and that $r=xy$. Further, suppose that $r\nmid x$. Since $r\nmid x$, we know that $⟨x⟩⊈⟨r⟩$, so $⟨x,r⟩⊋⟨r⟩$. By part 4, this means that $⟨x,r⟩=R$, so we have

$$1=sx+tr$$

for some elements, $s,t\in R$. Multiplying through by $y$, we get

$$y=sxy+try$$

and since $r=xy$, this is equivalent to

$$y=sr+try$$

which means that

$$y=r(s+ty)$$

Thus, $r|y$ and $r$ is prime. This establishes part 5.

Since we’ve shown that every element of $R$ can be factored into primes, we have unique factorization.

QED

Theorem: A Euclidean Domain is a PID

Proof

Let $N:R\to {\mathbb{Z}}_{\ge 0}$ be the map, such that for any pair of non-zero elements, $a,b\in R$, we have $a=bq+r$, where $N(r)<N(b)$, for some $q$ and $r$ in $R$. We are guaranteed such a map, since $R$ is a Euclidean Domain

Let $I$ be an arbitrary ideal of $R$. Let $x$ be an element of $I$, such that

$$y\in I⟹N(x)\le N(y)$$

We claim that $I=⟨x⟩$. Suppose, for a contradiction, that $⟨x⟩⊊I$, and let $z\in I$, but $z\notin ⟨x⟩$. Then there are elements $q$ and $r\in R$, such that $z=qx+r$, and $N(r)<N(x)$. However, if $x\in I$ and $z\in I$, then $r=z-qx$ is also in $I$, but that’s impossible, since $N(r)<N(x)$. This contradicts the minimality of $N(x)$ in $I$.

QED

Combining the last two theorems, we see that every Euclidean Domain has unique factorization.

Letting $N:\mathbb{Z}\to {\mathbb{Z}}_{\ge 0}$, where $N(n)=|n|$, we immediately see that $\mathbb{Z}$ is a Euclidean Domain… Whew! It’s a good thing, too, because our implementation of the Euclidean Algorithm depended on that!

---

RSA Encryption Algorithm

We’re now going to take a slight detour for the remainder of this entry to discuss the RSA encryption algorithm. Don’t worry, we’ll actually develop a little bit more ring theory along the way.

It works by starting with two distinct prime numbers, let’s call them $p$ and $q$. Then we consider the ideal, $pq\mathbb{Z}$. That ideal is the kernel of a homomorphism,

$$\psi (n):=n\mathrm{mod}pq\mathbb{Z}$$

where $n$ represents an entire coset of the ideal. The image of $\psi$ is a finite ring of order $pq$, it is often written,

$$\mathbb{Z}/pq\mathbb{Z}$$

or more succinctly as ${\mathbb{Z}}_{pq}$. Since $\mathbb{Z}$ is commutative, $\mathbb{Z}/pq\mathbb{Z}$ is also commutative. However, it is not an integral domain. For example, notice that $\psi (p)$ and $\psi (q)$ are both zero divisors, since $\psi (p)\cdot \psi (q)$ is equal to

$$\begin{array}{rl}\psi (pq)& =\\ pq\mathrm{mod}pq\mathbb{Z}& =0\end{array}$$

So, clearly, not every element of $\mathbb{Z}/pq\mathbb{Z}$ is a unit. However, there are some units.

Let $x\in \mathbb{Z}/pq\mathbb{Z}$. We want to find a $y\in \mathbb{Z}/pq\mathbb{Z}$, such that $xy=1\in \mathbb{Z}/pq\mathbb{Z}$. Notice that if we use our Extended Euclidean Algorithm, and set $a=pq$ and $b=x$, then we get $s$, $t$, and $gcd(pq,x)$, where

$$s\cdot pq+t\cdot x=gcd(pq,x)$$

so, if $gcd(pq,x)=1$, then

$$t\cdot x\equiv 1\mathrm{mod}pq\mathbb{Z}$$

This means that $x$ is a unit exactly when $gcd(pq,x)=1$. We showed that the set of units of a ring is a group under multiplication. We’ll denote it, “$\mathcal{U}$.”

Let’s figure out how many elements there are in $\mathcal{U}$. We’ll do it by first counting all of the elements which aren’t units. Suppose $w\in \mathbb{Z}/pq\mathbb{Z}$ is not a unit. Then $gcd(w,pq)>1$, which means there are three possibilities.

1. $gcd(w,pq)=p$
2. $gcd(w,pq)=q$
3. $gcd(w,pq)=pq$

How many elements satisfy 1? The only possible elements are: $p$, $2p$, $3p$, …, $(q-1)p$. I.e. there are $q-1$ such elements.

A similar count shows that there are $p-1$ elements that satisfy 2.

There is exactly one element, $pq=0\mathrm{mod}pq\mathbb{Z}$ that satisfies 3.

Adding them all up, we have

$$\begin{array}{rl}& (p-1)+(q-1)+1\\ & =p+q-1\end{array}$$

non-units. Which means that everything else is a unit. I.e. there are

$$\begin{array}{rl}& pq-(p+q-1)\\ & =(p-1)(q-1)\end{array}$$

units. That is, $|\mathcal{U}|=(p-1)(q-1)$. This is a crucial calculation for the RSA algorithm.

Here’s how RSA works. There are two communicators, “Alice” and “Bob” (They’re pretty much always given those names).

1. Before they start communicating, Alice picks two “large” prime numbers, $p$ and $q$. Then she multiplies them together to get $N=pq$. She then calculates $m=(p-1)(q-1)$, and chooses a third number, $e$, such that $gcd(e,m)=1$ ($e$ needs to be larger than $1$. It can be fairly large, but doesn’t have to be absolutely huge). She also calculates $t$, such that

$$e\cdot t\equiv 1\mathrm{mod}m$$

with the extended euclidean algorithm. This means that

$$et=mk+1$$

for some integer, $k$.

2. She then publishes $N=pq$ and $e$. However, she keeps, $t$ and $m$ a secret!

If Bob wants to communicate a secret with Alice, he then somehow encodes it as a number, $c$, which should really be thought of as an element of $\mathbb{Z}/pq\mathbb{Z}$. This means that $0\le c<pq$. Then,

3. Bob then calculates $c^e\text{ mod }N$ and communicates it to Alice somehow.

4. Alice receives the message and computes

$$(c^e{)}^t\mathrm{mod}N$$

Let’s see what that gets her. Recall that $c\in \mathcal{U}$, the group of units of $\mathbb{Z}/pq\mathbb{Z}$. Therefore, $⟨c⟩$, the subgroup generated by $c$ (defined in an earlier entry) will have an order which divides the size of $\mathcal{U}$ by Lagrange’s Theorem.

Let’s call the order of $c\in \mathcal{U}$, $h$. We then have $h|m=|\mathcal{U}|$ (By Lagrange’s Theorem), so $hd=m$, for some integer, $d$. This means that

$$\begin{array}{rl}{c}^m& =c^{hd}\\ & =(c^h{)}^d\\ & =1^d\\ & =1\end{array}$$

which means that

$$\begin{array}{rl}(c^e{)}^t& =c^{et}\\ & =c^{mk+1}\\ & =c^{mk}\cdot c\\ & =(c^m{)}^k\cdot c\\ & =1^k\cdot c\\ & =c\end{array}$$

Thus, Alice get’s Bob’s message back!

There’s just one fairly large detail we haven’t addressed, and that is this: what happens if $t$ is huge? There’s a trick that can be used, and it’s Repeated Squaring. It allows Alice to calculate $(c^e{)}^t$ with roughly ${\log }_2(t)$ multiplications. We’ll cover it in the next entry. We’ll also go into more of the math of why RSA seems to be a good Public Key Encryption system for sending small payloads.

That’s all for this entry. Thanks for reading!!