- #1

Math100

- 771

- 219

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

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