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
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.
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.
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.
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.
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?
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...