Determine all integers ## n ## for which ## \phi(n)=16 ##

[Math100]

Homework Statement

Determine all integers $n$ for which $\phi(n)=16$.

Relevant Equations

None.

Suppose that $n=p_{1}^{k_1}p_{2}^{k_2}\dotsb p_{r}^{k_r}$ satisfies $\phi(n)=k$.
Then $n=\frac{k}{\prod(p_{i}-1)}\prod p_{i}$.
Note that the integers $d_{i}=p_{i}-1$ can be determined by the conditions
$(1) d_{i}\mid k, (2) d_{i}+1$ is prime, and $(3) \frac{k}{\prod d_{i}}$ contains no prime factor not in $\prod p_{i}$.
Consider $\phi(n)=16$.
Then $k=16$.
Since $d_{i}\mid 16$ and $d_{i}+1$ is prime, it follows that $d_{i}$ must be a power of $2$.
Hence $d_{i}\in\{ 1, 2, 4, 16\}$ and $p_{i}\in\{ 2, 3, 5, 17\}$.
Observe that $\phi(n)=2^{k_{1}-1}(3-1)^{k_{2}}(5-1)^{k_{3}}\dotsb (p_{r}-1)^{k_{r}}$.
Thus
\begin{align*}
&2^{k_{1}-1}=16\implies k_{1}=5\\
&(3-1)^{k_{2}}=16\implies 2^{k_{2}}=16\implies k_{2}=4\\
&(5-1)^{k_{3}}=16\implies 4^{k_{3}}=16\implies k_{3}=2\\
&(17-1)^{k_{r}}=16\implies 16^{k_{r}}=16\implies k_{r}=1.\\
\end{align*}
Now we see that $n=17, 17(2)=34, 2^{5}=32, 2^{4}\cdot 3=48, 2^{3}\cdot 5=40, 2^{2}\cdot 3\cdot 5=60$.
Therefore, $\phi(n)=16$ when $n=17, 32, 34, 40, 48,$ and $60$.

 

[fresh_42]

Let me think loud.

Homework Statement:: Determine all integers $n$ for which $\phi(n)=16$.
Relevant Equations:: None.

Suppose that $n=p_{1}^{k_1}p_{2}^{k_2}\dotsb p_{r}^{k_r}$ satisfies $\phi(n)=k$.
Then $n=\frac{k}{\prod(p_{i}-1)}\prod p_{i}$.

The general formula is $\varphi (n)=k=n\cdot \prod_{i=1}^r \left(1-\dfrac{1}{p_i}\right).$ From there we get your formula.

Note that the integers $d_{i}=p_{i}-1$ can be determined by the conditions
$(1) d_{i}\mid k, (2) d_{i}+1$ is prime, and $(3) \frac{k}{\prod d_{i}}$ contains no prime factor not in $\prod p_{i}$.
Consider $\phi(n)=16$.
Then $k=16$.
Since $d_{i}\mid 16$ and $d_{i}+1$ is prime, it follows that $d_{i}$ must be a power of $2$.
Hence $d_{i}\in\{ 1, 2, 4, 16\}$ and $p_{i}\in\{ 2, 3, 5, 17\}$.

Either you write:
Hence $d_{i}\in\{ 1, 2, 4, 8, 16\}$ and $p_{i}\in\{ 2, 3, 5, 17\}$.
or you write:
Hence $p_{i}\in\{ 2, 3, 5, 17\}$.

Hence means an implication. The only implication so far is $d_i=2^{m_i}.$ We can only rule out $d_i=8$ after listing the primes, not before. Hence 'hence' is misleading.

Observe that $\phi(n)=2^{k_{1}-1}(3-1)^{k_{2}}(5-1)^{k_{3}}\dotsb (p_{r}-1)^{k_{r}}$.

Here I get lost. We have
\begin{align*}
\varphi (n) &=\prod_{i=1}^r p_i^{k_i -1}(p_i-1)
\end{align*}

I see that your solution is correct, but I do not see why your formula is correct.

Thus
\begin{align*}
&2^{k_{1}-1}=16\implies k_{1}=5\\
&(3-1)^{k_{2}}=16\implies 2^{k_{2}}=16\implies k_{2}=4\\
&(5-1)^{k_{3}}=16\implies 4^{k_{3}}=16\implies k_{3}=2\\
&(17-1)^{k_{r}}=16\implies 16^{k_{r}}=16\implies k_{r}=1.\\
\end{align*}
Now we see that $n=17, 17(2)=34, 2^{5}=32, 2^{4}\cdot 3=48, 2^{3}\cdot 5=40, 2^{2}\cdot 3\cdot 5=60$.
Therefore, $\phi(n)=16$ when $n=17, 32, 34, 40, 48,$ and $60$.

 

[Math100]

Let me think loud.The general formula is $\varphi (n)=k=n\cdot \prod_{i=1}^r \left(1-\dfrac{1}{p_i}\right).$ From there we get your formula.

Either you write:
Hence $d_{i}\in\{ 1, 2, 4, 8, 16\}$ and $p_{i}\in\{ 2, 3, 5, 17\}$.
or you write:
Hence $p_{i}\in\{ 2, 3, 5, 17\}$.

Hence means an implication. The only implication so far is $d_i=2^{m_i}.$ We can only rule out $d_i=8$ after listing the primes, not before. Hence 'hence' is misleading.

Here I get lost. We have
\begin{align*}
\varphi (n) &=\prod_{i=1}^r p_i^{k_i -1}(p_i-1)
\end{align*}

I see that your solution is correct, but I do not see why your formula is correct.

I am sorry about the confusion regarding formula. And what other word(s) should I replace 'Hence'? Also, do I have to show/prove how I got the $n=17, 17(2)=34$ part by explaining?

 

[fresh_42]

I am sorry about the confusion regarding formula. And what other word(s) should I replace 'Hence'? Also, do I have to show/prove how I got the $n=17, 17(2)=34$ part by explaining?

The hence thingy is not important. I would simply say that $p_i\in \{2,3,5,17\}$ follows.

The formula
$$
\phi(n)=2^{k_{1}-1}(3-1)^{k_{2}}(5-1)^{k_{3}}\dotsb (p_{r}-1)^{k_{r}}
$$
is what I do not see.

Can you derive it from your first version?
$$
n=\frac{16}{\prod(p_{i}-1)}\prod p_{i}
$$

 

[Math100]

The hence thingy is not important. I would simply say that $p_i\in \{2,3,5,17\}$ follows.

The formula
$$
\phi(n)=2^{k_{1}-1}(3-1)^{k_{2}}(5-1)^{k_{3}}\dotsb (p_{r}-1)^{k_{r}}
$$
is what I do not see.

Can you derive it from your first version?
$$
n=\frac{16}{\prod(p_{i}-1)}\prod p_{i}
$$

$\phi(n)=\prod_{i=1}^r p_{i}^{k_{i}-1}(p_{i}-1)=16$

 

[Math100]

But no, I want to know how to derive it from my first version.

 

[fresh_42]

But no, I want to know how to derive it from my first version.

I think it is wrong.

I only see that we must consider all possible cases of $n=2^{k_1}\cdot 3^{k_2}\cdot 5^{k_3}\cdot 17^{k_4}.$ There might be a more elegant way but I do not see it from the spot.

We have
$$
16=\underbrace{\left(2^{k_1-1}\right)}_{\text{if }k_1>0}\cdot \underbrace{\left(2\cdot 3^{k_2-1}\right)}_{\text{if }k_2>0}\cdot\underbrace{\left(4\cdot 5^{k_3-1}\right)}_{\text{if }k_3>0}\cdot\underbrace{\left(16\cdot 17^{k_4-1}\right)}_{\text{if }k_4>0}
$$

 

[Math100]

I think it is wrong.

I only see that we must consider all possible cases of $n=2^{k_1}\cdot 3^{k_2}\cdot 5^{k_3}\cdot 17^{k_4}.$ There might be a more elegant way but I do not see it from the spot.

We have
$$
16=\underbrace{\left(2^{k_1-1}\right)}_{\text{if }k_1>0}\cdot \underbrace{\left(2\cdot 3^{k_2-1}\right)}_{\text{if }k_2>0}\cdot\underbrace{\left(4\cdot 5^{k_3-1}\right)}_{\text{if }k_3>0}\cdot\underbrace{\left(16\cdot 17^{k_4-1}\right)}_{\text{if }k_4>0}
$$

So what should we do now?

 

[fresh_42]

Discuss it.
$$
16=\underbrace{\left(2^{k_1-1}\right)}_{\text{if }k_1>0}\cdot \underbrace{\left(2\cdot 3^{k_2-1}\right)}_{\text{if }k_2>0}\cdot\underbrace{\left(4\cdot 5^{k_3-1}\right)}_{\text{if }k_3>0}\cdot\underbrace{\left(16\cdot 17^{k_4-1}\right)}_{\text{if }k_4>0}
$$
Note that those factors do not occur at all if a $k_i=0.$$k_2,k_3,k_4\geq 2$ can be ruled out since we would get a prime $3,5,17$ on the right and not on the left. So $k_2,k_3,k_4 \in \{0,1\}.$ These are eight cases.
\begin{align*}
(k_2,k_3,k_4)&=(0,0,0)\\
(k_2,k_3,k_4)&=(0,0,1)\\
(k_2,k_3,k_4)&=(0,1,0)\\
(k_2,k_3,k_4)&=(0,1,1)\\
(k_2,k_3,k_4)&=(1,0,0)\\
(k_2,k_3,k_4)&=(1,0,1)\\
(k_2,k_3,k_4)&=(1,1,0)\\
(k_2,k_3,k_4)&=(1,1,1)
\end{align*}

Check which among them are possible and if so, determine $k_1.$ But some might have more than one solution. If you look at $(k_2,k_3,k_4)=(0,0,1)$ then it has $k_1=0$ and $k_1=1$ as a solution.

 

[Math100]

Discuss it.
$$
16=\underbrace{\left(2^{k_1-1}\right)}_{\text{if }k_1>0}\cdot \underbrace{\left(2\cdot 3^{k_2-1}\right)}_{\text{if }k_2>0}\cdot\underbrace{\left(4\cdot 5^{k_3-1}\right)}_{\text{if }k_3>0}\cdot\underbrace{\left(16\cdot 17^{k_4-1}\right)}_{\text{if }k_4>0}
$$
Note that those factors do not occur at all if a $k_i=0.$$k_2,k_3,k_4\geq 2$ can be ruled out since we would get a prime $3,5,17$ on the right and not on the left. So $k_2,k_3,k_4 \in \{0,1\}.$ These are eight cases.
\begin{align*}
(k_2,k_3,k_4)&=(0,0,0)\\
(k_2,k_3,k_4)&=(0,0,1)\\
(k_2,k_3,k_4)&=(0,1,0)\\
(k_2,k_3,k_4)&=(0,1,1)\\
(k_2,k_3,k_4)&=(1,0,0)\\
(k_2,k_3,k_4)&=(1,0,1)\\
(k_2,k_3,k_4)&=(1,1,0)\\
(k_2,k_3,k_4)&=(1,1,1)
\end{align*}

Check which among them are possible and if so, determine $k_1.$ But some might have more than one solution. If you look at $(k_2,k_3,k_4)=(0,0,1)$ then it has $k_1=0$ and $k_1=1$ as a solution.

$(k_{2}, k_{3}, k_{4})=(0, 0, 0), \frac{128}{255}$
$(k_{2}, k_{3}, k_{4})=(0, 0, 1), 16$
$(k_{2}, k_{3}, k_{4})=(0, 1, 0), 4$
$(k_{2}, k_{3}, k_{4})=(0, 1, 1), 64$
$(k_{2}, k_{3}, k_{4})=(1, 0, 0), 2$
$(k_{2}, k_{3}, k_{4})=(1, 0, 1), 32$
$(k_{2}, k_{3}, k_{4})=(1, 1, 0), 8$
$(k_{2}, k_{3}, k_{4})=(1, 1, 1), 128$
But how can these results lead us to the correct answers?

 

[fresh_42]

$(k_{2}, k_{3}, k_{4})=(0, 0, 0), \frac{128}{255}$
$(k_{2}, k_{3}, k_{4})=(0, 0, 1), 16$
$(k_{2}, k_{3}, k_{4})=(0, 1, 0), 4$
$(k_{2}, k_{3}, k_{4})=(0, 1, 1), 64$
$(k_{2}, k_{3}, k_{4})=(1, 0, 0), 2$
$(k_{2}, k_{3}, k_{4})=(1, 0, 1), 32$
$(k_{2}, k_{3}, k_{4})=(1, 1, 0), 8$
$(k_{2}, k_{3}, k_{4})=(1, 1, 1), 128$
But how can these results lead us to the correct answers?

It is important to note that those factors only occur if at least one of the primes actually occurs, that is, if some $k_i>0.$

If $(k_2,k_3,k_4)=(0,0,0)$ then we get $16=2^{k_1-1}$ which means $k_1=5$ and $n=32.$ $k_1=0$ is not possible in this case since we need at least one prime factor of $n.$

If $(k_2,k_3,k_4)=(0,0,1)$ then we get $16=2^{k_1-1}\cdot 16\cdot 17^{k_4-1}=2^{k_1-1}\cdot 16$ which means $k_1=1,$ and $n=34,$ or $k_1=0$ in which case we only have $16=16\cdot 17^{k_4-1}=16,$ and $n=17.$

If $(k_2,k_3,k_4)=(0,1,0)$ then we get $16=2^{k_1-1}\cdot 4 \cdot 5^{k_3-1}=2^{k_1-1}\cdot 4,$ i.e. $k_1=3,$ and $n= 8\cdot 5=40$ or we have $16= 4 \cdot 5^{k_3-1}=4$ which is always false and we have no solution where $n$ is only a power of five.

If $(k_2,k_3,k_4)=(0,1,1)$ then we get $16=2^{k_1-1}\cdot 4 \cdot 5^{k_3-1}\cdot 16 \cdot 17^{k_4-1}=2^{k_1}\cdot 32$ which is impossible for any $k_1\geq 0,$ or we get $16= 4 \cdot 5^{k_3-1}\cdot 16 \cdot 17^{k_4-1}= 4\cdot 16$ which is also impossible.

If $(k_2,k_3,k_4)=(1,0,0)$ then we get $16=2^{k_1-1}\cdot 2\cdot 3^{k_2-1}=2^{k_1}$ and $k_1=4$ with $n=16\cdot 3 =48,$ or we have $16=2\cdot 3^{k_2-1}=2$ which is impossible.

Etc.

 

[Math100]

It is important to note that those factors only occur if at least one of the primes actually occurs, that is, if some $k_i>0.$

If $(k_2,k_3,k_4)=(0,0,0)$ then we get $16=2^{k_1-1}$ which means $k_1=5$ and $n=32.$ $k_1=0$ is not possible in this case since we need at least one prime factor of $n.$

If $(k_2,k_3,k_4)=(0,0,1)$ then we get $16=2^{k_1-1}\cdot 16\cdot 17^{k_4-1}=2^{k_1-1}\cdot 16$ which means $k_1=1,$ and $n=34,$ or $k_1=0$ in which case we only have $16=16\cdot 17^{k_4-1}=16, and$n=17.$If$(k_2,k_3,k_4)=(0,1,0)$then we get$16=2^{k_1-1}\cdot 4 \cdot 5^{k_3-1}=2^{k_1-1}\cdot 4,$i.e.$k_1=3,$and$n= 8\cdot 5=40$or we have$16= 4 \cdot 5^{k_3-1}=4$which is always false and we have no solution where$n$is only a power of five. If$(k_2,k_3,k_4)=(0,1,1)$then we get$16=2^{k_1-1}\cdot 4 \cdot 5^{k_3-1}\cdot 16 \cdot 17^{k_4-1}=2^{k_1}\cdot 32 $which is impossible for any$k_1\geq 0,$or we get$16= 4 \cdot 5^{k_3-1}\cdot 16 \cdot 17^{k_4-1}= 4\cdot 16$which is also impossible. If$(k_2,k_3,k_4)=(1,0,0)$then we get$16=2^{k_1-1}\cdot 2\cdot 3^{k_2-1}=2^{k_1}$and$k_1=4$with$n=16\cdot 3 =48,$or we have$16=2\cdot 3^{k_2-1}=2## which is impossible.

Etc.

The last half of the latex command doesn't really show.

 

[fresh_42]

The last half of the latex command doesn't really show.

Sorry, I had forgotten ## somewhere. I fixed it.

 

[Math100]

It is important to note that those factors only occur if at least one of the primes actually occurs, that is, if some $k_i>0.$

If $(k_2,k_3,k_4)=(0,0,0)$ then we get $16=2^{k_1-1}$ which means $k_1=5$ and $n=32.$ $k_1=0$ is not possible in this case since we need at least one prime factor of $n.$

If $(k_2,k_3,k_4)=(0,0,1)$ then we get $16=2^{k_1-1}\cdot 16\cdot 17^{k_4-1}=2^{k_1-1}\cdot 16$ which means $k_1=1,$ and $n=34,$ or $k_1=0$ in which case we only have $16=16\cdot 17^{k_4-1}=16,$ and $n=17.$

If $(k_2,k_3,k_4)=(0,1,0)$ then we get $16=2^{k_1-1}\cdot 4 \cdot 5^{k_3-1}=2^{k_1-1}\cdot 4,$ i.e. $k_1=3,$ and $n= 8\cdot 5=40$ or we have $16= 4 \cdot 5^{k_3-1}=4$ which is always false and we have no solution where $n$ is only a power of five.

If $(k_2,k_3,k_4)=(0,1,1)$ then we get $16=2^{k_1-1}\cdot 4 \cdot 5^{k_3-1}\cdot 16 \cdot 17^{k_4-1}=2^{k_1}\cdot 32$ which is impossible for any $k_1\geq 0,$ or we get $16= 4 \cdot 5^{k_3-1}\cdot 16 \cdot 17^{k_4-1}= 4\cdot 16$ which is also impossible.

If $(k_2,k_3,k_4)=(1,0,0)$ then we get $16=2^{k_1-1}\cdot 2\cdot 3^{k_2-1}=2^{k_1}$ and $k_1=4$ with $n=16\cdot 3 =48,$ or we have $16=2\cdot 3^{k_2-1}=2$ which is impossible.

Etc.

So is this the only way to do this problem?

 

[fresh_42]

So is this the only way to do this problem?

It is what I saw. I suspect that there is a more elegant way, but I don't see it.

https://www.wolframalpha.com/input?i=phi(x)=16
would be a modern solution.

Another idea would be the examination of $k_1$ instead.
There is (modulo sign) exactly one solution for each $k_1=0,1,2,3,4,5.$

An algebraic approach would be: Determine all integers $n$ such that $| \mathbb{Z}_n^*|=16.$ Maybe there is some tricky theorem that helps tackle it from that side.