- Thread starter
- Banned
- #1

- Thread starter Poirot
- Start date

- Thread starter
- Banned
- #1

- Jan 26, 2012

- 644

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.

$$\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:

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

[tex] n = 3^r 5^s p^t...(1) [/tex]

g is multiplicative

[tex]g(n) = g(3^r)\cdot g(5^s)\cdot g(p^t) [/tex]

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

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

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

from (1)

[tex] 3^r\cdot 5^s = \frac{n}{p^t} [/tex]

[tex] g(n) = \frac{8n}{15} \frac{g(p^t)}{p^t} [/tex]

we want p such that [tex] g(p^t) = p^t [/tex] , thats true for 1 just

- Feb 13, 2012

- 1,704

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

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?

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

... so that Your equation...

$\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$