6.11.3. Euler’s Function and Euler’s Theorem

6.11.3.1. Euler’s Function (φ(n))

Euler’s function determines the count of positive integers less than a given positive integer n that are coprime with n. More technically, φ(n) counts the positive integers from 1 to n that have no common divisors with n other than 1.

Formally:

• φ(1) = 1: Only the number 1 is coprime with 1.
• If n is a prime number: φ(n) = n – 1. All positive integers less than a prime number n are coprime with it.
• If n = p^k where p is a prime number and k is a positive integer: φ(p^k) = p^k – p^k-1 = p^k(1 – 1/p).

This is because all multiples of p share a common factor with p^k.

Additionally, φ is a multiplicative function, meaning if m and n are coprime:

φ(m ⋅ n) = φ(m) ⋅ φ(n)

Example:

φ(9): The positive integers less than 9 that are coprime with it are: 1, 2, 4, 5, 7, 8. Being coprime means their greatest common divisor with 9 is 1. Therefore, φ(9) = 6.

6.11.3.2. Euler’s Theorem

Euler’s theorem is an important principle in modular arithmetic, expressed as:

a^φ(n) ≡ 1 (mod n)

Where:

• a and n are coprime (i.e., gcd(a, n) = 1).
• φ(n) is Euler’s function of n.

This theorem states that when raised to the power φ(n), a becomes a modular unit with respect to n.

Example:

φ(10) =

6.11.4. Period-Finding Problem

Period finding is one of the most critical steps in the quantum part of Shor’s algorithm. This step aims to identify the repeating behavior of a given function. The period of a function is the smallest positive integer at which the function begins to repeat its behavior.

Mathematically, the period r is defined as:

For a function f(x), the period r satisfies:

f(x + r) = f(x)

In Shor’s algorithm, for a number N to be factorized, a base a is selected, and the period r of the function a^x mod N is determined.

Example:

Let N = 15, a = 7.

The function is defined as f(x) = 7^x mod 15.

Calculations:

• f(0) = 1 mod 15
• f(1) = 7 mod 15
• f(2) = 4 mod 15
• f(3) = 13 mod 15
• f(4) = 1 mod 15

Here, the period r is found to be 4. This period information is used in the factorization step to determine the prime factors of the number.