# Rings, Fields and Euler's Totient Function

## Rings

In modular arithmetic we work modulo some modulus $$m$$, and we can think of the numbers we are able to use this way as a group of numbers:

$$
\mathbb{Z}/m\mathbb{Z} = {0,1,2,...,m-1}
$$

​This ring $$\mathbb{Z}/m\mathbb{Z}$$ is the *ring of integers modulo m*. We are able to add and multiply elements of this ring, then divide by $$m$$ and take the remainder to obtain an element in $$\mathbb{Z}/m\mathbb{Z}$$. There are [general rules which define this as a ring](https://www.britannica.com/science/ring-mathematics), including the need for associative addition and multiplication.

### Units of a Ring

As we discussed, $$a \in \mathbb{Z}/m\mathbb{Z}$$ has a modular multiplicative inverse if $$gcd(a,m)=1$$. The set of all numbers with modular inverses are denoted as $$(\mathbb{Z}/m\mathbb{Z})^\*$$ - this is called the *group of units modulo* $$m$$. Number which have inverses are called **units**. For example:

$$
(\mathbb{Z}/12\mathbb{Z})^\* = {1,5,7,11}
$$

You can think of the group of units modulo $$12$$ as essentially a set containing all numbers less than $$12$$ which are coprime with it.

## Fields

If every number in $$\mathbb{Z}/m\mathbb{Z}$$ has a modular inverse, it is promoted from a **ring** to a **field** (a field is a ring in which division is possible). Note that the only values of $$m$$ where this are possible are values which are prime, which is why these fields are usually denoted $$\mathbb{F}\_p$$. A **finite field** (also called a **Galois field**) is a field with a finite number of elements, such as those used in modular arithmetic. As a result, the term finite field will come up quite often to describe $$\mathbb{F}\_p$$.

### Relevant Sets of Numbers

$$\mathbb{Z}$$ denotes the **ring of integers** - note it is not a field, as there are no fractions to provide inverses.

## Euler's Totient Function

Euler's totient function returns the number of elements in the group of units modulo $$m$$. Mathematically, this means:

$$
\phi(m) = #(\mathbb{Z}/m\mathbb{Z})^\* = #{0 \leq a < m : gcd(a,m) = 1}
$$

​This function has a huge array of applications and further rules which allow us to do some pretty awesome things, and is a key piece of the RSA cryptosystem.

### Totient Rules

If $$gcd(p,q)=1$$ then $$\phi(pq)=\phi(p)\phi(q)$$.

### Computing the Euler Totient

If we say that the prime factorisation of $$n$$ is $$n=p\_1^{e\_1} \cdot p\_2^{e\_2} \cdot ... \cdot p\_k^{e\_k}$$ then

$$
\phi(n) = n \prod\_{p \mid n} (1-\frac{1}{p})
$$

Note that if $$p$$ is prime, $$\phi (p) = p-1$$.

#### Proof

TODO

### Euler's Formula

Euler's Formula states that if $$gcd(a,p)=1$$ then​

$$
a^{\phi(n)} \equiv 1 \mod n
$$

This is perhaps the most important formula for the RSA cryptosystem, which we will get to soon.​ Note that this actually tells us a little more in the case modulo a prime $$p$$, a case named after Fermat.

### Fermat's Little Theorem

Since $$\phi(p)=p-1$$​, Fermat's Little Theorem states that:

$$
a^{p-1} \equiv 1 \mod p
$$

This was stated by Fermat over 100 years before Euler's Formula. You may note that this also gives us a quick way to compute the **modular multiplicative inverse** of $$a$$ in $$\mathbb{F}\_p$$:

$$
a^{p-1} \equiv 1 \mod p \\
a^{p-1} \cdot a^{-1} \equiv 1 \cdot a^{-1} \mod p \\
a^{p-2} \equiv a^{-1} \mod p
$$