Motivation§

The Totient function is used in cryptosystems like RSA and is useful in computing number theoretic problems.

Euler’s Totient Function§

Euler’s Totient Function

Euler’s totient function is typically denoted using $\varphi(x)$, defined as

$$ \varphi(n) = \vert{0 \leq k \lt n : (k, n) = 1}\vert. $$

Or, $\varphi(n)$ is the number of non-negative numbers strictly less than $n$ that are co-prime with $n$.

Properties:

  • If $p \in \mathbb{P}$, then $\varphi\left(p\right) = p-1$
  • If $p \in \mathbb{P}$, then $\varphi\left(p^k\right) = p^{k-1}(p-1)$
    • In the case that $p = 2$, it simply becomes $p^{k-1}$. This fact is useful in implementing the Totient function as it allows us to use bit operations.
  • If $p, q \in \mathbb{N}$ and $(p, q) = 1$, then $\varphi(pq) = \varphi(p)\cdot\varphi(q)$ (multiplicative)

Multiplicative Property

To reiterate: If $p, q \in \mathbb{N}$ and $(p, q) = 1$, then

$$ \varphi(pq) = \varphi(p)\cdot\varphi(q). $$

Any number $a \in \mathbb{N}$ can be written as a factorization of $m$ primes,

$$ a = \prod_{i = 0}^{m} q_i^{e_i}. $$

Then, $\varphi(a)$ can be computed as:

$$ \begin{align*} \varphi(a) &= \prod_{i = 0}^{m} \varphi\left(q_i^{e_i}\right)\\ &= \prod_{i = 0}^{m} \left[(q_i)^{e_i - 1}(q_i - 1)\right] \end{align*} $$

Euler’s Theorem§

The following lemma is used in the proof of Euler’s theorem.

Lemma 5.1

If $(a, b) = 1$ and $(b, c) = 1$, then $(ac, b) = 1$.

Sketch: Write all three numbers in terms of their prime factorization and observe that $ac$ shares no common prime factors with $b$.

Euler’s Theorem

Let $(a, n) = 1$, then

$$ a^{\varphi(n)} \equiv_n 1. $$

Consider the numbers $ka \pmod{n}$ where $(k, n) = 1$ and $1 \leq k \lt n$. If $ja \equiv_n ka$, then another way to say this is $n \vert (j-k)a$. Since $(a, n) = 1$, we get that $n \vert (j - k)$, which means $j - k = 0$, so $j$ must equal $k$. Hence, the elements in the sequence given by:

$$ ka \pmod{n}, \text{ where } (k, n) = 1 \text{ and } 1 \leq k \lt n, $$

are all distinct, meaning

$$ \prod_{(j,n) = 1} ka \equiv_n \prod_{(l, n) = 1} l $$

for $l, j \in [0\dots n)$, since each element $ja$ is congruent to a remainder $l$ with $(l, n) = 1$.

Notice that the left hand side is just $\left(\prod_{(j,n)=1} l\right)a^{\varphi(n)}$. Since each term in the product is coprime with $n$, we can cancel $\prod_{(j,n)=1} l$ from both sides and obtain

$$ a^{\varphi(n)} \equiv_n 1. $$

Fermat’s Little Theorem

In the specific case of Euler’s theorem where $p$ is prime, we get that

$$ a^{p-1} \equiv 1 \pmod{p}. $$

One example of Euler’s theorem being applied is in exponentation:

$$ g^x \pmod{n} $$

in cases where $x > \varphi(n)$, we can reduce this problem to be

$$ g^{x} \equiv g^{(x \mod{\varphi(n)})} \pmod{n}. $$

Furthermore, we can observe that:

$$ g^{(a^b)} \equiv g^{\left((a \mod{\varphi(n)})^{(b \mod{\varphi(\varphi(n))})}\right)} \pmod{n}. $$

Carmichael’s Totient Function§

We didn’t talk about the Carmichael function in our MATH-470, however, this becomes useful in discussing the RSA algorithm.

Carmichael’s Totient Function

Carmichael’s totient uses the notation $\lambda(n)$, and is defined to be the smallest positive integer $m$ satisfying

$$ a^{m} \equiv 1 \pmod{n}, $$

for all $a \in [1\dots n)$ such that $(a, n) = 1$.

Computing the Carmichael Function§

Using results from Carmichael’s theorem, we can find that $\lambda(n)$ can be computed in terms of Euler’s totient function.

$$ \lambda\left(p^r\right) = \begin{cases} \varphi\left(p^r\right) & \text{if } p \in \mathbb{P}, \text{or } p = 4\\ \frac{1}{2}\varphi\left(p^r\right) & \text{if } p = 2 \text{ and } r \geq 3 \end{cases} $$