Welcome to our community

Be a part of something great, join today!

Number Theory Totient function proof

  • Thread starter
  • Banned
  • #1

Poirot

Banned
Feb 15, 2012
250

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
Jan 26, 2012
644
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
Mar 1, 2012
275
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
[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
 

chisigma

Well-known member
Feb 13, 2012
1,704

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)

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