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

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
$\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\}$.