MHB Can the Euler Totient Function Ever Divide n/5 for Any Positive Integer n?

AI Thread Summary
The discussion centers on proving that there is no positive integer n such that the Euler totient function g(n) divides n/5. Participants clarify that n must be a multiple of 5, leading to the expression g(n) = 5^(l - 1) * 4 * φ(m) for n = 5^l * m, where m is not a multiple of 5. They demonstrate that assuming g(n) divides n/5 leads to contradictions, particularly noting that φ(m) cannot divide m under the given conditions. The conclusion reached is that the original statement holds true, and the proof, despite being hastily written, effectively conveys the core argument.
Poirot1
Messages
243
Reaction score
0
prove that there is no positve integer n such that g(n) dividies n/5, where g is the euler totient function.
 
Mathematics news on Phys.org
Re: euler totient function proof

I think you misunderstand.
 
Re: euler totient function proof

Poirot said:
I think you misunderstand.

Yep, I surely did. I overlooked the word "divides".

This challenge seems far more harder than it looks like. I don't think I am at the state of attempting it since I am quite sleepy now (11 : 50 here) so I will consider looking at it in the morning if not already being answered till then.

As a note for who thinks $$\phi (n)$$ always exceeds n/5 for all n and therefore proving the challenge, I'd like to let you informed about that n/k always exceeds $$\pi (n)$$ for any k but it takes large n to do that since the denominator $$O(\log \log(n)) + O \left (\frac{1}{\log \log(n)} \right )$$ grows very slowly as the upper bound for totient but still reaches infinity somehow.
 
Re: euler totient function proof

I can assure you it is not a difficult challenge.
 
Re: euler totient function proof

First we see $n$ has to be a multiple of $5$, otherwise $n / 5$ is not an integer. so $n = 5^l \cdot m$ and $m$ not a multiple of $5$.

Then we have $\phi(n) = 5^{l - 1} 4 \phi(m)$. Now assume $5^{l - 1} 4 \phi(m)$ does divide $m$. Therefore:

$$m = k \cdot 5^{l - 1} 4 \phi(m) \tag{1}$$
Now let the factorization of $m$ be the quasi-general form ($m$ not a power of two, and not a multiple of $5$):

$$m = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r} ~ ~ ~ ~ \text{with} ~ ~ ~ ~ p_r ~ ~ \text{odd} ~ ~ ~ ~ \text{and} ~ ~ p_1 \ne p_2 \ne \cdots \ne p_r \ne 5$$
Then, it follows that:

$$\phi(m) = \left [ p_1^{\alpha_1 - 1} p_2^{\alpha_2 - 1} \cdots p_r^{\alpha_r - 1} \right ] \cdot \left ( p_1 - 1 \right ) \left ( p_2 - 1 \right ) \cdots \left (p_r - 1 \right )$$
And it should be clear that $(1)$ can never be satisfied, as the prime power $p_r^{\alpha_r}$ cannot divide $\phi(m)$. We have one case left, when $m$ is a power of two. Then:

$$m = 2^e ~ ~ ~ \implies ~ ~ ~ 5^{l - 1} 4 \phi(m) = 5^{l - 1} 2^{e + 1}$$
We see $5^{l - 1} 4 \phi(m) > m$ and so $(1)$ still does not hold.

We reach a contradiction, and Poirot's statement holds true. QED.



Ok I will agree this proof is poorly written but I've jotted it down hastily. Hopefully the underlying idea is still clear (the core concept is pretty much that $\phi(m)$ does not divide $m$). It could probably be generalized for divisors other than $5$, but one must be careful about the special case $m$ is a power of two, which occurs because $\phi(5)$ happens to be a power of two.​
 
Yes, well done.
 
Re: euler totient function proof

Bacterius said:
First we see $n$ has to be a multiple of $5$, otherwise $n / 5$ is not an integer. so $n = 5^l \cdot m$ and $m$ not a multiple of $5$.

Then we have $\phi(n) = 5^{l - 1} 4 \phi(m)$. Now assume $5^{l - 1} 4 \phi(m)$ does divide $m$. Therefore:

$$m = k \cdot 5^{l - 1} 4 \phi(m) \tag{1}$$
Now let the factorization of $m$ be the quasi-general form ($m$ not a power of two, and not a multiple of $5$):

$$m = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_r^{\alpha_r} ~ ~ ~ ~ \text{with} ~ ~ ~ ~ p_r ~ ~ \text{odd} ~ ~ ~ ~ \text{and} ~ ~ p_1 \ne p_2 \ne \cdots \ne p_r \ne 5$$
Then, it follows that:

$$\phi(m) = \left [ p_1^{\alpha_1 - 1} p_2^{\alpha_2 - 1} \cdots p_r^{\alpha_r - 1} \right ] \cdot \left ( p_1 - 1 \right ) \left ( p_2 - 1 \right ) \cdots \left (p_r - 1 \right )$$
And it should be clear that $(1)$ can never be satisfied, as the prime power $p_r^{\alpha_r}$ cannot divide $\phi(m)$. We have one case left, when $m$ is a power of two. Then:

$$m = 2^e ~ ~ ~ \implies ~ ~ ~ 5^{l - 1} 4 \phi(m) = 5^{l - 1} 2^{e + 1}$$
We see $5^{l - 1} 4 \phi(m) > m$ and so $(1)$ still does not hold.

We reach a contradiction, and Poirot's statement holds true. QED.



Ok I will agree this proof is poorly written but I've jotted it down hastily. Hopefully the underlying idea is still clear (the core concept is pretty much that $\phi(m)$ does not divide $m$). It could probably be generalized for divisors other than $5$, but one must be careful about the special case $m$ is a power of two, which occurs because $\phi(5)$ happens to be a power of two.​
My proof: Assume to the contary. Firstly, n is divisible by 5. Let $p_{1}$,...$p_{t}$ be the other prime factors of n.
Then g(n)=n(1-0.2)(1-(1/p_1))...(1-(1/p_t))=4n/5(1-(1/p_1))...(1-1/p_t))
But mg(n)=n/5 for some m so we get:

4m((1-(1/p_1))...(1-1/p_t))=1
Multiplying through by $p_{1}...p_{t}$ gives

$4m(1-p_{1})...(1-p_{t})=p_{1}...p_{t}$

We may assume the primes are in ascending order, and if p_1 is not 2, then the RHS is odd while the LHS is even. Therefore $p_{1}=2$ and upon dividing the equation by this we get:

$2m(1-p_{2})...(1-p_{t})=p_{2}...p_{t}$.

So the LHS is even, whilst the RHS, being a product of odds, is odd - contradiction.
 
Back
Top