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

[Poirot1]

prove that there is no positve integer n such that g(n) dividies n/5, where g is the euler totient function.

 

[Poirot1]

Re: euler totient function proof

I think you misunderstand.

 

[mathbalarka]

Re: euler totient function proof

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 \(\displaystyle \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 \(\displaystyle \pi (n)\) for any k but it takes large n to do that since the denominator \(\displaystyle 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.

 

[Poirot1]

Re: euler totient function proof

I can assure you it is not a difficult challenge.

 

[Nono713]

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

 

[Poirot1]

Yes, well done.

 

[Poirot1]

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

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.