Euler's Totient Theorem

  At its core lies Euler’s Totient Function, denoted $\varphi (n)$, which counts the integers up to $n$ that are coprime with $n$. This seemingly simple concept has profound implications, ranging from pure mathematics to cryptography.

Key Concepts in Euler's Totient Theorem

1. Definition of $\varphi (n)$:

The totient function $\varphi (n)$ is defined as:

$$\varphi (n)=\text{Number of integers }k\text{ such that }1\le k\le n\text{ and }\text{gcd}(k,n)=1.$$

Example:

For $n=12$:

$$\begin{gathered} 1,\cancel{2},\cancel{3},\cancel{4},5,\cancel{6},7,\cancel{8},\cancel{9},\cancel{10},11. \\ \text{Coprime integers: }[1,5,7,11] \end{gathered}$$

Thus, $\varphi (12)=4$.

What happens with prime numbers?

Prime numbers has only one prime factor: itself!

Example

For $n=5$:

$$\begin{gathered} 1,2,3,4,\cancel{5}. \\ \text{Coprime integers: }[1,2,3,4] \end{gathered}$$

Thus, $\varphi (5)=4$.

This is generally true of all prime numbers:

$$\begin{gathered} \varphi (p)=p-1 \\ \text{where p is a prime number} \end{gathered}$$

We have our first timesaver.

2. Multiplicative Property:

If $m$ and $n$ are coprime ($\text{gcd}(m,n)=1$), then:

$$\varphi (mn)=\varphi (m)\cdot \varphi (n).$$

Example:

For $m=5,n=6$:

$$\begin{gathered} \varphi (5)=4, \\ \varphi (6)=2, \\ \varphi (30)=\varphi (5)\cdot \varphi (6)=4\cdot 2=8. \end{gathered}$$

3. Prime Factorization Formula:

For $n=p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_k^{{\alpha }_k}$:

$$\varphi (n)=n\cdot \prod _{i=1}^k\left(1-\frac{1}{p_i}\right)$$

Example:

For $n=60=2^2\cdot 3\cdot 5$:

$$\varphi (60)=60\cdot \left(1-\frac{1}{2}\right)\cdot \left(1-\frac{1}{3}\right)\cdot \left(1-\frac{1}{5}\right),$$

$$\varphi (60)=60\cdot \frac{1}{2}\cdot \frac{2}{3}\cdot \frac{4}{5}=16.$$

Applications of Euler's Totient Theorem

1. Primality Testing:

For a prime $p$:

$$\varphi (p)=p-1.$$

This property aids in testing whether a number is prime.

2. RSA Encryption:

RSA relies on the totient function to generate keys:

• Let $n=p\cdot q$, where $p,q$ are primes. $$\varphi (n)=(p-1)(q-1).$$

Example: For $p=11,q=13$:

$$\begin{gathered} n=143, \\ \varphi (143)=10\cdot 12=120. \end{gathered}$$

Public and private keys are derived using $\varphi (n)$, ensuring secure encryption.

3. Applications in Modular Arithmetic and Prime Numbers:

a) Efficient Exponentiation:

Using the property $a^{\varphi (n)}\equiv 1(\mathrm{mod}n)$ for $a$ coprime to $n$, large powers modulo $n$ can be computed efficiently.

Example: Calculate $7^{100}(\mathrm{mod}12)$:

1. Since $\varphi (12)=4$, $7^4\equiv 1(\mathrm{mod}12)$.
2. Break $100$ into $4\cdot 25$: $7^{100}=(7^4{)}^{25}\equiv 1^{25}\equiv 1(\mathrm{mod}12)$.

b) Properties of Primes in Modular Arithmetic:

Prime numbers simplify modular inverses, as every nonzero element in ${\mathbb{Z}}_p$ is coprime to $p$.

Example: Modular Inverses:

Find the modular inverse of $3(\mathrm{mod}7)$:

1. $\varphi (7)=6$, so $3^6\equiv 1(\mathrm{mod}7)$.
2. Use powers to find $3\cdot x\equiv 1(\mathrm{mod}7)$: $$3\cdot 5\equiv 15\equiv 1(\mathrm{mod}7).$$ Thus, $5$ is the modular inverse of $3$ under mod $7$.

  Euler's Totient Theorem stands as a testament to the interplay between theory and application, bridging the gap between abstract mathematics and real-world cryptography. Its elegance and utility continue to inspire mathematicians and engineers alike.