I'm 14, and have been given a project over the holidays. It's about Euler's phi function and I am completely stuck. I've been struggling through the project and am particulary stuck on two questions.
If we take P as a prime number, obtain an expression for phi(p^3). So far, I know that
phi(3^3)=18
phi(5^3)=100
phi(7^3)=294
I don't know how to obtain an expression. If it helps, phi(p^2)=p(p-1)
I don't even know wehre to get started on phi(p^n) as well.
OK that's cool, I thought that would be it although I'm really surprised you managed to compute using that definition!
Consider the nth power of a prime, , what numbers less than this share a factor with ?
Firstly what are the factors of ? Clearly just 1 and . So any number less than that share a factor must have p as a factor. Can you figure out how many such numbers there are? When you work this out, subtract this number from and you will have the result for (Effectively what you have done, is instead of working out how many numbers are coprime, you have worked out how many are not coprime, and subtracted this from p^n)
This will give you a quick generel result for and you can just change the n to a three to give you your answer.
Good luck, and let us know where you get stuck.
Right, SO these are my workings- can you tell me if I have gone wrong or can you help me with certain bits. (Forgiver me if I copy you a bit.)
The factors of P^n are 1 and P. Any number less than P^n that shares a factor must have p as a factor. (yeah, you told me that.... :P )
there are 3 numbers less than p^n. These are 1, P, and P^2.
Therefore phi(P^n)=P^n-3
But that doesn't work, because there are also common factors. For example, with 5^3 you have to take in all the factors of 5.
The mistake you have made is that I said the numbers share a factor, not have only p as a factor.
Take 3^3 for example. Which numbers less than 27 share a factor with it?
Clearly 1 does, 2 doesn't, 3 does, 4 doesn't, 5 doesn't. Does 6? Are 6 and 27 coprime? No, since 6 factors as 2*3, and so shares a factor of 3 with 27, yet it is't a power of three.
Can you see where to go now?
Although this is correct, OP is 14 and is doing this as a project, I don't think he'd be able to get away with saying
The 'fundamental theorem of arithmetic' establishes that for any integer n is
... where are distinct primes, and as consequence is...
Besides, he so nearly got there on his own.
Sorry, I didn't mean to patronise OP by implying he wouldn't understand the language, all I meant was that by the age of 14, the material you would have covered probably wouldn't allow the step from TFA to the formula for phi(n).
You usually do it the other way round anyway, the formula for phi(n) is usually deduced from the formula for phi(p^k), not the other way round. Potato potato I suppose.
I dont think that He has heard this in a Lady Gaga's song...