# Number TheoryTotient function proof

#### Poirot

##### Banned

Show that g(n)=8n/15 iff n is divisible by 3 and 5 and by no other primes, where g is the euler totient function.

How to go about the proof?

#### Bacterius

##### Well-known member
MHB Math Helper
Re: totient function proof

Rewrite $N$ as a product of powers of $3$ and $5$. Use the multiplicative property, and what is the totient of a prime power?

Full derivation below.

If $N = 3^m \cdot 5^n$ then $\varphi(N) = \varphi(3^m \cdot 5^n)$. Using the multiplicative property:

$$\varphi(3^m \cdot 5^n) = \varphi(3^m) \cdot \varphi(5^n)$$
And you know that for prime $p$ we have:

$$\varphi(p^k) = p^{k - 1} \cdot (p - 1)$$
And so:

$$\varphi(3^m) \cdot \varphi(5^n) = \left ( 3^{m - 1} \cdot (3 - 1) \right ) \cdot \left ( 5^{n - 1} \cdot (5 - 1) \right ) = 8 \cdot 3^{m - 1} \cdot 5^{n - 1}$$
And...

$$3^m \cdot 5^n = N ~ ~ ~ \implies ~ ~ ~ 3^m \cdot 5^n \cdot \left ( 3^{-1} \cdot 5^{-1} \right ) = 3^{m - 1} \cdot 5^{n - 1} = N \cdot 15^{-1}$$
And we conclude:

$$\varphi(N) = 8 \cdot 3^{m - 1} \cdot 5^{n - 1} = 8 \cdot N \cdot 15^{-1} = \frac{8}{15} \cdot N$$

Last edited:

#### Amer

##### Active member
Re: totient function proof

first n should be divisible by 3 and 5 since phi(n) is the number of the positive integers relatively prime with n
so phi(n) is integer for all n.
suppose n is divisible by another prime p, say
$$n = 3^r 5^s p^t...(1)$$
g is multiplicative
$$g(n) = g(3^r)\cdot g(5^s)\cdot g(p^t)$$

$$g(n) = 3^r \left( 1 - \frac{1}{3} \right) 5^s \left(1 - \frac{1}{5} \right)g(p^t)$$

$$g(n) = 3^r \left( \frac{2}{3} \right) 5^s \left(\frac{4}{5} \right) g(p^t)$$

$$g(n) =3^r\cdot 5^s \left( \frac{8}{15} \right) g(p^t)$$

from (1)
$$3^r\cdot 5^s = \frac{n}{p^t}$$

$$g(n) = \frac{8n}{15} \frac{g(p^t)}{p^t}$$
we want p such that $$g(p^t) = p^t$$ , thats true for 1 just

#### chisigma

##### Well-known member

Show that g(n)=8n/15 iff n is divisible by 3 and 5 and by no other primes, where g is the euler totient function.

How to go about the proof?

The basic formula of the Euler's Totiens Function is...

$\displaystyle \varphi (n) = n\ \prod _{p|n} (1-\frac{1}{p})$ (1)

$\displaystyle \varphi(n)= \frac{8\ n}{15}$ (2)

... is satisfied if...

$\displaystyle \prod _{p|n} (1-\frac{1}{p}) = \frac{8}{15}$ (3)

... and that happens only for $\displaystyle n= 3 \cdot 5 = 15$ ...

Kind regards

$\chi$ $\sigma$