Rings, Fields and Euler's Totient Function

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

Rings
In modular arithmetic we work modulo some modulus mmm
, and we can think of the numbers we are able to use this way as a group of numbers:
Z/mZ={0,1,2,...,m−1}\mathbb{Z}/m\mathbb{Z} = \{0,1,2,...,m-1\}Z/mZ={0,1,2,...,m−1}
​This ring Z/mZ\mathbb{Z}/m\mathbb{Z}Z/mZ
 is the ring of integers modulo m. We are able to add and multiply elements of this ring, then divide by mmm
 and take the remainder to obtain an element in Z/mZ\mathbb{Z}/m\mathbb{Z}Z/mZ
. There are general rules which define this as a ring, including the need for associative addition and multiplication.
Units of a Ring
As we discussed, a∈Z/mZa \in \mathbb{Z}/m\mathbb{Z}a∈Z/mZ
 has a modular multiplicative inverse if gcd(a,m)=1gcd(a,m)=1gcd(a,m)=1
. The set of all numbers with modular inverses are denoted as (Z/mZ)∗(\mathbb{Z}/m\mathbb{Z})^*(Z/mZ)∗
 - this is called the group of units modulo mmm
. Number which have inverses are called units. For example:
(Z/12Z)∗={1,5,7,11}(\mathbb{Z}/12\mathbb{Z})^* = \{1,5,7,11\}(Z/12Z)∗={1,5,7,11}
You can think of the group of units modulo 121212
 as essentially a set containing all numbers less than 121212
 which are coprime with it.
Fields
If every number in Z/mZ\mathbb{Z}/m\mathbb{Z}Z/mZ
 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 mmm
 where this are possible are values which are prime, which is why these fields are usually denoted Fp\mathbb{F}_pFp​
. 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 Fp\mathbb{F}_pFp​
.
Relevant Sets of Numbers
​Z\mathbb{Z}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 mmm
. Mathematically, this means:
ϕ(m)=#(Z/mZ)∗=#{0≤a<m:gcd(a,m)=1}\phi(m) = \#(\mathbb{Z}/m\mathbb{Z})^* = \#\{0 \leq a < m : gcd(a,m) = 1\}ϕ(m)=#(Z/mZ)∗=#{0≤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)=1gcd(p,q)=1gcd(p,q)=1
 then ϕ(pq)=ϕ(p)ϕ(q)\phi(pq)=\phi(p)\phi(q)ϕ(pq)=ϕ(p)ϕ(q)
.
Computing the Euler Totient
If we say that the prime factorisation of nnn
 is n=p1e1⋅p2e2⋅...⋅pkekn=p_1^{e_1} \cdot p_2^{e_2} \cdot ... \cdot p_k^{e_k} n=p1e1​​⋅p2e2​​⋅...⋅pkek​​
 then
ϕ(n)=n∏p∣n(1−1p)\phi(n) = n \prod_{p \mid n} (1-\frac{1}{p})ϕ(n)=np∣n∏​(1−p1​)
Note that if ppp
 is prime, ϕ(p)=p−1\phi (p) = p-1ϕ(p)=p−1
.
Proof
TODO
Euler's Formula
Euler's Formula states that if gcd(a,p)=1gcd(a,p)=1gcd(a,p)=1
 then​
aϕ(n)≡1mod  na^{\phi(n)} \equiv 1 \mod naϕ(n)≡1modn
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 ppp
, a case named after Fermat.
Fermat's Little Theorem
Since ϕ(p)=p−1\phi(p)=p-1ϕ(p)=p−1
​, Fermat's Little Theorem states that:
ap−1≡1mod  pa^{p-1} \equiv 1 \mod pap−1≡1modp
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 aaa
 in Fp\mathbb{F}_pFp​
:
ap−1≡1mod  pap−1⋅a−1≡1⋅a−1mod  pap−2≡a−1mod  pa^{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 ap−1≡1modpap−1⋅a−1≡1⋅a−1modpap−2≡a−1modp
​

Fundamentals - Previous

Modular Arithmetic

Next - Group Theory

Sets

Last modified 3mo ago