how to prove that euler's phi function is multiplicative

We often hear about multiplicative functions in number theory, and they are useful when working with prime numbers. So, it helps to know what they are and how to use them. So, what is a multiplicative function? A multiplicative function f satisfies both f(1) = 1 and f(ab) = f(a)f(b) for any pair of positive coprime integers a & b. A multiplicative function is a specific type of arithmetic function, which has natural numbers as inputs and complex numbers as outputs. Euler’s phi function is multiplicative. Of course, some multiplicative functions are easy to find and verify (such as the constant function f(n) = 1). Others are a little more difficult to verify. In this article, we’ll talk about multiplicative functions and what they are. We’ll also give some examples and non-examples of multiplicative functions to make the concept clear. Let’s begin. What Is A Multiplicative Function? A multiplicative function f:N→C satisfies the following properties: f(1) = 1f(ab) = f(a)f(b) when a and b are coprime (that is, a and b share no common factor besides 1) If f(ab) = f(a)f(b) for any positive integers a and b, the f is completely multiplicative. A multiplicative function satisfies f(1) = 1 and f(ab) = f(a)f(b) for all positive coprime pairs a and b. A multiplicative function is a type of arithmetic function. This means it has only positive integers (natural numbers) as inputs, and it only has complex numbers as outputs. Multiplicative functions are found in the context of number theory. Example 1: Multiplicative Function f(n) = 1 The constant function f(n) = 1 is multiplicative, since we can show that the two properties are satisfied. The first property is easy: f(1) = 1 [since the function always has an output value of 1] Now for the second property: f(ab) = 1 [since the function always has an output value of 1]f(ab) = 1*1 [since 1*1 = 1]f(ab) = f(a)*1 [since f(a) = 1 for any value of a]f(ab) = f(a)*f(b) [since f(b) = 1 for any value of b] Thus, both of the necessary properties are satisfied. So, the function f(n) = 1 is multiplicative (in fact, it is completely multiplicative). Example 2: Multiplicative Function f(n) = n The identity function f(n) = n is multiplicative, since we can show that the two properties are satisfied. The first property is easy: f(1) = 1 [since n = 1 here, and this function always has the same input and output] Now for the second property: f(ab) = ab [by definition, this function always has the same input and output]f(ab) = f(a)*b [since f(a) = a for any value of a]f(ab) = f(a)*f(b) [since f(b) = b for any value of b] Thus, both of the necessary properties are satisfied. So, the function f(n) = n is multiplicative (in fact, it is completely multiplicative). Example 3: Multiplicative Function f(n) = nk The power function f(n) = nk is multiplicative, since we can show that the two properties are satisfied. The first property is easy: f(1) = 1k = 1 [since n = 1 here, and 1k = 1 for any power k] Now for the second property: f(ab) = (ab)k [by definition of a power function]f(ab) = akbk [by the rules of exponents]f(ab) = f(a)*bk [since f(a) = ak for any value of a and k]f(ab) = f(a)*f(b) [since f(b) = bk for any value of b and k] Thus, both of the necessary properties are satisfied. So, the function f(n) = nk is multiplicative (in fact, it is completely multiplicative). Example 4: Non-Multiplicative Function f(n) = 2 The constant function f(n) = 2 is non-multiplicative, since we can show that it fails the first property: f(1) = 2 [since f(n) = 2 for all values of n] Thus, f(1) is not equal to 1, and so the function is not multiplicative. The same is true for any function where f(1) is not equal to 1. Example 5: Non-Multiplicative Function f(n) = 2n - 1 The polynomial function f(n) = 2n - 1 is non-multiplicative. It satisfies the first property, but fails the second: f(1) = 2(1) – 1 = 1 The first property is satisfied, but: f(ab) = 2(ab) - 1 while: f(a)f(b) = (2a – 1)(2b – 1)f(a)f(b) = 4ab – 2a – 2b + 1 If these two were equal, then we would get: 2ab – 1 = 4ab – 2a – 2b + 10 = 2ab – 2a – 2b + 20 = ab – a – b + 10 = a(b – 1) – (b – 1)0 = (a – 1)(b – 1) This implies either a = 1 or b = 1 (or both). In any case, the second property is not satisfied for any values a and b where both are not 1. So, the function f(n) = 2n – 1 is not multiplicative. How Do You Know If A Function Is Multiplicative? First of all, the graph of a multiplicative function will pass through the point (1, 1), since it must satisfy f(1) = 1. However, this condition alone is not enough to ensure a multiplicative function. Rather, this helps us to find some of the non-multiplicative functions, which do not pass through (1, 1) However, the graph of a multiplicative function is neither defined nor continuous on the real numbers, since we only allow natural numbers (positive integers) as inputs. After testing the first property to easily rule out a function, the only way to know for sure if a function is multiplicative is to test the second property: f(ab) = f(a)f(b) when a and b are coprime It is impossible to check this for all coprime integer pairs a and b, so we need to prove it in general. How To Prove A Function Is Multiplicative To prove a function is multiplicative, we must show that f(ab) = f(a)f(b) for any coprime pair of integers a and b. The best way to do this is to start by looking at the left side. Figure out what it looks like – what can you change or simplify? Next, look at the right side and figure out what it looks like. What can you change or simplify? Then, compare the two sides and think about how to show they are the same. Remember some of the methods we used in earlier examples: the constant value of a function for f(n) = 1the rules of exponents for f(n) = nk Basically, use what you know about the function definition and any operation it introduces (constant, multiplication, power, etc.) Also, consider what it means for two positive integers a and b to be relatively prime. Think about how this can help you with your proof. Let’s look at a well-known example from Leonhard Euler. Is Euler’s Phi Function Multiplicative? Euler’s phi function (also called Euler’s totient function) is multiplicative. The definition is as follows: ɸ(n) = the number of positive integers up to n that are coprime to n. That is, to find ɸ(n), follow these steps: First, make a list of all the numbers from 1 to n - 1: 1, 2, 3, 4, … , n – 1, n.Next, check each number on the list to find out if it is coprime to n. Cross off any that are not coprime to n.Then, count how many of the numbers on the list are coprime to n.Finally, assign this count as the value of ɸ(n). For example, ɸ(5) = 4, since: Our starting list is 1, 2, 3, 4, 5.The numbers 1, 2, 3, and 4 are all coprime to 5 (since 5 is prime).There are 4 numbers remaining on our list.Thus, ɸ(5) = 4 In general, for any prime number p, we have ɸ(p) = p – 1, since all numbers from 1 to p – 1 are coprime to a prime number p. So: ɸ(2) = 2 – 1 = 1ɸ(3) = 3 – 1 = 2ɸ(5) = 5 – 1 = 4ɸ(7) = 7 – 1 = 6… As another example, ɸ(6) = 2, since: Our starting list is 1, 2, 3, 4, 5, 6.The numbers 1 and 5 are all coprime to 6 (2, 3, and 4 share factors of 2 or 3 with 6).There are 2 numbers remaining on our list.Thus, ɸ(6) = 2 In general, if a and b are coprime (meaning that gcd(a,b) = 1), then ɸ(ab) = ɸ(a) ɸ(b). How To Prove That Euler’s Phi Function Is Multiplicative To prove that Euler’s phi function is multiplicative, we must show both properties. For the first property, ɸ(1) = 1 is easy, since 1 is the only number in our list, and gcd(1, 1) = 1 (that is, the greatest common divisor of 1 and 1 is 1). For the second property: if a and b are coprime, then let: A = the set of integers less than a that are coprime to a (so |A| = ɸ(a))B = the set of integers less than b that are coprime to b (so |B| = ɸ(b))C = the set of integers less than ab that are coprime to ab (so |C| = ɸ(ab)) The Chinese Remainder Theorem tells us there is a bijection between AxB and C. This means that |AxB| = |C|, and thus |A|*|B| = |C|, and thus ɸ(a) ɸ(b) = ɸ(ab). Note: if a and b are coprime, then they do not share any common prime factors. This means that we can also write out two prime factorizations: a = p1k1p2k2…pmkmb = q1l1q2l2…qnln where each pi and qj is a distinct prime, and where there is no overlap between the pi’s and qj’s. Then we can say that: ɸ(ab)= ɸ((p1k1p2k2…pmkm)( q1l1q2l2…qnln))= ɸ(p1k1) ɸ(p2k2)… ɸ(pmkm)ɸ(q1l1) ɸ(q2l2)… ɸ(qmlm) [since ɸ is multiplicative] From here, we can use rules regarding Euler's phi function applied to powers of prime numbers: specifically, ɸ(pk) = pk – pk-1. This comes from the fact that any multiple of p will not be coprime to pk (and there are pk-1 such numbers from 1 to pk). Conclusion Now you know what a multiplicative function is. You also have some examples, and you know how to approach a proof that a function is multiplicative (or how to disprove it). I hope you found this article helpful. If so, please share it with someone who can use the information. Don’t forget to subscribe to my YouTube channel & get updates on new math videos! ~Jonathon