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

• Math100
In summary: Now we are in trouble. We could have ##k_1=5## and ##k_4=1## but that would require ##k_2=k_3=0##. So there is no general formula - we must consider all cases separately.Do you have a different approach?I am sorry, I do not have any other approach.
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 ##.

Let me think loud.

Math100 said:
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.
Math100 said:
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.
Math100 said:
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.

Math100 said:
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
fresh_42 said:
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?

Math100 said:
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}$$

fresh_42 said:
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 ##

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

Math100 said:
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}$$

fresh_42 said:
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?

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.

Last edited:
fresh_42 said:
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 ##

Math100 said:
## (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 ##
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.

Last edited:
fresh_42 said:
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.

Math100 said:
The last half of the latex command doesn't really show.
Sorry, I had forgotten ## somewhere. I fixed it.

Math100
fresh_42 said:
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?

Math100 said:
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.

Math100

## 1. What is the definition of phi (φ) function in number theory?

The phi (φ) function, also known as Euler's totient function, is a number theory function that counts the positive integers less than or equal to a given integer n that are relatively prime to n. In other words, it calculates the number of positive integers that are coprime to n.

## 2. How is the phi (φ) function related to Euler's theorem?

Euler's theorem states that if a and n are coprime positive integers, then a raised to the power of phi (φ) of n is congruent to 1 modulo n. In other words, a^φ(n) ≡ 1 (mod n). This relationship is used to find the value of phi (φ) for a given integer n.

## 3. How can we determine all integers n for which phi (φ) of n is equal to 16?

To determine all integers n for which phi (φ) of n is equal to 16, we can use the fact that phi (φ) of a prime number p is equal to p-1. Therefore, we need to find all prime numbers that are one more than 16. These prime numbers are 17, 19, and 31. Additionally, we can use the formula phi (φ) of n = n * (1-1/p1) * (1-1/p2) * ... * (1-1/pk) where p1, p2, ..., pk are the distinct prime factors of n. By plugging in 16 for phi (φ) of n and solving for n, we can find all the possible values of n.

## 4. Are there any other methods to solve for the values of n where phi (φ) of n is equal to 16?

Yes, there are other methods to solve for the values of n where phi (φ) of n is equal to 16. One method is to use a computer program or online calculator that can calculate phi (φ) of a given integer. Another method is to use the fact that phi (φ) of a power of a prime number p^k is equal to p^(k-1) * (p-1). By finding all the prime numbers that are one more than 16, we can then find all the possible values of n by taking the powers of these prime numbers.

## 5. What is the significance of finding all integers n for which phi (φ) of n is equal to 16?

Finding all integers n for which phi (φ) of n is equal to 16 has significance in many areas of mathematics, including number theory, cryptography, and group theory. It can also be useful in solving certain mathematical problems and equations. Additionally, understanding the values of phi (φ) for different integers can help in understanding the properties of integers and their relationships with other mathematical concepts.

Replies
19
Views
919
Replies
10
Views
993
Replies
5
Views
987
Replies
13
Views
1K
Replies
1
Views
879
Replies
10
Views
1K
Replies
6
Views
2K
Replies
4
Views
1K
Replies
3
Views
1K
Replies
4
Views
2K