1. ## Euler's phi function

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

2. 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...
$\displaystyle \phi(n) = 8$

as you know

$\displaystyle \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 $\displaystyle n = 2^t$

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

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

so

$\displaystyle n= 2^4$

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

4. "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

5. Originally Posted by Amer
$\displaystyle \phi(n) = 8$

as you know

$\displaystyle \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 $\displaystyle n = 2^t$

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

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

so

$\displaystyle n= 2^4$
The above works for when $\displaystyle n=p^a$

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

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

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

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

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

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