Number Theory: Introduction to Euler's Totient Function PDF

Number Theory: Introduction to Euler’s Totient Function Cathal Stephens and Roonak Thapa May 21 2023 1 Introduction Number theory is the study of relationships and properties of numbers. We learned about and worked with prime...

Number Theory: Introduction to Euler’s Totient Function Cathal Stephens and Roonak Thapa May 21 2023 1 Introduction Number theory is the study of relationships and properties of numbers. We learned about and worked with prime numbers and congruence relations in our study of number theory. This paper focuses on topics from Ivan Niven, Herbert S. Zuckerman, and Hugh L. Montgomery’s An Introduction to The Theory of Numbers. In particular, the totient function. Swiss mathematician Leonhard Euler contributed much to the study of prime numbers. Euler’s contributions to number theory are still studied and used today, making him one of the most influential mathematicians in history. One of these contributions was Euler’s φ-function, also known as the totient function. In reading An Introduction to The Theory of Numbers, one is exposed to the number theory in stages. As we worked through the text, we found the section on congruences and moduli particularly fascinating. The totient function beau- tifully integrates previous topics, such as primes and divisibility, while forming an entirely new and powerful theorem developing our understanding of reduced residue systems and moduli. In Section 2 we give contextual definitions and examples of mathematical concepts such as modulo and reduced residue classes, which are crucial to the understanding of the totient function. We then define the totient function. We derive formulas for evaluating φ(n) in Section 3. Finally, we consider the surjectivity of the totient function in Section 4. We ask: Over what codomain is φ surjective? Can we give n distinct numbers x1 , x2 ,...xn such that φ(x1 ) = φ(x2 )... = φ(xn )? 2 Background Before going into the uses and applications of Euler’s totient function, we should discuss the preliminary concepts required to understand our ideas and proofs, and to solidify our understanding further, we will go over some examples. We will start with integers as our other ideas show the relationship of integers, 1 developing our understanding of totient function, reduced residue systems, and moduli. b Definition 2.1. An integer b is divisible by an integer a when a leaves no remainder, this is denoted by a|b. We say that a is a divisor of b. Example 2.1. Consider 20 ÷ 5 = 4 which is an integer. This tells us that 5|20. As opposed to 21 ÷ 5 = 4.2 which is not an integer. This tells us that 5 ∤ 21. With this understanding of integers, we should discuss the primary form of comparison used in number theory, divisors, greatest common divisor, and coprimes. Definition 2.2. A common divisor is a divisor that is shared by two or more integers. The greatest common divisor (GCD) is the largest divisor that is shared. The greatest common divisor of integers a and b is denoted by (a, b) = g. A set of numbers are coprime when their greatest common divisor is 1, while a set of numbers are not coprime when their greatest common divisor is greater than 1. Example 2.2. Consider the greatest common divisor of 35 and 21. If we expand both values we get 7 · 5 and 7 · 3. Because both integers are multiples of 7, and 7 is the greatest divisor they share, the greatest common divisor of 35 and 21 is 7, denoted by (35, 21) = 7. Definition 2.3. A function f : X → Y is surjective if for every element y in Y , there exists an element x in X such that f (x) = y. Example 2.3. Consider the functions f (x) = x2 and g(x) = x3 both over the domain [−1, 1] and the codomain [−1, 1]. We see that f (x) is a not a surjective function as f (x) = x2 is never negative. We see that g(x) is a surjective function because for every y in the codomain [−1, 1], there exists x in the domain [−1, 1] such that g(x) = y. Definition 2.4. Prime numbers are positive integers that have no divisor other than itself and 1. Composite numbers are positive integers that are not prime. Example 2.4. Some example of prime numbers: 2, 3, 5, 7, 11, and 13.Some examples of composite numbers are 4, 6, 8, 10, 12, and 14. Definition 2.5. We say that an integer a is congruent to an integer b modulo m if a − b is divisible by m. This is denoted by a ≡ b (mod m), where we call m the modulus. Example 2.5. Consider the fact that 3|23 − 8, this gives us the congruence relation 23 ≡ 8 (mod 3). Definition 2.6. A reduced residue class mod m is a set of numbers that are all co prime to the modulus m such that all values in the set are not congrue nt to each other mod m. 2 Example 2.6. Let’s consider a reduced residue class mod 7. One example of a reduced residue class mod 7 is {1, 2, 3, 4, 5, 6}. Another example is {22, 9, 10, 39, 33, 13} as all integers will have a unique remainder when dividing by 7. Definition 2.7. A function f : X → Y is surjective if for every element y in Y , there exists an element x in X such that f (x) = y. Example 2.7. Consider the functions f (x) = x2 and g(x) = x3 both over the domain [−1, 1] and the codomain [−1, 1]. We see that f (x) is a not a surjective function as f (x) = x2 is never negative. We see that g(x) is a surjective function because for every y in the codomain [−1, 1], there exists x in the domain [−1, 1] such that g(x) = y. Theorem 2.8. Unique Prime Factorization Unique prime factorization is the idea that any integer greater than 0 can be expressed by unique product of prime numbers. The uniqueness mentioned comes from the orientation of the prime num- bers as multiplication is commutative, allowing someone to alter the orders of numbers in an expression. Definition 2.8. The Totient functions or the φ-function is the number of pos- itive integers less than n which are coprime to n. Example 2.9. Let us evaluate φ(6). First we list all positive integers less than 6: {1, 2, 3, 4, 5}, remove {2, 3, 4} because they share a divisor with 6 and count up the remaining integers being 1 and 5, allowing us to find that φ(6) = 2. 3 Patterns of the Totient Function The φ-function is the number of positive integers less than n which are coprime to n. This value can be computed methodically using a formula which is on certain properties of the value n. Proposition 3.1. For a prime number p, φ(p) = p − 1. Proof. Since p is prime, all positive integers less than p are coprime to p. So any reduced residue class (mod p) has size p − 1. Therefore, φ(p) = p − 1. Proposition 3.2. For p and q that are two distinct primes, φ(pq) = φ(p)φ(q). Proof. Since all numbers between each multiple of p are coprime to p, and there are q multiples of p in (qp) we subtract q from qp. The same is done for all multipled of q by subtracting p, finally we add 1 to account for both primes: = pq − q − p + 1 = q(p − 1) − 1(p − 1) φ(pq) = (p − 1)(q − 1) φ(pq) = φ(p)φ(q) 3 Corollary 3.1. For (m, n) = 1, φ(mn) = φ(m)φ(n). This means the φ- function is a multiplicative function. Corollary 3.1 follows from Proposition 3.2 by generalizing the proof. Proposition 3.3. For p a prime, φ(pr ) = pr − pr−1. Proof. Since p is prime, φ(pr ) = #{1, 2, 3,... , pr } − #{p, 2p,... , pr } In other words φ(p) is the number of positive integers less than or equal to pr minus the number of multiples of p less than or equal to pr , which is equal to pr−1. This can be rewritten as: φ(pr ) = pr − pr−1 Proposition    3.4. For n= pe11 p e2 er 2 · · · pr where pi are prime factors of n, φ(n) = n 1 − p11 1 − p12 · · · 1 − p1r. Proof. Note, by Theorem ?? all positive integers can be written uniquely by the prime factorization of that integer. By Corollary 3.1, φ(n) can be written as φ(pe11 p2 e2 · · · perr ) = φ(pe11 )φ(pe22 ) · · · φ(perr ). Since all pi are prime by Proposition 3.3, we can rewrite all factors as: φ(pe11 )φ(pe22 ) · · · φ(perr ) = (pe11 − p1e1 −1 )(pe22 − p2e2 −1 ) · · · (perr − prer −1 ) = (p1e1 −1 (p1 − 1))(p2e2 −1 (p2 − 1)) · · · (prer −1 (pr − 1))       e1 1 e2 1 er 1 = p1 1 − p2 1 − · · · pr 1 − p1 p2 pr      1 1 1 =n 1− 1− ··· 1 − p1 p2 pr 4 The Surjectivity of the Totient Function As we continued our study of Euler’s Totient function, we wondered ”over what co-domain is φ surjective?” as well as if we can ”give n distinct num- bers x1 , x2 ,...xn such that...?” Proposition 4.1. For integers x ≥ 3, φ(x) is never odd. φ(x) is only odd when x = 2. 4 Proof. Let us consider the case where n is an odd prime. Since n is prime, all positive integers less than n are relatively prime to n, except for the multiples of n. The number of multiples of n less than or equal to n is precisely 1, namely n itself. Therefore φ(n) is equal to n − 1, and φ(n) is even when n > 2 but is odd when n = 2. Now consider n as composite number greater than 2. If n is composite and greater than 2, then n can be written as the product of two or more primes: n = pa1 1 pa2 2 · · · pakk , where {p1 , p2 ,... , pk } are distinct primes and {a1 , a2 ,... , ak } are positive integers. We can use the formula for Euler’s totient function to calculate φ(n):      1 1 1 φ(n) = n 1 − 1− ··· 1 −. p1 p2 pk We can use the formula for Euler’s totient function to calculate φ(n): n is composite and greater than 2. If n is composite and greater than 2, then it can be written as the product of two or more primes: n = pa1 1 · pa2 2 ·... · pakk , where p1 , p2 ,... , pk are distinct primes and a1 , a2 ,..., ak are positive integers. Proposition 4.2. The codomain of the totient function does not contain every even number. Proof. To determine this, we computationally check every value φ(x) for x in the interval [15, 450], we found no value of x such that φ(x) = 14. We chose to search for 14 because when we checked the φ(x) in the intervals [2, 100], we noticed that 14 wasn’t an result. How we found 15 to be the lower bound of x as φ(x) produces a number less than x meaning in order for φ(x) = 14 to possibly be true, x > 14, the smallest integer greater than 14 is 15. consider the following lemma: Lemma 1. There exists a lower bound for φ(x) where no value can φ(x) ≥ x2 p With this lemma and the lower bound in mind, we determined the upper bound calculated. We can set x2 = 15 and determined that x = 450. p In terms of how we computationally checked every value of φ(x), we created a program to do so. The program calculates the Euler’s totient function (phi function) for num- bers ranging from 15 to 450. The program starts in the Main class and the main method. Inside the main method, a loop determines the value of x in φ(x). x is in the interval is between the upper and lower bound set. For each number x, the calculatePhi method is called. calculatePhi first contains a loop to find all values less than x, i. The way i is found is similar to x but i is between the interval [2, x − 1]. After i is determined, the areRelativelyPrime method is called. The areRelativelyPrime function determines whether two given numbers, x and i, are relatively prime. It calculates their greatest common divisor (GCD) 5 class Main function main(args: String[] ): void for x = 15 to 450 do phi = calculatePhi(x) print(”phi(” +x+ ”) = ” +phi) end for end function function calculatePhi(number: integer ): integer count = 0 for i = 1 to number − 1 do if areRelativelyPrime(i, number) then count = count + 1 end if end for return count end function function areRelativelyPrime(a: integer, b: integer ): boolean gcd = calculateGCD(a, b) return gcd == 1 end function function calculateGCD(a: integer, b: integer ): integer while b ̸= 0 do temp = b b=a%b a = temp end while return a end function end class 6 using the Euclidean algorithm implemented in the calculateGCD function. The GCD is obtained by repeatedly dividing the more significant number by the smaller number and updating the values until the remainder becomes zero. If the resulting GCD is equal to 1, it signifies that x and i have no common factors other than 1, indicating their relative primality. In such cases, the function returns true. However, if the GCD is greater than 1, it implies the presence of at least one common factor other than 1, indicating that a and b are not relatively prime. In this scenario, the function returns false. Thus, the areRelativelyPrime function employs the GCD calculation to assess the relative prim ality of x and i. Proposition 4.3. φ(x1 ) = φ(x2 )... = φ(xn )? Proof. Consider φ(x1 ) = φ(x2 ). By Proposition 3.3 this can be written as: pe11 −1 (p1 − 1) · · · perr −1 (pr − 1) = q1x1 −1 (q1 − 1) · · · qkxk −1 (qk − 1) Case 1 : Since φ is multiplicative, we can remove some pi and raise some other pk to a new power pekk. Thus maintaining φ(pi ) value, yet forming a new input value x so that φ(x1 ) = φ(x2 ). Example 4.1. Given φ(30) = 8, give 4 distinct x1 , x2 , x3 , x4 such that φ(30) = φ(x1 )... = φ(x4 ). Using the formula from Proposition 3.4 we can rewrite φ(30) = φ(2 · 3 · 5). Since φ(5) = 4, and φ(8) = φ(23 ) = 4 we can therefore write new φ(2·3·5) = φ(23 ·3), a new x value with the same φ(x). We can do the same with the prime 3, φ(3) = 2 we can reach the same φ value from φ(4) = φ(22 ) = 2, then write our new φ(2 · 3 · 5) = φ(23 · 3) = φ(22 · 5). We can repeat this process to eventually reach 4 new distinct x1 , x2 , x3 , x4 : φ(2 · 3 · 5) = φ(23 · 3) = φ(22 · 5) = φ(3 · 5) = φ(24 ). 5 Conclusion In conclusion, our interests in Euler’s totient function led us to wonder: Can we give n distinct numbers x1 , x2 ,...xn such that.... We also asked ourselves: Over what co-domain is φ surjective? We determined that a codomain of φ(x) consists of but not all even numbers and 1. References An Introduction To The Theory of Numbers, 5th edition by Ivan Niven, Herbert S. Zuckerman, Hugh L. Montgomery. 7