Determine all integers ## n ##

[Math100]

Homework Statement

Determine all integers $n$ for which $\phi(n)$ is a divisor of $n$.

Relevant Equations

None.

Observe that $\phi(1)=\phi(2)=1$.
This implies $\phi(1)\mid 1$ and $\phi(2)\mid 2$.
Thus $n=1$.
Let $n=p_{r}^{k_{1}}\dotsb p_{s}^{k_{s}}$ be the prime factorization of $n$.
Then $\phi(n)=n\prod_{p\mid n} (1-\frac{1}{p})$.
Suppose $\phi(n)\mid n$.
Then $\frac{n}{\phi(n)}=(\prod_{p\mid n} \frac{p}{p-1})$ for some $n\in\mathbb{Z^{+}}$.
Note that the prime divisors of $n$ must be $2$ or $3$ for $n>1$, because $p-1$ is even for $p\geq 3$.
Therefore, all integers $n$ for which $\phi(n)$ is a divisor of $n$ are $1, 2^{r}$ and $2^{r}3^{j}$ for some $r, j\in\mathbb{N}$.

 

[fresh_42]

Homework Statement:: Determine all integers $n$ for which $\phi(n)$ is a divisor of $n$.
Relevant Equations:: None.

Observe that $\phi(1)=\phi(2)=1$.
This implies $\phi(1)\mid 1$ and $\phi(2)\mid 2$.
Thus $n=1$.
Let $n=p_{r}^{k_{1}}\dotsb p_{s}^{k_{s}}$ be the prime factorization of $n$.
Then $\phi(n)=n\prod_{p\mid n} (1-\frac{1}{p})$.
Suppose $\phi(n)\mid n$.
Then $\frac{n}{\phi(n)}=(\prod_{p\mid n} \frac{p}{p-1})$ for some $n\in\mathbb{Z^{+}}$.
Note that the prime divisors of $n$ must be $2$ or $3$ for $n>1$, because $p-1$ is even for $p\geq 3$.
Therefore, all integers $n$ for which $\phi(n)$ is a divisor of $n$ are $1, 2^{r}$ and $2^{r}3^{j}$ for some $r, j\in\mathbb{N}$.

Looks good. I would write it differently.

We have $\varphi (n)=n\cdot \displaystyle{\prod_{p|n}\left(1-\dfrac{1}{p}\right)}$ and thus
$$
\dfrac{n}{\varphi (n)}=\prod_{p|n}\left(1-\dfrac{1}{p}\right)^{-1}=\prod_{p|n}\dfrac{p}{p-1}
$$
The necessary condition is that $P:=\displaystyle{\prod_{p|n}\dfrac{p}{p-1} } \in \mathbb{Z}.$

From here on I have difficulties with your rigor, which means you lost me.

If $p\geq 3$ then $\dfrac{p}{p-1}=\dfrac{2m+1}{2m}.$ So $P\in \mathbb{Z}$ only if $2m$ occurs in the numerator again without creating new denominators, i.e. is a power of $2,$ say $2m=2^k.$ Then $\varphi (p\cdot 2^k)=2^{k-1}\cdot (p-1) \,|\,(p\cdot 2^k)$ if $\dfrac{p-1}{2}\,|\,p$ which is only possible for $p=3$ and $k\geq 1.$

So $n=r^s\cdot 3^t$ with $s\in \mathbb{N}$ and $t \in \mathbb{N}_0:=\mathbb{N}\cup \{0\}.$

This is our necessary condition. (You have forgotten that all powers of $2$ without any $3's$ are a solution, and any power of $3's$ require at least one $2.$)

Is it also sufficient? Are all numbers $n=r^s\cdot 3^t$ with $s\geq 1\, , \,t\geq 0$ solutions to $\varphi (n)\,|\,n\;?$

 

[Math100]

Looks good. I would write it differently.

We have $\varphi (n)=n\cdot \displaystyle{\prod_{p|n}\left(1-\dfrac{1}{p}\right)}$ and thus
$$
\dfrac{n}{\varphi (n)}=\prod_{p|n}\left(1-\dfrac{1}{p}\right)^{-1}=\prod_{p|n}\dfrac{p}{p-1}
$$
The necessary condition is that $P:=\displaystyle{\prod_{p|n}\dfrac{p}{p-1} } \in \mathbb{Z}.$

From here on I have difficulties with your rigor, which means you lost me.

If $p\geq 3$ then $\dfrac{p}{p-1}=\dfrac{2m+1}{2m}.$ So $P\in \mathbb{Z}$ only if $2m$ occurs in the numerator again without creating new denominators, i.e. is a power of $2,$ say $2m=2^k.$ Then $\varphi (p\cdot 2^k)=2^{k-1}\cdot (p-1) \,|\,(p\cdot 2^k)$ if $\dfrac{p-1}{2}\,|\,p$ which is only possible for $p=3$ and $k\geq 1.$

So $n=r^s\cdot 3^t$ with $s\in \mathbb{N}$ and $t \in \mathbb{N}_0:=\mathbb{N}\cup \{0\}.$

This is our necessary condition. (You have forgotten that all powers of $2$ without any $3's$ are a solution, and any power of $3's$ require at least one $2.$)

Is it also sufficient? Are all numbers $n=r^s\cdot 3^t$ with $s\geq 1\, , \,t\geq 0$ solutions to $\varphi (n)\,|\,n\;?$

Not all numbers $n=r^{s}\cdot 3^{t}$ with $s\geq 1, t\geq 0$ are solutions to $\phi(n)\mid n$.

 

[fresh_42]

Not all numbers $n=r^{s}\cdot 3^{t}$ with $s\geq 1, t\geq 0$ are solutions to $\phi(n)\mid n$.

Sorry. Big typo! I meant $r=2.$

 

[Math100]

Sorry. Big typo! I meant $r=2.$

Yes, the counterexample is $r=1, s=2, t=1$. Because then we have $\phi(3)\nmid 3$.

 

[Math100]

And yes, all numbers $n=2^{s}\cdot 3^{t}$ with $s\geq 1, t\geq 0$ are solutions to $\phi(n)\mid n$.

 

[Math100]

Suppose $n=2^{s}\cdot 3^{t}$ with $s\geq 1, t\geq 0$.
Then $\phi(n)=\phi(2^{s})\phi(3^{t})=2^{s-1}\cdot 3^{t-1}\cdot 2=2^{s}\cdot 3^{t-1}$.
Thus $\phi(n)\mid n$ for $n=2^{s}\cdot 3^{t}$.

 

[Math100]

So how should I explain this part in the middle of my proof after mentioning the $p\geq 3$ part? Do I insert/add $2m=2^{k}$ part?

 

[fresh_42]

So how should I explain this part in the middle of my proof after mentioning the $p\geq 3$ part? Do I insert/add $2m=2^{k}$ part?

It is the essential part. I didn't get it in your version, so I wrote my own to convince myself. But, I am afraid, my version isn't perfect either. "... occurs in the numerator again without creating new denominators ..." isn't very professional. But my start was fine. Proofs in algebra are basically always indirect: What if ...

I think this is better:

If $p\geq 3$ Then $P\in \mathbb{Z}$ means
$$\prod_{p|n}\dfrac{p}{p-1}=\dfrac{2m+1}{2m}\prod_{p|n,p\neq 2m+1}\dfrac{p}{p-1}\in \mathbb{Z}
$$
This requires $2|p'$ for another prime $p'$ and $m=1$ which means $p=2\cdot 1+1=3.$

 

[Math100]

It is the essential part. I didn't get it in your version, so I wrote my own to convince myself. But, I am afraid, my version isn't perfect either. "... occurs in the numerator again without creating new denominators ..." isn't very professional. But my start was fine. Proofs in algebra are basically always indirect: What if ...

I think this is better:

If $p\geq 3$ Then $P\in \mathbb{Z}$ means $\prod_{p|n}\dfrac{p}{p-1}=\prod_{p|n}\dfrac{2m+1}{2m}$ This requires $2|n$ and $m=1$ which means $p=2\cdot 1+1=3.$

Yes, sorry, it's all my fault. I was trying to form this proof based on my textbook's answer, so it was very vague. I like your version much more.

 

[fresh_42]

Yes, sorry, it's all my fault. I was trying to form this proof based on my textbook's answer, so it was very vague. I like your version much more.

Reload the page. I corrected the formula a bit.