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