Welcome to our community

Be a part of something great, join today!

Euler totient function proof

  • Thread starter
  • Banned
  • #1

Poirot

Banned
Feb 15, 2012
250
prove that there is no positve integer n such that g(n) dividies n/5, where g is the euler totient function.
 
  • Thread starter
  • Banned
  • #2

Poirot

Banned
Feb 15, 2012
250
Re: euler totient function proof

I think you misunderstand.
 

mathbalarka

Well-known member
MHB Math Helper
Mar 22, 2013
573
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 \(\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.
 
  • Thread starter
  • Banned
  • #4

Poirot

Banned
Feb 15, 2012
250
Re: euler totient function proof

I can assure you it is not a difficult challenge.
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
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}$$
[JUSTIFY]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.
[/JUSTIFY]

[HR][/HR]

[JUSTIFY]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.[/JUSTIFY]
 
  • Thread starter
  • Banned
  • #6

Poirot

Banned
Feb 15, 2012
250
Yes, well done.
 
  • Thread starter
  • Banned
  • #7

Poirot

Banned
Feb 15, 2012
250
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}$$
[JUSTIFY]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.
[/JUSTIFY]

[HR][/HR]

[JUSTIFY]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.[/JUSTIFY]

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.