Euler and Möbius Arithmetic Functions and RSA Cryptography

This article illustrates the properties of the Euler and Möbius functions, which have great importance in Number Theory and in other fields. As an example of application we describe the RSA algorithm for public key cryptography.

---

1) Arithmetic functions

An arithmetic function \(f\) is a function with real or complex values ​​defined for all positive integers:

\[ f: \mathbb{N} \mapsto \mathbb{C} \]

An arithmetic function \(f(n)\) is called multiplicative if

\[ f(nm) = f(n)f(m) \quad \forall n,m \in \mathbb{N} \quad (n,m)=1 \]

It’s called completely multiplicative if the relation holds for all pairs of positive integers \(n,m\).

Example 1.1
The identity function \(I(n)\) is so defined:

\[ I(n) = \Bigl\lfloor \frac{1}{n} \Bigr\rfloor = \begin{cases} 1 & if \quad n = 1 \\ 0 & if \quad n > 1 \end{cases} \]

where the symbol with square brackets denotes the integer part of the fractional number. This function is clearly completely multiplicative.

On the set of arithmetic functions it’s possible to define a binary operation, called convolution or Dirichlet product. Given two arithmetic functions \(f,g\) the convolution, denoted with the symbol \(f*g\), is defined as follows:

\[ (f*g)(n) = \sum_{d|n}f(d)g\left(\frac{n}d\right) = \sum_{d|n}f\left(\frac{n}d\right)g(d) \]

where the summation is taken on all the divisors of \(n\).
The following properties are easily proved:

\[ \begin{array}{l} f*g = g*f \\ (f*g)*h = f*(g*h) \\ \end{array} \]

Exercise 1.1
Prove that the convolution \(f*g\) is a multiplicative function if the functions \(f,g\) are multiplicative.

Exercise 1.2
Prove that, for every arithmetic function \(f\), we have:

\[ I*f = f*I = f \]

that is, the identity function is a neutral element with respect to convolution.

---

2) Euler’s totient function \(\varphi(n)\)

If \(n\) is a positive integer, the Euler function, denoted with \( \varphi(n)\), counts the number of positive integers between \(1\) and \(n\) which are relatively prime with \(n\). In symbols:

\[ \varphi (n) = |\{x\in \mathbb{N} \mid 1\leq x\leq n, (x,n)=1\}| \]

where the symbol \(|A|\) denotes the number of elements (or cardinality) of the set \(A\).
The first values ​​of the function are

\[ \begin{array}{l} \varphi (1)=1,\varphi (2)=1,\varphi (3)=2,\varphi (4)=2 \\ \end{array} \]

To analyze the values ​​assumed by the Euler function with the SageMath environment we can use the euler_phi(n) function.

If \(p\) is a prime number we have

\[ \varphi(p)= p-1 \]

If \(n=p^{a}\), with \(a \in \mathbb{N}\), then

\[ \varphi(p^{a})= p^{a} – p^{a-1} \]

To prove this it’s enough to observe that among the natural numbers included between \(1\) and \(p^{a}\), those not prime with \(p^{a}\) are only the multiples of \(p\), that is \(\{p, 2p, \cdots ,p^{a-1}p\}\) .

In the general case the following theorem holds:

Theorem 2.1
If \(n=p_1^{a_1}\cdots p_k^{a_k}\), then

\[ \varphi(n)=\prod_{i=1}^kp_i^{a_i-1}(p_i-1) = n \cdot \prod_{p \vert n} \left( 1- \frac{1}{p}\right) \]

Proof
To prove the theorem we will use the principle of inclusion-exclusion. Let us first observe that the number of positive integers less or equal to \(n\) and divisible by a positive integer \(a\) is \(\Bigl\lfloor \frac{n}{a}\Bigr\rfloor\), that is the integer part of the division; if \(a,b\) are relatively prime, the number of positive integers less than or equal to \(n\), divisible both by \(a\) and \(b\), is \(\Bigl\lfloor \frac{n}{ab}\Bigr\rfloor\), and so on. Applying the inclusion-exclusion principle we obtain the following formula:

\[ \begin{array}{l} \varphi(n)= n – \frac{n}{p_{1}} -\frac{n}{p_{2}} – \cdots -\frac{n}{p_{k}} \\ +\frac{n}{p_{1}p_{2}} +\frac{n}{p_{1}p_{3}} + \cdots +\frac{n}{p_{k-1}p_{k}} \\ \vdots \\ +(-1)^{k}\frac{n}{p_{1}p_{2}\cdots p_{k}} \\ = n(1-\frac{1}{p_{1}})(1-\frac{1}{p_{2}}) \cdots (1-\frac{1}{p_{k}}) \\ =n \prod\limits_{i=1}^{k}\left (1- \frac{1}{p_{i}}\right) \end{array} \]

From the formula you can easily see that for \(n \ge 3\) the Euler function is always even.
Another consequence is the following property:

Theorem 2.2
The function \(\varphi\) is multiplicative. That is:

\[ \varphi(nm) = \varphi(n) \varphi(m) \quad \forall n,m \in \mathbb{N} \mid (n,m)=1 \\ \]

Theorem 2.3 – Euler
Let \(n\) be a positive integer and \(a\) an integer prime with \(n\). Then the following formula applies:

\[ a^{\varphi(n)}\equiv 1 \pmod{n} \]

As a special case we have the small Fermat Theorem:

\[ a^{p-1}\equiv 1 \pmod{p} \]

Proof
Let \(\{a_{1}, \cdots a_{\varphi(n)}\}\) be a reduced residue system modulo \(n\). Then also the set \(\{ aa_{1}, \cdots aa_{\varphi(n)}\}\) is a reduced residue system modulo \(n\). Multiplying all the elements we have:

\[ \begin{split} a_{1} \cdots a_{\varphi(n)} \equiv (a \cdot a_{1}) \cdots (a \cdot a_{\varphi(n)}) \equiv \\ a^{\varphi(n)} a_{1} \cdots a_{\varphi(n)} \pmod{n} \end{split} \]

We can delete all the factors \(a_{i}\) because \((a_{i},n)=1\), and so we have the desired result.

Exercise 2.1
Prove that if \(m|n\) then \(\varphi(m) | \varphi(n)\) .

Exercise 2.2
Prove that \(\varphi(n) \le 5\) if and only if \(n \in \{1,2,3,4,5,6,8,10,12\}\).

Theorem 2.4
Prove that for every positive integer \(N\) there is at most a finite number of integers \(n\) such that \(\varphi(n) = N\) .
From this, prove that the function \(\varphi(n)\) tends to infinity when \(n\) tends to infinity.

Hint
Let’s fix a positive integer \(K\) and suppose that \(n > (K!)^{K}\). Then the number \(n\) is divisible by a prime number \(p >K\) , or by \(p^{K+1}\) for some prime. In the first case we have

\[ \varphi(n) \ge \varphi(p)=p-1 \ge K \]

while in the second case we have

\[ \varphi(n) \ge \varphi(p^{K+1})= p^{K}(p-1) \ge p^{K} > K \]

So, in any case, if \(n> (K!)^{K}\) then \(\varphi(n) \ge K\), thus proving the theorem.

To deepen the study of the Euler function we can see ^[1] or ^[2].

---

3) Möbius function

The Möbius function \(\mu(n)\) is defined as follows:

\[ \mu(n)= \begin{cases} (-1)^{k} &\mbox{if } n=\prod_{i=1}^{k} p_{i} \\ 0 &\mbox{ otherwise} \end{cases} \]

The function \(\mu(n)\) therefore is equal to zero if the number is not a square-free positive integer. The following theorem directly follows from the definition.

Theorem 3.1
The function \(\mu(n)\) is multiplicative.

Theorem 3.2
If \(n \ge 1\) we have:

\[ \sum_{d|n} \mu(d) = \Bigl\lfloor \frac{1}{n} \Bigr\rfloor = \begin{cases} 1 & if \quad n = 1 \\ 0 & if \quad n > 1 \end{cases} \]

Proof
The theorem is true for \(n=1\). Suppose now \(n \gt 1\) and \( n=p_1^{a_1}\cdots p_k^{a_k}\) .From the definition of the function \(\mu(n)\), we have

\[ \begin{split} \sum_{d|n} \mu(d) &= \mu(1) + \mu(p_{1})+ \cdots \mu(p_{k}) \\ &+ \mu(p_{1}p_{2})+ \cdots + \mu(p_{k-1}p_{k}) \\ & \vdots \\ &+ \mu(p_{1}p_{2} \cdots p_{k}) \\ &=\sum_{i=0}^{k}\binom{k}{i} (-1)^{i}=0 \end{split} \]

for Newton’s binomial theorem.

Theorem 3.3

\[ \sum_{d|n}|\mu(d)|=2^{k} \]

The proof is similar to the previous one.

Theorem 3.4

\[ \varphi(n)=n \sum_{d|n} \frac{\mu (d)}{d} \]

Proof
The proof easily follows from theorem 2.1 and the properties of the Möbius function.

Theorem 3.5
If \(f(n)\) is a multiplicative function, so is the function

\[ g(n)=\sum_{d|n} f(d) \]

Proof
If \((n,m)=1,\ d|n,\ D|m\), then \((d,D)=1\) and the product \(c=dD\) takes the values ​​of all divisors of \(nm\). Then

\[ \begin{split} g(nm)= \sum_{c|nm} f(c)= \sum_{d|n,D|m} f(dD)= \\ \sum_{d|n} f(d) \sum_{D|m} f(D)= g(n) g(m) \end{split} \]

---

4) Möbius inversion formula

Theorem 4.1
Let \(f,g \colon \mathbb{N} \to \mathbb{R}\) be two arithmetic functions. If

\[ f(n)=\sum_{d|n}g(d) \hspace{5 mm} \forall n\geq 1. \]

then the following inversion formula applies:

\[ g(n)=\sum_{d|n} \mu(d) f\left(\frac{n}{d}\right). \]

Proof

\[ \begin{split} &\sum_{d|n} \mu(d) f\left(\frac{n}{d}\right)= \sum_{d|n} \mu(d)\sum_{c|\frac{n}{d}}g(c)=\sum_{cd|n} \mu(d)g(c)= \\ &\sum_{c|n} g(c) \sum_{d|\frac{n}{c}}\mu(d) \end{split} \]

The internal sum is equal to \(1\) if \( \frac{n}{c}=1\) , otherwise it’s equal to \(0\). So the expression is equal to \(f(n)\).

The following inverse theorem is also valid:

Theorem 4.2
If \(n=p_1^{a_1}\cdots p_k^{a_k}\) and

\[ g(n)=\sum_{d|n} \mu(d) f\left(\frac{n}{d}\right). \]

then

\[ f(n)=\sum_{d|n}g(d) \hspace{5 mm} \forall n\geq 1 \]

The proof is similar to the previous one.

Putting together theorem 3.4 and theorem 4.2 we immediately obtain the following formula:

Theorem 4.3

\[ \sum_{d|n} \varphi(d) = n \]

Exercise 4.1
If \(n=p_1^{a_1}\cdots p_k^{a_k}\) prove the following formula:

\[ \sum_{d|n} \frac{\varphi(d)}{d} = \prod_{i=1}^{k} \left(1+ a_{i}\left(1- \frac{1}{p_{i}}\right)\right) \]

Exercise 4.2
Prove the following formula:

\[ \sum_{d|n} \mu(d) \varphi(d) = 0 \Longleftrightarrow \mbox{n is even} \]

Exercise 4.3
If \(f(n)\) is a multiplicative function, prove that

\[ \sum_{d|n} \mu(d) f(d) = \prod_{p|n} (1-f(p) \]

Exercise 4.4

\[ \sum_{d|n} \mu(d) \varphi(d) = \prod_{p|n} (2-p) \]

---

5) Relationship with Riemann’s hypothesis (Nicolas criterion)

The Euler function has several connections with the Riemann zeta function. In particular, an important relation with the Riemann hypothesis on the zeros of the zeta function is given by the following theorem.

Theorem 5.1 – Jean-Louis Nicolas
If the Riemann hypothesis is true, then the following relation holds:

\[ \frac {N_{k}}{\varphi (N_{k})} > e^{\gamma} \log \log N_{k} \]

where \( \gamma \approx 0.577\) is the Euler-Mascheroni constant and \( N_{k}= \prod_ {i=1}^{k} p_{i}= 2 \cdot 3 \cdot 5 \cdots p_{k}\) is the primorial of order \(k\) , that is the product of the first \(k\) prime numbers (the name is analogous to the factorial).
Conversely, if the Riemann hypothesis is false, then the relation described above is valid for infinite other values ​​of \(k\) and is not verified for infinite values of \(k\) .
So a possible strategy to prove Riemann’s hypothesis is to prove the validity of the relation from a certain positive integer \(k\) onwards.

To learn more about Nicolas’s criterion, see ^[3]. To study the Riemann zeta function an excellent text is ^[4].

---

6) RSA encryption algorithm

The RSA algorithm, introduced in 1978 by Rivest, Shamir and Adleman, is currently the most widely used public and private key cryptography system. It can be used both to encrypt data and to manage digital signatures. It’s considered safe, at present, if fairly long keys (at least 1024 bits) are used. Its security is based on the difficulty of factorizing very large integers.

6.1) Chinese remainder theorem

Before describing the RSA algorithm it is useful to remember the following theorem, which plays an important role in proving the correctness of the algorithm itself.

Theorem 6.1 – Chinese remainder theorem
Consider the system of two linear equations to congruences:

\[ \begin{cases} x \equiv a_{1} \pmod {m_{1}} \\ x \equiv a_{2} \pmod {m_{2}} \end{cases} \]

If \( m_{1},m_{2}\) are two relatively prime positive integers and \(a_{1},a_{2}\) are integers, then the system has a solution \(\pmod {m_{1}m_{2}}\). If \(x_{0}\) is a solution, then so are the integers \(x=x_{0} + k m_{1}m_{2},\ k \in \mathbb{Z}\).
The theorem can be easily extended to the case of a system of \(n\) equations, with \(n \gt 2\).
For a proof see one of the texts referenced in the bibliography.

Exercise 6.1
Solve the following system:

\[ \begin{cases} x \equiv 4 \pmod {5} \\ x \equiv 3 \pmod {7} \end{cases} \]

Answer: \(x= 24 + 35k\)

6.2) RSA algorithm

The basic scheme of the RSA procedure is as follows:

• given two subjects, A and B, each chooses a pair of very large prime numbers, which are kept secret
• subject A uses his pair of primes \( p_{a},q_{a}\) and compute \(n_{a}=p_{a} q_{a}\). We note that \(\varphi(n_{a})=(p_{a}-1)(q_{a}-1)\).
• using a random number generation algorithm, a number \(e_{a}\) is computed such that \(1 < e_{a} < \varphi(n_{a})\) and that is also prime with \(\varphi (n_{a})\).
• then compute \(d_{a}\), the inverse of \(e_{a}\) modulo \(\varphi(n_{a})\).

Ultimately, the numbers available to subject A are as follows:

\[ \begin{cases} n_{a}=p_{a} q_{a} \\ e_{a} \quad \text{ with } \quad (e_{a},\varphi(n_{a}))=1 \\ d_{a}= e_{a}^{-1} \mod {\varphi(n_{a})} \end{cases} \]

The same procedure is performed by the subject B.
The public key of subject A is the pair of numbers

\[ K(E,A) = (n_{a},e_{a}) \]

which is made public and accessible to the outside world. The private key of subject A is the pair

\[ K(D,A) = (n_{a},d_{a}) \]

The public key of subject B is the pair of numbers

\[ K(E,B) = (n_{b},e_{b}) \]

which is made public and accessible to the outside world. The private key is the pair

\[ K(D,B) = (n_{b},d_{b}) \]

6.2.1) Message encryption

The following diagram summarizes the operations of the RSA procedure:

The message to be encrypted is represented with an integer \(m \lt n\). If the integer is greater than \(n\), the message is decomposed into a set of smaller separate messages. Another condition is that the integer \(m\) must be prime with \(n\). However, this is an unlikely event as if \(n=pq\) there are only \(p+q-1\) smaller integers that are not prime with \(n\) , that is the numbers \(1,p,2p, \cdots (q-1)p,q,2q, \cdots (p-1)q\) ; the probability is:

\[ \frac{p+q-1}{pq} \approx 1/p+1/q \]

If the primes \(p,q\) are very large, this probability is very small. So, to encrypt a message \(m\) that A sends to B, the public key of B is used through the following function:

\[ c \equiv m^{e_{b}}\pmod {n_{b}} \]

6.2.2) Message decryption

To decrypt the encrypted message \(c\), subject B uses the inverse function with his private key.

Theorem 6.2

\[ c^{d_{b}} \equiv m \pmod{n_{b}} \]

Proof
In the proof, we will skip the index \(b\) for simplicity.

\[ \begin{array}{l} c^{d} = (m^{e}\bmod{n})^{d}\bmod{n} \equiv{m}^{ed} \bmod{n} \\ = m^{1+k\varphi(n)} = m\cdot (m^{\varphi(n)})^{k} \bmod{n} \\ \equiv m\cdot 1 = {m} \bmod{n} \end{array} \]

We have applied the Euler theorem, thanks to the hypothesis that \(m\) is prime with \(n\).

Exercise 6.2
We apply the algorithm in the following case:

\[ p=11,q=3, n= 33, \varphi (33)=20 \]

We choose e=3 and compute \(ed \equiv 1 \pmod {20}\) . It’s easily found that \(d=7\). So, the public key is \(K_{3}= (33,3)\) while the private key is \(K_{7} = (33,7)\).
Now, to encrypt a plain message \(P=5\), we compute \(C \equiv 5^{3} \pmod{33} = 26\). To do the reverse operation and obtain the unencrypted message, we compute \(P \equiv 26^{7} \pmod {33} =5\).

---

7) Digital signature

The RSA procedure described above has some security problems. A good encryption system must guarantee, in addition to data security and confidentiality, also the authenticity of the user who transmits the message. This can be achieved through a digital signature procedure that uses the RSA protocol.
Without going into details, we add another small message, encrypted with the sender’s private key, to the message encrypted with the recipient’s public key. The receiver, before decoding the message with his private key, performs an authenticity verification operation using the sender’s public key. If the verification is successful, it then proceeds to decrypt the message with its own private key.
The following diagram illustrates the main operations:

8) RSA security

The security of the RSA system is based on the difficulty of computing the prime factors of very large numbers. In the period 1993-1994, using about 600 computers for 6 months, it was possible to decrypt the RSA code that used \(129\)-digit numbers. This forced to increase the length of the keys.
In the current state of mathematics the factoring of numbers of a thousand digits is practically impossible, except in some very specific cases. However, the progress of mathematics and the availability of more and more powerful computers used in parallel make it clear that the RSA procedure will have to use even larger numbers to ensure security. For an in-depth study of the mathematics of cryptographic schemes see ^[5].

---

9) Exercises

Exercise 9.1
Prove that \(\varphi(n) \ge \frac{\sqrt{n}}{2}\).

Hint
Use the following inequalities:

\[ \begin{array}{l} (p-1) > \sqrt{p} \quad (p \ge 3) \\ (n – \frac{1}{2}) \ge \frac{n}{2} \\ \end{array} \]

Exercise 9.2
Let \(n\) be a perfect even number. Show that the integer \(n-\varphi(n)\) is the square of an integer.

Hint
Remember that a perfect even number is an integer of the form \(n=2^{p-1}(2^{p}-1)\), where \(p\) is a prime number and the number \((2^{p}-1)\) is prime too.

Exercise 9.3
Find infinite integer numbers \(n\) such that \(100 | \varphi(n)\).

Exercise 9.4
Characterize the positive integers \(n\) for which the relationship applies:

\[ \varphi(n)=\varphi(2n) \]

Exercise 9.5
If \((a,b)=d\), then

\[ \varphi(ab) = \frac{d\varphi(a)\varphi(b)}{\varphi(d)} \]

Exercise 9.6
We define the Jordan function \(J_{k}(n)\) , which is a generalization of the Euler function \( J_{1}(n)=\varphi(n) \):

\[ J_{k}(n)= n^{k} \cdot \prod_{p \vert n} \left( 1- \frac{1}{p^{k}}\right) \]

For each integer \( k \ge 1\) , prove that \(J_{k}(n)\) is equal to the number of \((k + 1)\)-uples of integers \(\{x_{1}, \cdots x_{k},n\}\) whose maximum common divisor is equal to \(1\).

---

Bibliography

^[1]Niven, Zuckerman, Montgomery – An introduction to the Theory of Numbers (Wiley)

^[2]Hardy, Wright – An introduction to the Theory of Numbers, V edition (Oxford, 1979)

^[3]Jean-Louis Nicolas – Small values of the Euler function and the Riemann hypothesis (ACTA ARITHMETICA 155.3, 2012)

^[4] H. Edwards – Riemann’s zeta Function (Dover)

^[5] N. Koblitz – A Course in Number Theory and Cryptography (Springer)