How do I finish this Euler-phi proof?

**Timbuk2**

Note: [latex]\phi(n)[/latex] is the Euler-phi (or Euler Toitent) function of n, which counts the number of integers between 1 and n that are relatively prime to n. The question:

If p is a prime and k [latex]\geq[/latex] 2 is an integer, prove that:
[latex]\displaystyle \phi(\phi(p^k)) = p^{k-2}\phi((p-1)^2)[/latex]

So, I attempted a solution as follows.
[latex]\phi(p^k) = p^{k-1}(p-1)[/latex]
Thus [latex]\phi(\phi(p^k)) = \phi(p^{k-1}(p-1)) = \phi(p^{k-1})\phi(p-1)[/latex] (as phi is multiplicative)
[latex]=p^{k-2}(p-1)\phi(p-1)[/latex]

Which seems fine so far, but things get a bit more complex now.

I can write p-1 in terms of prime products
[latex]p - 1 = \displaystyle q_1^{e_1}q_2^{e_2} \ldots q_n^{e_n}[/latex], where [latex]q_i[/latex] are primes, i = 1,2,....,n

So, [latex]\phi(p-1) = q_1^{{e_1}-1}({q_1}-1) \ldots q_n^{{e_n}-1}({q_n}-1)[/latex]

So, to get [latex]\phi(\phi(p^k))[/latex] which I have shown is equal [latex]=p^{k-2}(p-1)\phi(p-1)[/latex], by multiplication I get

[latex]\phi(\phi(p^k)) = p^{k-2}[ q_1^{{2e_1}-1}({q_1}-1) \ldots q_n^{{2e_n}-1}({q_n}-1)][/latex] - this is right, isn't it?

I'm not sure exactly how to finish this proof (i.e. show that the above is equal to the right hand side).

Could I say that [latex] q_1^{{2e_1}-1}({q_1}-1) \ldots q_n^{{2e_n}-1}({q_n}-1)[/latex] is what I would result in, if I got the Euler-Phi function of something in the form [latex]q_1^{2e_1}q_2^{2e_2} \ldots q_n^{2e_n}[/latex], which is the equivalent of [latex][q_1^{e_1}q_2^{e_2} \ldots q_n^{e_n}]^2[/latex] which is the same as [latex](p-1)^2[/latex], thus apparently completing the proof. Is this even valid?

If I worked down the right hand side, and show that it's equivalent to the left, somehow?

Thanks for reading.

CJC86

Yep, looks good to me.

Essentially, after you've shown that [LATEX]\phi(\phi(p^k)) = p^{k-2}(p-1)\phi(p-1)[/LATEX], you are left with showing that [LATEX] \phi(n^2) = n\phi(n)[/LATEX] for any n, which you have done.

**Timbuk2**

Thanks for answering! It came up recently in an exam, and I didn't get it to work out fully (but I used the same method). I probably made a mistake somewhere. When typing out the LaTeX it takes longer so I can go slowly through each step and don't make mistakes as much!

I didn't know that [latex]\phi(n^2) = n\phi(n)[/latex] - it seems like a useful property!

Thanks again!

FoxT

LaTex is beyond be I'm afraid....but a way of looking at this that I find more intuitive is as follows: if Instead of



we state

phi(p-1) = q1...qn(1-1/q1)...(1-1/qn) =(p-1)(1-1/q1)...(1-1/qn)

then (p-1) phi(p-1) = (p-1)^2 (1-1/q1)...(1-1/qn) = phi(p-1)^2

Your proof is fine as far as I can see, though!

Depending on your course, you might be expected to restate this line as follows:

Thus (as phi is multiplicative)

TO:

Thus

as gcd(p-1,p^(n-1))=1 by fundamental th arith., and
phi (ab) = phi(a)phi(b) when (a,b)=1


Sounds anal, but in number theory land, "multiplicative" means the arguments must be mutually prime, an issue that turned out to be a tripwire for me in the past

**Timbuk2**

Thanks a million for the answer!

Actually, you're right and I completely forgot, phi is multiplicative if the two numbers are mutually prime. So I'd imagine that would need to be part of the proof. That actually happens in quite a few places in number theory, and I very often forget to actually state it!

For the reference, I'm a first year Actuary student in UCD - the subject is Numbers and Functions (which is mainly Number Theory).

Thanks again for the help!

FoxT

You're welcome - I enjoyed it. Did engineering years back but still do a bit of math on the side for fun. Actuary - sounds like a v. interesting course - enjoying it?

**Timbuk2**

FoxT wrote: »

You're welcome - I enjoyed it. Did engineering years back but still do a bit of math on the side for fun. Actuary - sounds like a v. interesting course - enjoying it?

I'm loving it so far, it's extremely interesting! I especially like the Statistics that we do. The Mathematics that we are doing in first year is interesting, but there are tough aspects to it - some of it is more 'abstract' than I would have been used to (from Leaving Cert), such as Vector Spaces, Groups and Fields etc. In the module Numbers and Functions, which is where my question in this thread comes from, we do Number Theory and Combinatorics (mainly) which I find extremely interesting!