# Euler's phi function

• Jan 10th 2010, 11:49 AM
xWhiteyx
Euler's phi function
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.
• Jan 10th 2010, 11:58 AM
pomp
Quote:

Originally Posted by xWhiteyx
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.

Hello Whitey,

Quick question, what definition of Euler's Phi function are you using? I ask because there are many equivalent definitions for it, and helping you might be difficult not knowing which one you are using.
• Jan 10th 2010, 12:04 PM
xWhiteyx
Quote:

Originally Posted by pomp
Hello Whitey,

Quick question, what definition of Euler's Phi function are you using? I ask because there are many equivalent definitions for it, and helping you might be difficult not knowing which one you are using.

Two positive intergers are coprime if they have no factors other than 1 in common. For any positive interger n, the phi function phi(n) is defined as the number of positive intergers less than n, which are coprime to it.
• Jan 10th 2010, 12:08 PM
pomp
Quote:

Originally Posted by xWhiteyx
Two positive intergers are coprime if they have no factors other than 1 in common. For any positive interger n, the phi function phi(n) is defined as the number of positive intergers less than n, which are coprime to it.

OK that's cool, I thought that would be it although I'm really surprised you managed to compute $\displaystyle \phi(7^3)$ using that definition!

Consider the nth power of a prime, $\displaystyle p^n$, what numbers less than this share a factor with $\displaystyle p^n$ ?

Firstly what are the factors of $\displaystyle p^n$ ? Clearly just 1 and $\displaystyle p$. So any number less than $\displaystyle p^n$ 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 $\displaystyle p^n$ and you will have the result for $\displaystyle \phi(p^n)$ :) (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 $\displaystyle \phi(p^n)$ 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.
• Jan 10th 2010, 12:54 PM
xWhiteyx
Quote:

Originally Posted by pomp
OK that's cool, I thought that would be it although I'm really surprised you managed to compute $\displaystyle \phi(7^3)$ using that definition!

Consider the nth power of a prime, $\displaystyle p^n$, what numbers less than this share a factor with $\displaystyle p^n$ ?

Firstly what are the factors of $\displaystyle p^n$ ? Clearly just 1 and $\displaystyle p$. So any number less than $\displaystyle p^n$ 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 $\displaystyle p^n$ and you will have the result for $\displaystyle \phi(p^n)$ :) (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 $\displaystyle \phi(p^n)$ 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.
• Jan 10th 2010, 12:59 PM
pomp
Quote:

Originally Posted by xWhiteyx
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?
• Jan 11th 2010, 06:07 AM
xWhiteyx
Quote:

Originally Posted by pomp
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?

so 1, and all the factors of p go into p. So with 3^3, it's every 3rd, with 5^3, It's every 5th and so on. But I need to obtain an expression for that, and frankly, that just isn't coming into my head right now- and I'm still on the easy questions. ;(
• Jan 11th 2010, 01:32 PM
Drexel28
Quote:

Originally Posted by xWhiteyx
so 1, and all the factors of p go into p. So with 3^3, it's every 3rd, with 5^3, It's every 5th and so on. But I need to obtain an expression for that, and frankly, that just isn't coming into my head right now- and I'm still on the easy questions. ;http://mathhelpforum.com/advanced-math-topics/123151-eulers-phi-function.html#post436592\" rel=\"nofollow\">
so 1, and all the factors of p go into p. So with 3^3, it's every 3rd, with 5^3, It's every 5th and so on. But I need to obtain an expression for that, and frankly, that just isn't coming into my head right now- and I'm still on the easy questions. ;(

You've got it! You're so close, just keep going.

If every third number of 27 has a factor in common, how many such numbers are there? Can you see why it's just 27/3 ? Can you finish now?
• Jan 12th 2010, 04:28 AM
chisigma
The 'fundamental theorem of arithmetic' extablishes that for any integer n is...

$\displaystyle n=p_{1}^{k_{1}}\dots p_{r}^{k_{r}}$ (1)

... where $\displaystyle p_{1},\dots , p_{r}$ are distinct primes, and as consequence is...

$\displaystyle \varphi(n)= (p_{1}-1)\cdot p_{1}^{k_{1}-1} \dots (p_{r}-1)\cdot p_{r}^{k_{r}-1}$ (2)

If r=1 is...

$\displaystyle \varphi(n)= (p-1)\cdot p^{k-1}$ (3)

... and for k=3 is...

$\displaystyle \varphi(p^{3})= (p-1)\cdot p^{2}$ (4)

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
• Jan 12th 2010, 04:43 AM
pomp
Quote:

Originally Posted by chisigma
The 'fundamental theorem of arithmetic' extablishes that for any integer n is...

$\displaystyle n=p_{1}^{k_{1}}\dots p_{r}^{k_{r}}$ (1)

... where $\displaystyle p_{1},\dots , p_{r}$ are distinct primes, and as consequence is...

$\displaystyle \varphi(n)= (p_{1}-1)\cdot p_{1}^{k_{1}-1} \dots (p_{r}-1)\cdot p_{r}^{k_{r}-1}$ (2)

If r=1 is...

$\displaystyle \varphi(n)= (p-1)\cdot p^{k-1}$ (3)

... and for k=3 is...

$\displaystyle \varphi(p^{3})= (p-1)\cdot p^{2}$ (4)

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$

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

$\displaystyle n=p_{1}^{k_{1}}\dots p_{r}^{k_{r}}$

... where $\displaystyle p_{1},\dots , p_{r}$ are distinct primes, and as consequence is...

$\displaystyle \varphi(n)= (p_{1}-1)\cdot p_{1}^{k_{1}-1} \dots (p_{r}-1)\cdot p_{r}^{k_{r}-1}$

(Giggle)

Besides, he so nearly got there on his own.
• Jan 12th 2010, 05:03 AM
chisigma
The fact that OP is 14 doesn't mean that He doesn't understand the mathematical language... in fact He spoke of 'Euler phi function' and I dont think that He has heard this in a Lady Gaga's song (Giggle) ...

Kind regards

$\displaystyle \chi$ $\displaystyle \sigma$
• Jan 12th 2010, 05:10 AM
pomp
Quote:

Originally Posted by chisigma
The fact that OP is 14 doesn't mean that He doesn't understand the mathematical language... in fact He spoke of 'Euler phi function'

$\displaystyle \chi$ $\displaystyle \sigma$

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.

Quote:

I dont think that He has heard this in a Lady Gaga's song...

(Rofl)