# Determine all integers ## n ##

• Math100
In summary: Hence ##p=3## and ##P=\dfrac{3}{2}\cdot \dfrac{p}{p-1}\in \mathbb{Z}## only if ##p=3.## So we have ##n=3^t\cdot 2^s## with ##t,s\in \mathbb{N}## and ##t\geq 0.##This is our necessary condition.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
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} ##.

Math100 said:
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\;?##

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

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

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

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

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

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?

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

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

Math100

## 1. What does it mean to "determine all integers ## n ##"?

When we say to "determine all integers ## n ##", we are asking for a list of all whole numbers that satisfy a certain condition or property. For example, we may want to determine all integers ## n ## that are divisible by 3.

## 2. How do you determine all integers ## n ## that satisfy a given condition?

The process of determining all integers ## n ## that satisfy a given condition will vary depending on the specific condition. In general, we can use mathematical techniques such as algebraic manipulation, number patterns, and logical reasoning to find all possible solutions.

## 3. Can there be an infinite number of integers ## n ## that satisfy a given condition?

Yes, it is possible for there to be an infinite number of integers ## n ## that satisfy a given condition. For example, if we are looking for all integers ## n ## that are divisible by 2, there are an infinite number of solutions (2, 4, 6, 8, etc.).

## 4. What is the importance of determining all integers ## n ##?

Determining all integers ## n ## is important in many areas of mathematics and science. It allows us to find patterns and relationships between numbers, make predictions, and solve problems. In some cases, determining all integers ## n ## can also help us prove theorems and make generalizations.

## 5. Are there any tools or techniques that can make determining all integers ## n ## easier?

Yes, there are various tools and techniques that can make determining all integers ## n ## easier. These include using algebraic equations, creating tables or graphs, and using computer programs or calculators to assist with calculations. It is also helpful to have a strong understanding of number properties and mathematical concepts.

• Precalculus Mathematics Homework Help
Replies
14
Views
1K
• Precalculus Mathematics Homework Help
Replies
4
Views
2K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
9
Views
2K
• Precalculus Mathematics Homework Help
Replies
13
Views
1K
• Precalculus Mathematics Homework Help
Replies
5
Views
2K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Precalculus Mathematics Homework Help
Replies
6
Views
1K
• Precalculus Mathematics Homework Help
Replies
3
Views
1K
• Precalculus Mathematics Homework Help
Replies
12
Views
2K