multiplicity of totient function

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

multiplicity of totient function

Postby Quaternia » Sun Aug 29, 2010 3:27 am UTC

[Pardon me if any term is undefined the way I wrote them in English. I've been doing math in French for several months now and it has gotten to me]

Hello all, a friend asked me if I knew of an easier proof of the multiplicity (for coprimes) of the totient function than the one his book was giving. (this isn't homework)
I figured that, given that monstrosity, even I could come up with one that was easier. I now realize the follies of my ways, but here is what I came up with. I think this works, but yeah...
I thought I'd post it if anyone's bored enough to check/comment upon. Thanks!

Let A be the set composed of the PRIME divisors of m, B be the set composed of the PRIME divisors of n. As m and n are relatively prime, A and B are disjoint.
Let [imath]p_1^a p_2^b ... p_x^z[/imath] be the decomposition of m into its prime factors.
Let [imath]\psi_1^\alpha \psi_2^\beta ... \psi_y^\zeta[/imath] be the decomposition of n into its prime factors.
So [imath]p_1^a p_2^b ... p_x^z\psi_1^\alpha \psi_2^\beta ... \psi_y^\zeta[/imath] is the decomposition of mn into its prime factors.
Since we can't form sets with repeated elements, but want to represent 2^3 as the three different elements {2, 2', 2''}, let us form two new sets:
Let [imath]A'[/imath] be a set with a+b+...+z elements. Let [imath]B'[/imath] be a set with [imath]\alpha + \beta + ... + \zeta[/imath] elements.

Let me introduce here the power set function, which I will denote [imath]P(x)[/imath]. The not-coprimes of m are all of the different partitions of the set A', the not-coprimes of n are all of the different partitions of the set B'.
By a known result in set theory, the cardinality of the power set of a set with x elements is 2^x.
Since A and B are disjoint, we will not have to worry about counting not-coprimes twice. Let a be the number of elements in A, b the number of elements in B. Then we have:
[imath]card(P(A')) = 2^a[/imath], [imath]card(P(B')) = 2^b[/imath]
[imath]card(P(A'))* card(P(B')) = 2^a * 2^b[/imath]
[imath]card(P(A' \cup B')) = (ab)^2 = 2^a * 2^b[/imath]
So [imath]card(P(A'))* card(P(B')) = card(P(A' \cup B'))[/imath] (in this particular case)

We have shown that counting the number of not-coprimes of n multiplied by the number of not-coprimes of m is the same as counting the number of not-coprimes to mn. Since being a not-coprime is the exact opposite of being a coprime, and that a number must either be a coprime or a not-coprime, this suffices to show that the number of coprimes of n multiplied by the number of coprimes of m is the same as the number of coprimes of mn (given m,n relatively prime).
Since the Totient function counts the number of coprimes, this completes our proof. [hopefully. :roll: ]
Last edited by Quaternia on Tue Aug 31, 2010 9:57 pm UTC, edited 2 times in total.
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

User avatar
imatrendytotebag
Posts: 152
Joined: Thu Nov 29, 2007 1:16 am UTC

Re: multiplicity of totient function

Postby imatrendytotebag » Mon Aug 30, 2010 9:00 am UTC

Well, I regret to inform you that your proof is flawed. Importantly, your assertion that the number of non-coprime elements to mn is not equal to the number of non-coprime elements to m times the number of non-coprime elements to n. Try some small cases for m and n and try to figure out where your proof breaks down.

Here is an outline of a different proof (maybe you like it better?):

Suppose 0 <= x < mn. We can associate x to the pair (a_x,b_x), where x = a_x (mod m), x = b_x (mod n), 0 <= a_x < m, 0 <= b_x < n (obviously this choice of a_x and b_x are unique). Then we want to prove 2 facts: a) Each (a_x,b_x) is associated to one and only one x (so (a_y,b_y) =/= (a_x,b_x) if x =/= y). b) x is coprime to mn if and only if a_x is coprime to m and b_x is coprime to n. Then we have showed the number of integers less than mn coprime to mn is the same as the number of pairs (a,b), a less than m and coprime to m, b less than n and coprime to n. The former is phi(mn), the latter is phi(m)*phi(n).

a) Suppose (a_x,b_x) = (a_y,b_y). Then x = y (mod m), x = y (mod n). Or m|(x-y), n|(x-y), and since m and n are relatively prime, mn|(x-y). But if 0 <= x < mn and 0 <= y < mn this must mean x = y. But then there are mn numbers 0 <= x < mn and mn pairs (a,b) with 0 <=a < m and 0 <= b < n, and since no pair is hit more than once every pair is hit exactly once.

b) If x is coprime to mn, then for any prime p|m, p does not divide x. Hence p also does not divide a_x (since p divides x - a_x). So a_x is coprime to m. Similarly, b_x is coprime to n. On the other hand, suppose a_x is coprime to m and b_x is coprime to n. Then if p is a prime and p|mn then p|m or p|n. If p|m, p does not divide a_x, hence p does not divide x (since p divides x - a_x). Similarly, if p|n, p does not divide x. So no prime dividing mn also divides x. This means x is coprime to mn.

This proof is based on the idea of the Chinese Remainder Theorem (wiki it?), the simplest case of which is basically the assertion that each (a_x,b_x) is associated to one and only one x.
Hey baby, I'm proving love at nth sight by induction and you're my base case.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Mon Aug 30, 2010 3:37 pm UTC

Thanks for the answer, I appreciate.
imatrendytotebag wrote:Importantly, your assertion that the number of non-coprime elements to mn is not equal to the number of non-coprime elements to m times the number of non-coprime elements to n. Try some small cases for m and n and try to figure out where your proof breaks down.

Oh hell, I forgot to say that it's PRIME divisors... Is this what you were going at? I've gone back and edited it.


imatrendytotebag wrote:This proof is based on the idea of the Chinese Remainder Theorem (wiki it?), the simplest case of which is basically the assertion that each (a_x,b_x) is associated to one and only one x.

My friend is not familiar with the Chinese Remainder Theorem, but is familiar with a lot of set theory, hence what I tried to do.
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: multiplicity of totient function

Postby jaap » Mon Aug 30, 2010 4:18 pm UTC

Quaternia wrote:We have shown that counting the number of not-coprimes of n multiplied by the number of not-coprimes of m is the same as counting the number of not-coprimes to mn. Since being a not-coprime is the exact opposite of being a coprime, and that a number must either be a coprime or a not-coprime, this suffices to show that the number of coprimes of n multiplied by the number of coprimes of m is the same as the number of coprimes of mn (given m,n relatively prime).


Counting the number of not-coprimes of k plus the co-primes of k, we must get k. I don't want to use imath, so let's write this as NC(k)+C(k) = k.
In the above paragraph you are saying that
NC(n) * NC(m) = NC(nm)
and that from this it follows that
C(n) * C(m) = C(nm)
This cannot be true if NC(k)+C(k) = k for all k.

Small example:
n=3,m=5
C(3) = |{1,2}| = 2
C(5) = |{1,2,3,4}| = 4
C(15) = |{1,2,4,7,8,11,13,14}| = 8

NC(3) = |{3}| = 1 = 3 - C(3)
NC(5) = |{5}| = 1 = 5 - C(5)
NC(15) = |{3,5,6,9,10,12,15}| = 7 = 15-C(15)

Clearly it is not true that NC(3)*NC(5)=NC(15), though the totient function is multiplicative: C(3)*C(5)=C(15).

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Mon Aug 30, 2010 5:17 pm UTC

Thanks, Jaap, but there's something that bothers me.
jaap wrote:This cannot be true if NC(k)+C(k) = k for all k.

That's not what I meant. What I meant was, if I show that NC(k) is multiplicative, that means C(k) must be too.
Am I missing something here? Does what you wrote follow directly from what I wrote in this post? Sorry if I'm slow, I don't doubt you, I just want to undertand :)
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: multiplicity of totient function

Postby jaap » Mon Aug 30, 2010 5:30 pm UTC

Quaternia wrote:Thanks, Jaap, but there's something that bothers me.
jaap wrote:This cannot be true if NC(k)+C(k) = k for all k.

That's not what I meant. What I meant was, if I show that NC(k) is multiplicative, that means C(k) must be too.
Am I missing something here? Does what you wrote follow directly from what I wrote in this post? Sorry if I'm slow, I don't doubt you, I just want to undertand :)


Given n, every one of the numbers 1,2,3....,n is either coprime to n or not coprime to n.
The number of coprime numbers, plus the number of coprime numbers must therefore sum to n.

Anyway, just look at the counterexample I gave and count them.
Edit: The point I'm trying to get across is that there is no relation between the multiplicativity of the totient function C, and the multiplicativity or otherwise of NC, which can be expressed as NC(k) = k-C(k). In fact, NC is not multiplicative.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Mon Aug 30, 2010 7:45 pm UTC

Ah now I understand. Thanks for clarifying, that indeed kills it :D
Is there any set-theoretic proof of the multiplicity of the totient function, by the way? Because it seemed like it was going somewhere in the beginning.
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: multiplicity of totient function

Postby Nitrodon » Tue Aug 31, 2010 5:02 am UTC

I would be surprised if there were any proof of the result without using the Chinese Remainder Theorem in some way.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Tue Aug 31, 2010 6:23 pm UTC

Well, this is the proof that my friend's book ("Abstract Algebra", W.E. Deskins) gave. He typed it up for me, thought I'd share. I don't think it uses the Chinese Remainder Theorem; it hasn't been introduced yet in the book at this point, and I doubt they use it sneakily either, but what do I know.
Spoilered for length and excessive imath.
Spoiler:
Theorem. If [imath]m[/imath] and [imath]n[/imath] are positive integers such that [imath](m,n)=1[/imath], then [imath]\phi(mn)=\phi(m)\phi(n)[/imath].

Proof

To prove this we rely heavily on the characterization of the totient in Theorem 3.23. Denote [imath]\phi(m)[/imath] by [imath]s[/imath] and [imath]\phi(n)[/imath] by [imath]t[/imath]. Then [imath]s[/imath] is the number of equivalence classes modulo [imath]m[/imath] which consist of elements relatively prime to [imath]m[/imath], and [imath]t[/imath] is the number of equivalence classes modulo [imath]n[/imath] which contain only elements relatively prime to [imath]n[/imath]. Now select integers [imath]x[/imath] and [imath]y[/imath] such that [imath](x,m) = 1 = (y,n)[/imath] and form

[imath]u = nx+my[/imath]

We claim that [imath](u, mn)=1[/imath]. For suppose [imath]p[/imath] is a prime factor of [imath]mn[/imath]. Since [imath](m,n)=1[/imath] we know that [imath]p[/imath] is a factor of only one of the two, say [imath]m[/imath]. Then if [imath]p[/imath] were a factor of [imath]u[/imath] we could write

[imath]nx = u - my[/imath],

which would show that [imath]p[/imath] is a factor of [imath]nx[/imath]. But equations [imath](n,m)=(x,m)=1[/imath] imply that this is impossible. So we see that [imath](u, mn) = 1[/imath].

If we count the number of such integers [imath]u[/imath] which can be formed we see that there are [imath]st[/imath] such integers since there are [imath]s[/imath] choices for [imath]x[/imath] and [imath]t[/imath] choices for [imath]y[/imath]. If we can show that these [imath]st[/imath] integers lie in different equivalence classes modulo [imath]mn[/imath], then we will have shown that

[imath]\phi(mn) \geq \phi(m)\phi(n) = st[/imath].
So assume that two numbers of this form are in the same class:
[imath]nx_1 + my_1 \equiv nx_2 + my_2[/imath] mod mn,
where [imath]1 \leq x_i < m, (x_i, m) = 1, 1 \leq y_i < n, (y_i, n) = 1[/imath], for [imath]i = 1[/imath] and [imath]2[/imath]. Therefore
[imath](nx_1 + my_1) - (nx_2 + my_2) = kmn[/imath]
for some integer [imath]k[/imath], and we have
[imath]n(x_1 - x_2) + m(y_1 - y_2) = kmn[/imath],
an equation which implies, since [imath](m,n)=1[/imath], that [imath]m[/imath] is a factor of [imath]x_1 - x_2[/imath] and [imath]n[/imath] is a factor of [imath]y_1 - y_2[/imath]. But [imath]x_1[/imath] and [imath]x_2[/imath] are positive integers less than [imath]n[/imath] so that
[imath]-m < x_1 - x_2 < m[/imath] and [imath]-n < y_1 - y_2 < n[/imath].
Since 0 is the only multiple of [imath]m[/imath] between [imath]-m[/imath] and [imath]m[/imath] we see that
[imath]x_1 - x_2 = 0[/imath] or [imath]x_1 = x_2[/imath].
Similarly [imath]y_1 = y_2[/imath]. Thus the [imath]st[/imath] numbers of the form [imath]nx+my[/imath] lie in distinct classes modulo [imath]mn[/imath], and
[imath]\phi(mn) \geq st[/imath].

Now suppose [imath]w[/imath] is an integer relatively prime to [imath]mn[/imath], [imath](w,mn)=1[/imath]. Then certainly [imath]w[/imath] is relatively prime to each of the integers [imath]m[/imath] and [imath]n[/imath], so that [imath](w,m) = (w,n)=1[/imath]. We wish to show that there are [imath]x[/imath] and [imath]y[/imath] such that [imath]1 \leq x < m, 1 \leq y < n, (x,m)=(y,n)=1[/imath], and
[imath]w \equiv xn+ym[/imath] mod mn.
Since this means that
[imath]w = (xn+ym)+kmn[/imath]
for some integer [imath]k[/imath], we see that [imath]x[/imath] and [imath]y[/imath] must satisfy congruences
[imath]w \equiv xn[/imath] mod m
and
[imath]w \equiv ym[/imath] mod n.

Do such integers exist? Well, we know that [imath](m,n)=1[/imath], and from this condition we get an equation
[imath]am+bn=1[/imath]
for some integers [imath]a[/imath] and [imath]b[/imath]. Multiplying this by [imath]w[/imath] yields
[imath]w = wam+wbn.[/imath]

By the Divisor Theorem,
[imath]wa = q_1n+y, \quad 0 \leq y < n[/imath]
[imath]wb = q_2n+x, \quad 0 \leq x < m[/imath].

Substituting these we get
[imath]w = ym+(wb+q_1m)n[/imath]
and
[imath]w = xn+(wa+q_2n)m[/imath]
or
[imath]w \equiv ym[/imath] mod n
and
[imath]w \equiv xn[/imath] mod m.

Furthermore, from these equations we see that [imath](y,n)=1[/imath], since a common factor of [imath]y[/imath] and [imath]n[/imath] would be a common factor of [imath]w[/imath] and [imath]n[/imath] as
[imath]w =ym+kn[/imath],
and similarly
[imath](x,m)=1[/imath].

Further substitution yields
[imath]w = (q_1n + y)m + (q_2m+x)n = xn+ym+(q_1+q_2)mn[/imath]
and so
[imath]w \equiv xn + ym[/imath] mod mn.

This means that the number of classes consisting of elements relatively prime to [imath]mn[/imath] is no greater than the number of elements of the form
[imath]xn+ym[/imath],
where [imath](x,m)=(y,n)=1, 1 \leq x < m, 1 \leq y < n[/imath].

Therefore [imath]\phi(mn) \leq \phi(m)\phi(n)[/imath], and we conclude from this and the other inequality that
[imath]\phi(mn)=\phi(m)\phi(n)[/imath].
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: multiplicity of totient function

Postby mike-l » Tue Aug 31, 2010 7:02 pm UTC

Quaternia wrote:Well, this is the proof that my friend's book ("Abstract Algebra", W.E. Deskins) gave. He typed it up for me, thought I'd share. I don't think it uses the Chinese Remainder Theorem; it hasn't been introduced yet in the book at this point, and I doubt they use it sneakily either, but what do I know.
Spoilered for length and excessive imath.
Spoiler:
Theorem. If [imath]m[/imath] and [imath]n[/imath] are positive integers such that [imath](m,n)=1[/imath], then [imath]\phi(mn)=\phi(m)\phi(n)[/imath].

Proof

To prove this we rely heavily on the characterization of the totient in Theorem 3.23. Denote [imath]\phi(m)[/imath] by [imath]s[/imath] and [imath]\phi(n)[/imath] by [imath]t[/imath]. Then [imath]s[/imath] is the number of equivalence classes modulo [imath]m[/imath] which consist of elements relatively prime to [imath]m[/imath], and [imath]t[/imath] is the number of equivalence classes modulo [imath]n[/imath] which contain only elements relatively prime to [imath]n[/imath]. Now select integers [imath]x[/imath] and [imath]y[/imath] such that [imath](x,m) = 1 = (y,n)[/imath] and form

[imath]u = nx+my[/imath]

We claim that [imath](u, mn)=1[/imath]. For suppose [imath]p[/imath] is a prime factor of [imath]mn[/imath]. Since [imath](m,n)=1[/imath] we know that [imath]p[/imath] is a factor of only one of the two, say [imath]m[/imath]. Then if [imath]p[/imath] were a factor of [imath]u[/imath] we could write

[imath]nx = u - my[/imath],

which would show that [imath]p[/imath] is a factor of [imath]nx[/imath]. But equations [imath](n,m)=(x,m)=1[/imath] imply that this is impossible. So we see that [imath](u, mn) = 1[/imath].

If we count the number of such integers [imath]u[/imath] which can be formed we see that there are [imath]st[/imath] such integers since there are [imath]s[/imath] choices for [imath]x[/imath] and [imath]t[/imath] choices for [imath]y[/imath]. If we can show that these [imath]st[/imath] integers lie in different equivalence classes modulo [imath]mn[/imath], then we will have shown that

[imath]\phi(mn) \geq \phi(m)\phi(n) = st[/imath].
So assume that two numbers of this form are in the same class:
[imath]nx_1 + my_1 \equiv nx_2 + my_2[/imath] mod mn,
where [imath]1 \leq x_i < m, (x_i, m) = 1, 1 \leq y_i < n, (y_i, n) = 1[/imath], for [imath]i = 1[/imath] and [imath]2[/imath]. Therefore
[imath](nx_1 + my_1) - (nx_2 + my_2) = kmn[/imath]
for some integer [imath]k[/imath], and we have
[imath]n(x_1 - x_2) + m(y_1 - y_2) = kmn[/imath],
an equation which implies, since [imath](m,n)=1[/imath], that [imath]m[/imath] is a factor of [imath]x_1 - x_2[/imath] and [imath]n[/imath] is a factor of [imath]y_1 - y_2[/imath]. But [imath]x_1[/imath] and [imath]x_2[/imath] are positive integers less than [imath]n[/imath] so that
[imath]-m < x_1 - x_2 < m[/imath] and [imath]-n < y_1 - y_2 < n[/imath].
Since 0 is the only multiple of [imath]m[/imath] between [imath]-m[/imath] and [imath]m[/imath] we see that
[imath]x_1 - x_2 = 0[/imath] or [imath]x_1 = x_2[/imath].
Similarly [imath]y_1 = y_2[/imath]. Thus the [imath]st[/imath] numbers of the form [imath]nx+my[/imath] lie in distinct classes modulo [imath]mn[/imath], and
[imath]\phi(mn) \geq st[/imath].

Now suppose [imath]w[/imath] is an integer relatively prime to [imath]mn[/imath], [imath](w,mn)=1[/imath]. Then certainly [imath]w[/imath] is relatively prime to each of the integers [imath]m[/imath] and [imath]n[/imath], so that [imath](w,m) = (w,n)=1[/imath]. We wish to show that there are [imath]x[/imath] and [imath]y[/imath] such that [imath]1 \leq x < m, 1 \leq y < n, (x,m)=(y,n)=1[/imath], and
[imath]w \equiv xn+ym[/imath] mod mn.
Since this means that
[imath]w = (xn+ym)+kmn[/imath]
for some integer [imath]k[/imath], we see that [imath]x[/imath] and [imath]y[/imath] must satisfy congruences
[imath]w \equiv xn[/imath] mod m
and
[imath]w \equiv ym[/imath] mod n.

Do such integers exist? Well, we know that [imath](m,n)=1[/imath], and from this condition we get an equation
[imath]am+bn=1[/imath]
for some integers [imath]a[/imath] and [imath]b[/imath]. Multiplying this by [imath]w[/imath] yields
[imath]w = wam+wbn.[/imath]

By the Divisor Theorem,
[imath]wa = q_1n+y, \quad 0 \leq y < n[/imath]
[imath]wb = q_2n+x, \quad 0 \leq x < m[/imath].

Substituting these we get
[imath]w = ym+(wb+q_1m)n[/imath]
and
[imath]w = xn+(wa+q_2n)m[/imath]
or
[imath]w \equiv ym[/imath] mod n
and
[imath]w \equiv xn[/imath] mod m.

Furthermore, from these equations we see that [imath](y,n)=1[/imath], since a common factor of [imath]y[/imath] and [imath]n[/imath] would be a common factor of [imath]w[/imath] and [imath]n[/imath] as
[imath]w =ym+kn[/imath],
and similarly
[imath](x,m)=1[/imath].

Further substitution yields
[imath]w = (q_1n + y)m + (q_2m+x)n = xn+ym+(q_1+q_2)mn[/imath]
and so
[imath]w \equiv xn + ym[/imath] mod mn.

This means that the number of classes consisting of elements relatively prime to [imath]mn[/imath] is no greater than the number of elements of the form
[imath]xn+ym[/imath],
where [imath](x,m)=(y,n)=1, 1 \leq x < m, 1 \leq y < n[/imath].

Therefore [imath]\phi(mn) \leq \phi(m)\phi(n)[/imath], and we conclude from this and the other inequality that
[imath]\phi(mn)=\phi(m)\phi(n)[/imath].

Um, that's pretty much the CRT :) You showed that (pairs congruence classes mod m and n) correspond to (congruence classes modulo mn) in the case of coprime congruence classes. The CRT just does the same thing for all pairs/all classes.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Tue Aug 31, 2010 7:09 pm UTC

Grrr :mrgreen: Thanks. There IS one last proof that I know of, that shows the Mobius inversion function is multiplicative, and then uses some group theory to show that the totient function also is. You might know it, or I can type it up if you want, but since I don't understand it...
Last edited by Quaternia on Tue Aug 31, 2010 8:30 pm UTC, edited 1 time in total.
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: multiplicity of totient function

Postby mike-l » Tue Aug 31, 2010 7:55 pm UTC

Quaternia wrote:Grrr :mrgreen: Thanks. There IS one last proof that I know of, that shows the Mobius inversion function is multiplicative, and then uses some group theory to show that the totient function also is. You might know it, or I can type it up if you want, but since I don't understand it...

Ok, haven't seen this in years so let's give it a go.

The Möbius function, [imath]\mu[/imath] is 0 on all numbers except square free numbers and (-1)^n for a square free number with n prime factors. This is clearly multiplicative.

Now we get the remarkable property that
[math]\sum_{d \vert n} \mu(d) = \delta_{n,1}.[/math]
Indeed, we may assume n is square free since only the square free factors of n will contribute, and then this is really just the statement that the number of odd sized subsets of a non-trivial set is equal to the number of even sized subsets. (NB, usually you define the Möbius function this way and then get it's description above, but this is the fastest way I can do it right now).

This property leads the the even more remarkable Möbius inversion formula, whereby if
[math]f(n) = \sum_{d \vert n} g(d)[/math]
then [math]g(n) = \sum_{d \vert n} \mu(d) f(n/d).[/math]
To see this, just substitute the definition of f in and change the order of summation:
[math]\sum_{d \vert n} \mu(d) f(n/d)=\sum_{d \vert n} \sum_{e \vert n/d} \mu(d)g(e) = \sum_{e \vert n}g(e) \sum_{d \vert n/e} \mu(d) = \sum_{e\vert n}g(e)\delta_{n/e, 1} = g(n)[/math]

Ok great, now we note that [math]n = \sum_{d \vert n}\phi(d)[/math]since the number [imath]0 < x \le n[/imath] will be counted exactly when d = (x,n).

So we apply the inversion formula above and get
[math]\phi(n) = \sum_{d \vert n}\mu(d)n/d[/math]

If (m,n) = 1, then the divisors of mn are exactly the ed where [imath]e \vert m[/imath] and [imath]d \vert n[/imath]. So using this, and the above, and the multiplicativity of the Möbius function, and the fact that the e,d above must be coprime if m,n are, we get
[math]\phi(mn) = \sum_{d \vert n}\sum_{e \vert m} \mu(ed)mn/(ed) = \sum_{d \vert n}\sum_{e \vert m} (\mu(e)m/e)(\mu(d)n/d) = \left( \sum_{d \vert n}\mu(d)n/d\right) \left(\sum_{e \vert m}\mu(e)m/e\right) =\phi(n)\phi(m).[/math]

Hey, it works, and I don't think there's any CRT involved!
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Tue Aug 31, 2010 10:07 pm UTC

mike-l wrote:Hey, it works, and I don't think there's any CRT involved!

Wow, nice! I'm reasonably sure that's the one I've heard about, but I won't pretend to understand it. I'll read it through a couple of times, though, thanks.

jaap wrote:NC(3) = |{3}| = 1 = 3 - C(3)
NC(5) = |{5}| = 1 = 5 - C(5)
NC(15) = |{3,5,6,9,10,12,15}| = 7 = 15-C(15)

Clearly it is not true that NC(3)*NC(5)=NC(15), though the totient function is multiplicative: C(3)*C(5)=C(15).


Right, so that means there's something else that's going wrong too (?).
Let's take a look at what I get, because I'm not really using NC itself directly, but rather something related I'll call NC':
NC'(3) = 1 because 3 is prime, 3 = 3^1, and I'm adding the exponent in the prime decomposition, so, 1.
NC'(5) = 1, same reasoning as above.
NC'(15) = , 15 = 3^1*5^1, and I'm adding the exponents in the prime decomposition, so, 2.
So my first set A' will have 1 element, my set B' will have 1 element, and A' and B' are disjoint by the way I set it up.
So, A U B will have 2 elements. That last line of mine seems to work fine here, the one that states:
So [imath]card(P(A'))* card(P(B')) = card(P(A' \cup B'))[/imath] (in this particular case)

Now let's look at what I'm 'counting' with the cardinality and the power set constructions. If I have a number, say 8, and I decompose it into prime factors, I get 2^3.
And from there we can create every single common factor, right? So like: {2, 4, 8}. (notice how it has three elements)
A bit of horrible breakage of notation to show what's going on: we could've been using the power set function on {2, 2, 2} (WHICH ISN'T A SET!!!) and we'd be getting {null, 2, {2,2}, {2,2,2}} (4 elements counting the null set)
But we really don't care about the actual element, just the number of them, hence why I create A' and B' as new sets to avoid the problem of the {2,2,2} non-set.
And this is what I'm saying is multiplicative.
Can someone clarify then where it's breaking down? Thanks :oops:
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

Re: multiplicity of totient function

Postby Nitrodon » Tue Aug 31, 2010 11:19 pm UTC

Quaternia: You had a mostly correct proof of the (true) result that the function which returns the amount of factors of a given number (including 1 and itself) is multiplicative. The main problem was that this was not the result you wanted to prove.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Wed Sep 01, 2010 1:25 am UTC

Ok, so that much at least is alright...
Two things:
- does this function have a name? Is it sometimes useful? o.O
- So now what I was failing at trying to do was say, "well, they're multiplicative, so the inverse property of being not-factors must also be, since I'm counting the opposite ones". To clarify, is this the part that fails by Jaap's counterexample? If so, theoretically... I'm so lost.
Thanks a bunch, all of you!
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

mike-l
Posts: 2758
Joined: Tue Sep 04, 2007 2:16 am UTC

Re: multiplicity of totient function

Postby mike-l » Wed Sep 01, 2010 2:03 am UTC

Quaternia wrote:Ok, so that much at least is alright...
Two things:
- does this function have a name? Is it sometimes useful? o.O
- So now what I was failing at trying to do was say, "well, they're multiplicative, so the inverse property of being not-factors must also be, since I'm counting the opposite ones". To clarify, is this the part that fails by Jaap's counterexample? If so, theoretically... I'm so lost.
Thanks a bunch, all of you!


There is the divisor function d(n) which is the number of divisors a number has. This is multiplicative for the reason you show. Then there is the totient function [imath]\phi(n)[/imath] which the proofs above show is also multiplicative. But it's not true that [imath]\phi(n) + d(n) = n[/imath]. For one thing, 1 is counted twice, but more importantly, there are generally numbers less than n that are neither coprime nor divisors (eg 4 is neither coprime nor a divisor of 6).

In general, the sum of two multiplicative functions will not be multiplicative (unless their product is identically zero). This is what Jaap was saying.
addams wrote:This forum has some very well educated people typing away in loops with Sourmilk. He is a lucky Sourmilk.

User avatar
Quaternia
Posts: 218
Joined: Mon Jun 15, 2009 6:18 pm UTC

Re: multiplicity of totient function

Postby Quaternia » Wed Sep 01, 2010 5:08 pm UTC

Alright, thanks!
mike-l wrote:there are generally numbers less than n that are neither coprime nor divisors (eg 4 is neither coprime nor a divisor of 6).

This really did it for me.

I just thought I'd show explicitely how it fails, using your example.
Then the numbers coprime to n are {1,5}, and the divisors of n are {2,3}.
My method takes the set {2,3} and applies the power set operation to it, giving the set:
{null, {2}, {3}, {2,3}}
so 2, 3, and 6. And the 4 isn't taken into account.
Yakk wrote:hey look, the algorithm is a FSM. Thus, by his noodly appendage, QED

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: multiplicity of totient function

Postby DavCrav » Fri Sep 10, 2010 7:36 am UTC

Sorry to drag this thing up, but I came up with an easy proof of this (obviously already known, I guess), using cyclic groups.

Firstly, if [imath]d[/imath] and [imath]e[/imath] are coprime, then it is well known that [imath]C_{de}=C_d\times C_e[/imath], where [imath]C_n[/imath] is the cyclic group of order [imath]n[/imath]. Notice that a generator for the cyclic group [imath]C_n[/imath] (thought of as integers modulo [imath]n[/imath]) is an integer less than [imath]n[/imath] that is prime to [imath]n[/imath]. Hence the number of generators of [imath]C_n[/imath] is [imath]\phi(n)[/imath].

Next, we note that every subgroup of [imath]C_d\times C_e[/imath] is of the form [imath]C_a\times C_b[/imath] for [imath]a\mid d[/imath] and [imath]b\mid e[/imath]. Hence the number of elements of [imath]C_d\times C_e[/imath] that lie in proper subgroups of it are
[math](d-\phi(d))(e-\phi(e))+\phi(d)(e-\phi(e))+\phi(e)(d-\phi(d).[/math]
(Here, the first term is all elements [imath](x,y)[/imath] that generate a proper subgroup of both factors (so that neither [imath]x[/imath] nor [imath]y[/imath] is prime to [imath]d[/imath] and [imath]e[/imath] respectively), the second are those that generate a proper subgroup of the second factor and the whole of the first factor, and vice versa for the third.)

Cleaning this up, we get
[math](d-\phi(d))(e-\phi(e))+\phi(d)(e-\phi(e))+\phi(e)(d-\phi(d)=de-\phi(d)\phi(e).[/math]
This is the number of elements of [imath]C_d\times C_e=C_{de}[/imath] that do not generate the whole group, so is equal to [imath]de-\phi(de)[/imath]. This completes the proof.


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 10 guests