Euler's phi function

**jzellt** · April 7th 2010, 07:51 PM

I will denote the phi function to be &.
For example, &(36) = 36(1-1/2)(1-1/3) = 12

Find all n such that &(n) = 8.

How is this done w/o just guessing and checking? Thanks...

**Amer** · April 7th 2010, 08:24 PM

Originally Posted by jzellt

I will denote the phi function to be &.
For example, &(36) = 36(1-1/2)(1-1/3) = 12

Find all n such that &(n) = 8. Find them and prove there is no more.

How is this done w/o just guessing and checking? Thanks...

$\phi(n) = 8$

as you know

$\phi(p^n) = (p^n - p^{n-1})$

so n is a multiple of 2 just since if it is multiple from another prime it will be a divisor of phi(n) is it ok for now

so n contains just 2

suppose $n = 2^t$

$\phi(2^t) = 2^t - 2^{t-1} = 8$

$2^{t-1}(2-1) = 8 \rightarrow t-1=3$

so

$n= 2^4$

**jzellt** · April 7th 2010, 10:13 PM

I thought I understood, but I guess I'm still a bit confused...

What if I had to find all n such that &(n) = 2?

The above seems to calculate how many n, but not what each n is.

Can you elaborate...

Thanks.

**Amer** · April 7th 2010, 10:35 PM

"so n is a multiple of 2 just since if it is multiple from another prime it will be a divisor of phi(n) is it ok for now"

this is wrong statement I forgot number theory sorry

phi(5) = 4 and 2 is not a divisor of 5

phi(15) = 2(4) = 8

there is another solutions

I can't figure exactly how I can solve it sorry

**chiph588@** · April 8th 2010, 02:58 PM

Originally Posted by Amer

$\phi(n) = 8$

as you know

$\phi(p^n) = (p^n - p^{n-1})$

so n is a multiple of 2 just since if it is multiple from another prime it will be a divisor of phi(n) is it ok for now

so n contains just 2

suppose $n = 2^t$

$\phi(2^t) = 2^t - 2^{t-1} = 8$

$2^{t-1}(2-1) = 8 \rightarrow t-1=3$

so

$n= 2^4$

The above works for when $n=p^a$

What if $n=p^a q^b$ ?

$\phi(n) = p^{a-1}(p-1)q^{b-1}(q-1)$ . Now if $p,q\neq2$ we have then that $p^{a-1}=q^{b-1}=1 \implies a=b=1$ and WLOG $p-1=4,\; q-1=2 \implies p=5,\; q=3$ .
Thus $n=15$ .

WLOG if $p=2$ , then $\phi(n) = 2^{a-1}q^{b-1}(q-1)$ . This means again that $q^{b-1} = 1\implies b=1$ . So we could have $q-1=2,\; 2^{a-1} = 4$ or $q-1=4,\; 2^{a-1}=2$ . Or in other words $q=3,\;a=3$ or $q=5,\; a=2$ .
Thus $n=24 \text{ or } n=20$

What if $n=2p^aq^b$ ? I'll let you do this one (hint: what's $\phi(n)$ ?). The answer comes out to be $n=30$ .

Now what about other $n$ ? Well, it turns out that with three or more prime divisors, there are just too many factors in $\phi(n)$ i.e. $p_1-1,p_2-1,p_3-1,\cdots$ will all be even and distinct, thus making $\phi(n)>8$ .

So here's all $n$ with $\phi(n)=8$ : $n=\{15,16,20,24,30\}$ .

Thread: Euler's phi function

LinkBack

Thread Tools

Display

Euler's phi function

Similar Math Help Forum Discussions

Euler Phi function II

Euler's phi function

Euler's Function

euler phi function and others

Help with euler-phi function

Search Tags