# Rings, Fields and Euler's Totient Function

The basics of Rings, Fields and Euler's Phi Function

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, including the need for associative addition and multiplication.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.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$

.

$\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 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.

If

$gcd(p,q)=1$

then $\phi(pq)=\phi(p)\phi(q)$

.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$

.TODO

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.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$

Last modified 3mo ago